在 C# 中过滤字典及其值的最快方法 "simplify"

Question

在 C# 中，给定一个 SortedDictionary，我需要过滤它的键，然后 "simplify" 它的值。下面的 MWE 对此进行了最好的解释，它完全符合我的要求

static void Main()
{
    var lowerBound = new DateTime(2018, 01, 02);
    var upperBound = new DateTime(2018, 01, 04);

    var myInput = new SortedDictionary<DateTime, SimpleItem>();

    myInput.Add(new DateTime(2018, 01, 01), new SimpleItem { item1 = 1.1, item2 = 2.1 });
    myInput.Add(new DateTime(2018, 01, 02), new SimpleItem { item1 = 1.2, item2 = 2.2 });
    myInput.Add(new DateTime(2018, 01, 03), new SimpleItem { item1 = 1.3, item2 = 2.3 });
    myInput.Add(new DateTime(2018, 01, 04), new SimpleItem { item1 = 1.4, item2 = 2.4 });
    myInput.Add(new DateTime(2018, 01, 05), new SimpleItem { item1 = 1.5, item2 = 2.5 });
    myInput.Add(new DateTime(2018, 01, 06), new SimpleItem { item1 = 1.6, item2 = 2.6 });
    myInput.Add(new DateTime(2018, 01, 07), new SimpleItem { item1 = 1.7, item2 = 2.7 });

    var q = myInput.Where(x => x.Key >= lowerBound && x.Key <= upperBound);

    Dictionary<DateTime, double> d = 
                  q.ToDictionary(x => x.Key, x => x.Value.item1);

    SortedDictionary<DateTime, double> myOutput = 
                  new SortedDictionary<DateTime, double>(d);

    int wait = 0;
}

class SimpleItem
{
    public double item1 { get; set; }
    public double item2 { get; set; }
}

通过分析我的实际代码（不是这个 MWE），很明显 ToDictionary 是非常慢（所有其他部分似乎没问题）。所以我只是要求另一种方法（希望是最快的）来做同样的事情。

Answer 1

SortedDictionary 构造函数简单地迭代输入字典的 KeyValuePair 对象并调用 .Add():

public SortedDictionary(IDictionary<TKey,TValue> dictionary, IComparer<TKey> comparer) {
    if( dictionary == null) {
        ThrowHelper.ThrowArgumentNullException(ExceptionArgument.dictionary);
    }

    _set = new TreeSet<KeyValuePair<TKey, TValue>>(new KeyValuePairComparer(comparer));

    foreach(KeyValuePair<TKey, TValue> pair in dictionary) {
        _set.Add(pair);
    }            
}

这意味着您不会通过创建中间词典获得任何收益。您可以编写一个查询来过滤和 select 您想要的值，并通过 ICollection.Add 方法将它们添加到字典中：

var q = myInput.Where(x => x.Key >= lowerBound && x.Key <= upperBound)
               .Select(x=>new KeyValuePair<DateTime,double>(x.Key,x.Value.item1));

var myOutput = new SortedDictionary<DateTime, double>();    
var coll=(ICollection<KeyValuePair<DateTime,double>>)myOutput;

foreach(var pair in q)
{
  coll.Add(pair);
}

SortedDictionary 对于编写或枚举来说不是线程安全的，这意味着您不能使用 PLINQ 来加速过滤源字典或创建新字典。

Answer 2

您的问题是您对 SortedDictionary 的过滤没有利用它已排序的事实。由于 ICollection（和一般的 C# 泛型集合）不实现任何类型的有效拼接操作，查找是您最好的选择。

翻转你的过滤器，你得到：

var q = Enumerable.Range(0, (Int32)(upperBound - lowerBound).TotalDays+1).Select(n => new { Key = lowerBound.AddDays(n), Item = myInput[lowerBound.AddDays(n)].item1 });

var myOutput = new SortedDictionary<DateTime, double>();

foreach (var pair in q)
    myOutput.Add(pair.Key, pair.Item);

其他方法的平均时间都差不多。在 lowerBound 和 upperBound 中使用非常小的间隔可使性能提高数千倍。当 myInput 包含 200 万个条目时，即使使用两年跨度也会导致性能提高数百倍。

请注意，加速的范围实际上取决于 SortedList 中有多少条目，较小的列表不会显示出太大的性能差异。

在 C# 中过滤字典及其值的最快方法 "simplify"

Fastest way to filter a dictionary and "simplify" its values in C#

c#

linq

dictionary

sorteddictionary