从键列表中检索字典的所有元素的最有效方法？

Question

我有一个 c# Dictionary<DateTime,SomeObject> 实例。

我有以下代码：

private Dictionary<DateTime, SomeObject> _containedObjects = ...;//Let's imagine you have ~4000 items in it

public IEnumerable<SomeObject> GetItemsList(HashSet<DateTime> requiredTimestamps){
    //How to return the list of SomeObject contained in _containedObjects
    //Knowing that rarely(~<5% of the call), one or several DateTime of "requiredTimestamps" may not be in _containedObjects
}

我正在研究如何 return 一个 IEnumerable<SomeObject> 包含由提供的键之一引用的所有元素。唯一的问题是这个方法会被经常调用，我们可能不会总是在参数中包含每个给定的键。

那么有没有比这更高效的东西呢：

private Dictionary<DateTime, SomeObject> _containedObjects = ...;//Let's imagine you have ~4000 items in it

public IEnumerable<SomeObject> GetItemsList(HashSet<DateTime> requiredTimestamps){
    List<SomeObject> toReturn = new List<SomeObject>();
    foreach(DateTime dateTime in requiredTimestamps){
        SomeObject found;
        if(_containedObjects.TryGetValue(dateTime, out found)){
            toReturn.Add(found);
        }
    }
    return toReturn;
}

Answer 1

您可以使用 LINQ，但我怀疑它是否会提高任何性能，即使有任何差异也可以忽略不计。

您的方法可以是：

public IEnumerable<SomeObject> GetItemsList(HashSet<DateTime> requiredTimestamps)
{
    return _containedObjects.Where(r => requiredTimestamps.Contains(r.Key))
                            .Select(d => d.Value);
}

一个积极的方面是惰性评估，因为您没有填充列表并返回它。

Answer 2

一般来说，有两种方法可以做到这一点：

按顺序浏览 requiredTimestamps 并在字典中查找每个 date/time 邮票。字典查找是 O(1)，所以如果有 k 项要查找，则需要 O(k) 时间。
按顺序遍历字典，并在 requiredTimestamps 哈希集中提取具有匹配键的那些。这将花费 O(n) 时间，其中 n 是字典中的项目数。

理论上，第一种选择——也就是你目前所拥有的——将是最快的方法。

实际上，当您要查找的项目数少于字典中项目总数的某个百分比时，第一个方法可能会更有效。也就是说，如果您要在一百万个字典中查找 100 个键，第一个选项几乎肯定会更快。如果您要在一百万个字典中查找 500,000 个键，则第二种方法可能更快，因为移动到下一个键比查找要快得多。

您可能希望针对最常见的情况进行优化，我怀疑这种情况正在查找相对较小比例的键。在那种情况下，您描述的方法几乎肯定是最好的方法。但唯一确定的方法是测量。

您可能会考虑的一项优化是预先调整输出列表的大小。这将避免重新分配。因此，当您创建 toReturn 列表时：

List<SomeObject> toReturn = new List<SomeObject>(requiredTimestamps.Count);

Answer 3

这里有一些不同的方法 - 性能几乎相同，因此您可以根据可读性进行选择。

如果您想对其进行测试，请将其粘贴到 LinqPad 中 - 否则只需获取您需要的任何代码即可。

我认为从可读性的角度来看，我个人最喜欢的是方法 3。方法 4 当然是可读的，但有一个令人不快的特性，即它为每个所需的时间戳在字典中查找两次。

void Main()
{
    var obj = new TestClass<string>(i => string.Format("Element {0}", i));

    var sampleDateTimes = new HashSet<DateTime>();
    for(int i = 0; i < 4000 / 20; i++)
    {
        sampleDateTimes.Add(DateTime.Today.AddDays(i * -5));
    }
    var result = obj.GetItemsList_3(sampleDateTimes);
    foreach (var item in result)
    {
        Console.WriteLine(item);
    }
}

class TestClass<SomeObject>
{
    private Dictionary<DateTime, SomeObject> _containedObjects;

    public TestClass(Func<int, SomeObject> converter)
    {
        _containedObjects = new Dictionary<DateTime, SomeObject>();
        for(int i = 0; i < 4000; i++)
        {
            _containedObjects.Add(DateTime.Today.AddDays(-i), converter(i));
        }
    }

    public IEnumerable<SomeObject> GetItemsList_1(HashSet<DateTime> requiredTimestamps)
    {
        List<SomeObject> toReturn = new List<SomeObject>();
        foreach(DateTime dateTime in requiredTimestamps)
        {
            SomeObject found;
            if(_containedObjects.TryGetValue(dateTime, out found))
            {
                toReturn.Add(found);
            }
        }
        return toReturn;
    }

    public IEnumerable<SomeObject> GetItemsList_2(HashSet<DateTime> requiredTimestamps)
    {
        foreach(DateTime dateTime in requiredTimestamps)
        {
            SomeObject found;
            if(_containedObjects.TryGetValue(dateTime, out found))
            {
                yield return found;
            }
        }
    }    

    public IEnumerable<SomeObject> GetItemsList_3(HashSet<DateTime> requiredTimestamps)
    {
        return requiredTimestamps
            .Intersect(_containedObjects.Keys)
            .Select (k => _containedObjects[k]);
    }

    public IEnumerable<SomeObject> GetItemsList_4(HashSet<DateTime> requiredTimestamps)
    {
        return requiredTimestamps
            .Where(dt => _containedObjects.ContainsKey(dt))
            .Select (dt => _containedObjects[dt]);
    }
}

Answer 4

方法一： 要使这个显着更快-这不是通过更改算法而是通过在您的方法中制作_containedObjects的本地副本并引用本地副本进行查找。

示例：

public static IEnumerable<int> GetItemsList3(HashSet<DateTime> requiredTimestamps)
{
    var tmp = _containedObjects;

    List<int> toReturn = new List<int>();
    foreach (DateTime dateTime in requiredTimestamps)
    {
        int found;

        if (tmp.TryGetValue(dateTime, out found))
        {
            toReturn.Add(found);
        }
    }
    return toReturn;
}

测试数据和时间（在一组 5000 个项目上找到 125 个键）：
您的原始方法（毫秒）：2,06032186895335
方法一（毫秒）：0,53549626223609

方法二： 一种稍微加快速度的方法是遍历 较小的集合 并在较大的集合上进行查找。根据尺寸差异，您将获得一些速度。

您正在使用 Dictionary 和 HashSet，因此您对其中任何一个的查找都是 O(1)。

示例：如果 _containedObjects 的项目少于 requiredTimestamps，我们循环遍历 _containedObjects（否则使用您的方法进行相反的操作）

public static IEnumerable<int> GetItemsList2(HashSet<DateTime> requiredTimestamps)
{
    List<int> toReturn = new List<int>();
    foreach (var dateTime in _containedObjects)
    {
        int found;

        if (requiredTimestamps.Contains(dateTime.Key))
        {
            toReturn.Add(dateTime.Value);
        }
    }
    return toReturn;
}

测试数据和时间（在 _containedObjects 的 5000 集和 requiredTimestamps 的 10000 项集上找到 125 个键）：
您的原始方法（毫秒）：3,88056291367086
方法二（毫秒）：3,31025939438943

从键列表中检索字典的所有元素的最有效方法？

Most efficient way to retrieve all element of a Dictionary from a list of keys?

c#

algorithm

dictionary

processing-efficiency