极快的业务对象过滤

• 下载演示 - 25.2 KB

引言

你是否遇到过在多个不同属性上过滤大量业务对象集合时性能瓶颈的问题？

类似于这样吗？

//_tasks is a List<Task>

List<Task> filteredList = new List<Task>();
    foreach (Task t in _tasks)

        if (t.Type == "Product Backlog Item" && t.Number = 9)
            filteredList.Add(t);

    return filteredList;

//Time it took to complete filtering 5000 Tasks
//1680401 Ticks

但是，如果能做到像这样，产生与之前方法相同的结果呢？

//_tasks is the IndexableCollection<T> described in this article

return _tasks.Find("Type", "Product Backlog Item").Intersect<Task>(_tasks.Find("Number", 9));

//Time it took to complete filtering 5000 Tasks
//581 ticks!!

不，这不是笔误。这是性能提升了 289200%。

现在，有一个限制。这仅在你想要过滤的属性上，项目集合的差异比率较低时才有效。进行以下计算：

# of possible values for the property / Total Items in Collection = ratio 

在我的例子中，Type 属性只有 5 个可能的值，而 Number 属性有 14 个可能的值。所以，我的比率将是 5/5000 和 14/5000，两者都非常接近 0。随着该比率越来越接近 0，内存开销会减少，性能会提高。即使比率接近 1，我仍然注意到性能有了很大提升，但内存开销也显著增加。

使用代码

首先，你需要安装 .NET 3.5 Framework。唯一依赖 3.5 的是 HashSet<T> 类。这可以很容易地替换为普通的 HashTable，这将使其能够与 2.0 一起使用。

接下来，将 [IndexedProperty()] 属性添加到你想要过滤的类的任何属性上。你必须注意的一件事是，你正在过滤的属性不能有 null 值。由于我们索引属性的方式，我们必须用一个值代替 null。你可以在创建属性时传入你想要用什么值来表示 null。如果属性的类型是值类型，并且不能为 null，则使用无参数构造函数。

以下示例使用 String.Empty 代替 null 来索引属性

[IndexedProperty(string.Empty)]
public string Type
{
    get
    {
        return _type;
    }
    set
    {
        _type = value;

        OnPropertyChanged("Type");
    }
}

现在，创建一个 IndexableCollection<T> 的实例（对 T 的唯一限制是它需要实现 INotifyPropertyChanged）。当 T 的父级 IndexableCollection<T> 捕获 PropertyChanged 事件时，索引会被构建和更新。

就是这样！

现在，你可以做一些有趣的事情，比如这样：

_tasks.Find("Type", "Product Backlog Item")

这将返回所有 Type == "Product Backlog Item" 的任务。

最后总结一下。这是代码（你还可以从附加的 zip 文件中下载示例应用程序和代码）

public class IndexableCollection<T> : BindingList<T> where T : INotifyPropertyChanged
{
    private Dictionary<string, object> _indexedProperties;

    private Dictionary<string, IDictionary> _propertyHashes = 
                        new Dictionary<string, IDictionary>();
    private Dictionary<T, Dictionary<string, 
      HashSet<T>>> _currentPropertyHashes = 
      new Dictionary<T, Dictionary<string, HashSet<T>>>();

    public bool IsPropertyIndexed(string propertyName)
    {
        return _indexedProperties.ContainsKey(propertyName);
    }

    public IndexableCollection()
    {
        //we cach the indexed properties so we can quickly
        //see if a property is indexed during the listchanged event
        _indexedProperties = new Dictionary<string, object>();
        foreach (PropertyInfo info in typeof(T).GetProperties())
        {
            object[] temp = info.GetCustomAttributes(typeof(IndexedProperty), false);

            if (temp.Count<object>() > 0)
                _indexedProperties.Add(info.Name, 
                  ((IndexedProperty)temp[0]).NullValue);
        }
    }

    protected override void SetItem(int index, T item)
    {
        T obj = this[index];
        RemoveAllHases(obj);

        SetAllHashes(item);
        base.SetItem(index, item);
    }

    protected override void OnListChanged(ListChangedEventArgs e)
    {
        //we only care when an item of the collection has its property changed
        if (e.ListChangedType == ListChangedType.ItemChanged)
        {
            T obj = this[e.NewIndex];
            if (e.PropertyDescriptor != null && 
                      _indexedProperties.ContainsKey(e.PropertyDescriptor.Name))
                SetHash(obj,e.PropertyDescriptor.Name, 
                         GetPropertyValue(obj,e.PropertyDescriptor.Name));
        }
        base.OnListChanged(e);

    }

