从字典创建一个排序和过滤列表

Question

我需要根据未排序的对象字典创建排序和过滤列表。

我尝试维护一个排序的字典，但事实证明这不切实际，因为这些对象包含不断由外部进程更新的属性。

当前的解决方案需要对字典进行两次完整的传递——首先是过滤，然后是排序。我觉得应该有一种方法可以将这些步骤结合起来，以避免对整个集合进行两次循环。

如果可能的话，我正在尝试将下面显示的第一遍和第二遍组合成对字典的一次迭代。

这里速度很重要，所以我怀疑我是否可以使用 Linq。

//SETUP//

//class stub
public class myObject{
    public int ID;
    public float sortAttribute;
    public bool filterAttribute;
}

//unsorted dictionary
Dictionary<int, myObject> myDictionary = new Dictionary<int, myObject>();

//sorting method
public int sortMethod(myObject o1, myObject o2)
{
    if (o1.sortAttribute < o2.sortAttribute)
    {
        return -1;
    } else {
        return 1;
    }
}    

//CURRENT PROCESS//

//create empty list
List<myObject> sortedList = new List<myObject>();

//first pass - populate list from dictionary - filtering on the way
foreach (KeyValuePair<int, myObject> entry in myDictionary){
    if (entry.Value.filterAttribute){
        sortedList.Add(entry.Value)
    }
}

//2nd pass - sort the populated list
sortedList.Sort(sortMethod);

Answer 1

由于您没有具体说明您的字典有多大，我将在此处列出 2 个答案和一个建议，一个用于您的字典大时，一个用于您的字典小（足够）时。

让我们从大词典开始。您可以通过多种方式实现这一点，但我会尝试使用 O(n log n) 方法而不是 O(n^2) ，因为您提到速度至关重要。当您创建过滤列表时，我会尝试创建一个有利的合并排序步骤。当您将每个过滤的两个元素添加到新列表时，都可以对它们进行排序。那么就可以跳过归并排序的第一步，直接开始对4个元素进行排序。然而，这几乎与您当前的实现一样快，因为您只跳过合并排序的一个步骤，您将不得不创建自己的合并排序版本，该版本不以 2 个元素开头。

对于小（足够）的字典，您可以使用更快的排序算法。您可以使用计数排序的一个版本来创建可以在 O(n) 中对字典进行排序的过滤器和排序算法。您将需要研究该算法的数据，以了解如何将数据拆分到不同的计数排序桶中，例如如果你所有的数字都在 0 和 1 之间，你可以创建 1000 个桶和 select 一个桶，方法是将浮点数乘以 1000。请注意，如果桶中有多个元素（如果你的数据分割得很好，这些可以非常快，因为不会有很多数字在同一个桶中。

就我个人而言，我建议尝试选项 2，看看它是否能为您带来足够好的性能提升，以及它是否不需要太多的存储桶。如果您需要太多的存储桶或性能不是您想要的，您之后可以随时执行选项 1。

Answer 2

这里你有一个基于排序字典的数据结构，它总是按 SortAttribute 然后按 Id 排序，无论数据是否在外部更改，因为它对数据的更改做出正确反应。

项的插入、修改和删除是 O(log(n))。

免责声明：它不是线程安全的

namespace SortedDataStructureApp
{
    public class ValueChangedEventArgs<T> : EventArgs
    {
        public T? PreviousValue { get; private set; }
        public T? CurrentValue { get; private set; }
        public ValueChangedEventArgs(T previousValue, T currentValue)
        {
            this.PreviousValue = previousValue;
            this.CurrentValue = currentValue;
        }
    }

    public class MyObject
    {
        public event EventHandler<ValueChangedEventArgs<int>>? IdChanged;
        public event EventHandler<ValueChangedEventArgs<float>>? SortAttributeChanged;
        public event EventHandler<ValueChangedEventArgs<bool>>? FilterAttributeChanged;

        private int _id;
        public int Id 
        {
            get
            {
                return _id;
            }
            set 
            {
                if (value == _id) return;
                var previousValue = _id;
                _id = value;
                IdChanged?.Invoke(this, new ValueChangedEventArgs<int>(previousValue, value));
            }
        }

        private float _sortAttribute;
        public float SortAttribute
        {
            get
            {
                return _sortAttribute;
            }
            set
            {
                if (value == _sortAttribute) return;
                var previousValue = _sortAttribute;
                _sortAttribute = value;
                SortAttributeChanged?.Invoke(this, new ValueChangedEventArgs<float>(previousValue, value));
            }
        }

        private bool _filterAttribute;

        public bool FilterAttribute
        {
            get
            {
                return _filterAttribute;
            }
            set
            {
                if (value == _filterAttribute) return;
                var previousValue = _filterAttribute;
                _filterAttribute = value;
                FilterAttributeChanged?.Invoke(this, new ValueChangedEventArgs<bool>(previousValue, value));
            }
        }
    }

    internal class SortedDataStructure
    {
        private Dictionary<int, MyObject> unsortedDictionary = new Dictionary<int, MyObject>();
        private SortedDictionary<float, SortedDictionary<int, MyObject>> sortedDictionary = new SortedDictionary<float, SortedDictionary<int, MyObject>>();
        private EventHandler<ValueChangedEventArgs<int>> idChangedHandler;
        private EventHandler<ValueChangedEventArgs<float>> sortAttributeChangedHandler;
        private EventHandler<ValueChangedEventArgs<bool>> filterAttributeChangedHandler;

