查询列表与ToDictionary()

Question

设想一种情况，您有一个相当大的列表，您需要搜索。何时将其转换为Dictionary，以及何时只查询列表？

我知道查询列表是O(n)操作，而查询字典(或查找/哈希集)是O(1)。但是，我完全不确定将任何O(n)集合转换为O(1)集合的效率。转换的效率不是O(n)本身吗？这是否意味着将列表转换为字典是完全没有意义的，除非您至少三次查询它？

当我们正在做的时候，当你决定一个特定的集合时，你的思考过程是什么？你认为什么是最好的做法？

(用我的手机写这个，不考虑语法)

public class BigData
{
  public int Id;
  public SubBigData SubBigData;
}

//elsewhere...
public SubBigData GetDataById(int id) 
{
  List<BigData> data = GetDataFromSomewhere();

  return data.Where(d => d.Id == id).Select(d => d.SubBigData).FirstOrDefault();
  //vs
  return data.ToDictionary(d => d.Id, d.SubBigData)[id];
}

Answer 1

，如果我能在得到结果之前过滤它，那将是理想的。因此，如果该GetDataFromSomewhere 是可查询的，则在那里查询您的数据.

摘要

我做了一个测试来显示实际结果：

On a collection of 1 000 000 records, get 1 000 records by ID

示例中的Linq表达式花了5.7秒时间。

一个简化的Linq表达式花了6.6几秒钟。

字典转换和检索花费了26秒时间。

有趣的是，如果您将整个集合转换为字典并将其用作您的新源，则需要2.7秒才能获得1000条记录。

因此，字典转换在这里更快。不过，我不确定这是否是一个足够的测试。

代码

using System.Diagnostics;

#region Create and populate collection
List<TestObject> listCollection = new();

for (int i = 0; i < 1000000; i++)
{
    listCollection.Add(new TestObject()
    {
        Id = i,
        Name = $"Name{i}"
    });
}
#endregion Create and populate collection

Stopwatch stopwatch = Stopwatch.StartNew();

Random random = new();

#region Get using Linq
for (int i = 0; i < 1000; i++)
{
    int id = random.Next(0, 2000000);
    _ = listCollection.Where(c => c.Id == id).Select(c => c.Name).FirstOrDefault();
}

Console.WriteLine($"Took {stopwatch.Elapsed} to get 1000 items from list"); //Took 00:00:05.7212037
#endregion Get using Linq

#region Get using Linq (Shorter Expression, takes longer to execute)
stopwatch.Restart();

for (int i = 0; i < 1000; i++)
{
    int id = random.Next(0, 2000000);
    _ = listCollection.FirstOrDefault(c => c.Id == id)?.Name;
}

Console.WriteLine($"Took {stopwatch.Elapsed} to get 1000 items from list"); //Took 00:00:06.6697507
#endregion Get using Linq (Shorter Expression, takes longer to execute)

#region Get using Dictionary
stopwatch.Restart();

for (int i = 0; i < 1000; i++)
{
    try
    {
        int id = random.Next(0, 2000000);
        _ = listCollection.ToDictionary(c => c.Id, c => c.Name)[id];
    }
    catch {
        //Ignore errors when trying to get a value from the Dictionary that does not have a matching key
    }
}
Console.WriteLine($"Took {stopwatch.Elapsed} to get 1000 items from dictionary"); //Took 00:00:26.0257818
#endregion Get using Dictionary

#region Get using cached Dictionary
stopwatch.Restart();

var cachedDictionary = listCollection.ToDictionary(c => c.Id, c => c.Name);
for (int i = 0; i < 1000; i++)
{
    try
    {
        int id = random.Next(0, 2000000);
        _ = cachedDictionary[id];
    }
    catch
    {
        //Ignore errors when trying to get a value from the Dictionary that does not have a matching key
    }
}

Console.WriteLine($"Took {stopwatch.Elapsed} to get 1000 items from cached dictionary"); //Took 00:00:02.7144331
#endregion Get using cached Dictionary

stopwatch.Stop();


public class TestObject
{
    public int Id { get; set; }
    public string Name { get; set; }
}