    /// <summary>
    /// Removes all hashes - used when an object is removed from the collection
    /// </summary>
    /// <param name="obj"></param>
    private void RemoveAllHases(T obj)
    {
        foreach (HashSet<T> set in _currentPropertyHashes[obj].Values)

            set.Remove(obj);

        _currentPropertyHashes.Remove(obj);
    }

    /// <summary>
    /// Sets all hashes - used when an object is first added to the collection
    /// </summary>
    /// <param name="obj"></param>
    private void SetAllHashes(T obj)
    {
        foreach (string prop in _indexedProperties.Keys)
            SetHash(obj, prop, GetPropertyValue(obj, prop));
    }

    private object GetPropertyValue(T obj, string propertyName)
    {
        return obj.GetType().GetProperty(propertyName).GetValue(obj, null);
    }

    private void SetHash(T obj, string propertyName, object value)
    {
        RemoveHashFromHistory(obj, propertyName);
        Dictionary<object, HashSet<T>> dict = 
              GetDictionaryForProperty(propertyName);

        value = value ?? _indexedProperties[propertyName];
        HashSet<T> set = GetHashSetFromDictionary(dict, value);
        StoreHashToHistory(obj, propertyName, set);
        set.Add((T)obj);
    }

    private void StoreHashToHistory(T obj, string propertyName, HashSet<T> hash)
    {
        Dictionary<string, HashSet<T>> dict;

        if (!_currentPropertyHashes.TryGetValue(obj, out dict))
        {
            dict = new Dictionary<string, HashSet<T>>();
            _currentPropertyHashes[obj] = dict;
        }
        dict[propertyName] = hash;
    }

    private void RemoveHashFromHistory(T obj, string propertyName)
    {
        HashSet<T> previousSet = GetPreviousHash(obj, propertyName);

        if (previousSet != null)
            previousSet.Remove(obj);
    }

    private HashSet<T> GetPreviousHash(T obj, string propertyName)
    {
        HashSet<T> set = null;
        Dictionary<string, HashSet<T>> dict;

        if (!_currentPropertyHashes.TryGetValue(obj, out dict))
        {
            dict = new Dictionary<string, HashSet<T>>();
            _currentPropertyHashes[obj] = dict;

            if (!dict.TryGetValue(propertyName, out set))
            {
                set = new HashSet<T>();
                dict[propertyName] = set;
            }
        }
        else
        {
            if (!dict.TryGetValue(propertyName, out set))
            {
                set = new HashSet<T>();
                dict[propertyName] = set;
            }
        }

        return set;
    }

    protected HashSet<T> GetHashSetFromDictionary(Dictionary<object, 
                HashSet<T>> dict, object value)
    {
        HashSet<T> set;

        if (!dict.TryGetValue(value, out set))
        {
            set = new HashSet<T>();
            dict[value] = set;
        }
        return set;
    }

    private Dictionary<object, HashSet<T>> GetDictionaryForProperty(string property)
    {
        Dictionary<object, HashSet<T>> dict = null;
        IDictionary temp;

        if (!_propertyHashes.TryGetValue(property, out temp))
        {
            dict = new Dictionary<object, HashSet<T>>();
            _propertyHashes[property] = dict;

            return dict;
        }
        else
        {
            return temp as Dictionary<object, HashSet<T>>;
        }
    }

    protected override void InsertItem(int index, T obj)
    {
        SetAllHashes(obj);
        base.InsertItem(index, obj);
    }

    public virtual HashSet<T> Find(string propertyName, object value)
    {
        if (!_indexedProperties.ContainsKey(propertyName))
            throw new Exception("You can only search on indexed properties");

        return GetHashSetFromDictionary(GetDictionaryForProperty(propertyName), value);
    }

    protected override void RemoveItem(int index)

    {
        RemoveAllHases(this[index]);

        base.RemoveItem(index);
    }

}
         
[AttributeUsage(AttributeTargets.Property, AllowMultiple = false)]
public class IndexedProperty : System.Attribute
{
    private object _nullValue;
    public object NullValue
    {
        get
        {
            return _nullValue;

        }
    }
    public IndexedProperty()
    {

    }
    public IndexedProperty(object nullValue)
    {
        if (nullValue == null)
            throw new Exception("The nullValue must be non-null");

        _nullValue = nullValue;
    }
}