        public SortedDataStructure() 
        {
            idChangedHandler = new EventHandler<ValueChangedEventArgs<int>>(IdChanged);
            sortAttributeChangedHandler = new EventHandler<ValueChangedEventArgs<float>>(SortAttributeChanged);
            filterAttributeChangedHandler = new EventHandler<ValueChangedEventArgs<bool>>(FilterAttributeChanged);

        }

        private void IdChanged(object? sender, ValueChangedEventArgs<int> e)
        {
            if (sender == null) throw new ArgumentNullException(nameof(sender));
            var obj = (MyObject)sender;
            Remove(e.PreviousValue);
            Add(obj);
        }

        private void SortAttributeChanged(object? sender, ValueChangedEventArgs<float> e)
        {
            if (sender == null) throw new ArgumentNullException(nameof(sender));
            var obj = (MyObject)sender;
            if (obj.FilterAttribute)
            {
                RemoveFromSortedDictionary(e.PreviousValue, obj.Id);
                AddToSortedDictionary(obj);
            }
        }

        private void FilterAttributeChanged(object? sender, ValueChangedEventArgs<bool> e)
        {
            if (sender == null) throw new ArgumentNullException(nameof(sender));
            var obj = (MyObject)sender;
            if (e.CurrentValue == true)
            {
                AddToSortedDictionary(obj);
            }
            else
            {
                RemoveFromSortedDictionary(obj.SortAttribute, obj.Id);
            }
        }

        public void Add(MyObject obj)
        {
            if (obj == null) throw new ArgumentNullException(nameof(obj));
            unsortedDictionary.Add(obj.Id, obj);
            if (obj.FilterAttribute)
            {
                AddToSortedDictionary(obj);
            }
            obj.FilterAttributeChanged += this.filterAttributeChangedHandler;
            obj.IdChanged += this.idChangedHandler;
            obj.SortAttributeChanged += this.sortAttributeChangedHandler;
        }

        private void RemoveFromSortedDictionary(float sortAttribute, int id)
        {
            if (sortedDictionary.TryGetValue(sortAttribute, out var subDictionary) == false)
            {
                throw new InvalidOperationException($"Sorted structure is corrupted. Could not find sortAttribute: {sortAttribute}");
            }
            if (subDictionary.Remove(id) == false)
            {
                throw new InvalidOperationException($"Sorted structure is corrupted. Could not find id {id} in subdictionary");
            }
        }

        private void AddToSortedDictionary(MyObject obj)
        {
            if (sortedDictionary.TryGetValue(obj.SortAttribute, out var subDictionary) == false)
            {
                subDictionary = new SortedDictionary<int, MyObject>();
                sortedDictionary.Add(obj.SortAttribute, subDictionary);
            }
            subDictionary.Add(obj.Id, obj);
        }

        public bool Remove(int id)
        {
            if (unsortedDictionary.Remove(id, out var obj) == false)
            {
                return false;
            }
            if (obj.FilterAttribute)
            {
                RemoveFromSortedDictionary(obj.SortAttribute, id);
            }
            obj.FilterAttributeChanged -= this.filterAttributeChangedHandler;
            obj.IdChanged -= this.idChangedHandler;
            obj.SortAttributeChanged -= this.sortAttributeChangedHandler;
            return true;
        }

        public IEnumerable<MyObject> GetSortedValues()
        {
            return this.sortedDictionary.Values.SelectMany(x => x.Values);
        }

        public MyObject GetById(int id)
        {
            return unsortedDictionary[id];
        }

        public bool ContainsKey(int id)
        {
            return unsortedDictionary.ContainsKey(id);
        }

        public bool TryGetValue(int id, out MyObject? obj)
        {
            return unsortedDictionary.TryGetValue(id, out obj);
        }
    }
}

显示其工作原理的代码：

using SortedDataStructureApp;

var obj1 = new MyObject
{
    Id = 1,
    SortAttribute = 1,
    FilterAttribute = true
};

var obj2 = new MyObject
{
    Id = 2,
    SortAttribute = 1,
    FilterAttribute = true
};

var data = new SortedDataStructure();
data.Add(obj1);
data.Add(obj2);


// It shows 1, 2. Both have the same sort attribute but Id = 1 comes before Id = 2
foreach (var obj in data.GetSortedValues())
{
    Console.WriteLine(obj.Id);
}


obj1.Id = 3;
Console.WriteLine();
// It shows 2, 3
foreach (var obj in data.GetSortedValues())
{
    Console.WriteLine(obj.Id);
}

obj1.SortAttribute = 0.5f;
Console.WriteLine();
// obj1.SortAttribute < obj2.SortAttribute, so it shows 3, 2
foreach (var obj in data.GetSortedValues())
{
    Console.WriteLine(obj.Id);
}

obj2.FilterAttribute = false;
Console.WriteLine();
// obj2 doesn't appear
foreach (var obj in data.GetSortedValues())
{
    Console.WriteLine(obj.Id);
}

obj2.FilterAttribute = true;
obj1.FilterAttribute = false;
// now only obj2 is shown
Console.WriteLine();
foreach (var obj in data.GetSortedValues())
{
    Console.WriteLine(obj.Id);
}

从字典创建一个排序和过滤列表

Create a sorted and filtered list from dictionary

c#

list

dictionary

optimization