13

如果我有 100 个项目将存储在字典中，我应该这样初始化它吗？

var myDictionary = new Dictionary<Key, Value>(100);

我的理解是 .NET 字典在达到给定负载时会在内部调整自身大小，并且负载阈值被定义为容量的比率。

这表明如果将 100 项添加到上述字典中，那么当添加其中一项时，它会自行调整大小。调整字典大小是我想避免的，因为它会影响性能并且浪费内存。

散列冲突的概率与字典中的加载成正比。因此，即使字典不调整自身大小（并使用其所有插槽），性能也会因这些冲突而降低。

假设您知道字典中有多少项，应该如何最好地决定将字典初始化到什么容量？

4

6 回答 6

6

改进的基准：

  • 硬件：Intel Core i7-10700K x64，.NET 5，优化构建。运行 .NET 5 的 LINQPad 6 和运行 .NET Fx 4.8 的 LINQPad 5。
  • 时间以毫秒为单位，保留 3 个小数位。
    • 0.001ms是 1 微秒。
    • 我不确定Stopwatch它的实际分辨率，因为它取决于系统，所以不要强调微秒级的差异。
  • 基准测试被重新运行了数十次，结果一致。显示的时间是所有运行的平均值。
  • 结论：通过在构造函数中进行设置，整体加速始终保持 10-20%capacityDictionary<String,String>。
。网： .NET 框架 4.8 .NET 5
初始容量为 1,000,000
构造函数 1.170ms 0.003ms
填写循环 353.420 毫秒 181.846 毫秒
总时间 354.590 毫秒 181.880 毫秒
无初始容量
构造函数 0.001ms 0.001ms
填写循环 400.158ms 228.687 毫秒
总时间 400.159 毫秒 228.688ms
从设置初始容量加速
时间 45.569 毫秒 46.8ms
加速 ％ 11% 20%
  • 10我确实对较小的初始大小（ 、100、1000、10000和）重复了基准测试，并且100000在这些大小上也观察到了 10-20% 的加速，但绝对而言，在需要几分之一毫秒的操作上加速了 20%
  • 虽然我看到了一致的结果（显示的数字是平均值），但有一些警告：
    • 这个基准测试是在 1,000,000 个项目的相当大的规模上执行的，但有紧密的循环（即循环体内没有太多其他事情发生），这不是一个现实的场景。因此，请始终对您自己的代码进行剖析和基准测试以确保知道，而不是相信您在 Internet 上找到的随机基准（就像这个）。
    • 基准测试不会隔离生成数百万个左右String实例所花费的时间（由i.ToString().
    • 引用类型String（值类型（例如 a ValueTuple）。还有其他类型大小的因素需要考虑。
    • 随着从 .NET Framework 4.8 到 .NET 5 的大幅改进，这意味着如果您在 .NET 6 或更高版本上运行，则不应相信这些数字。
      • 此外，不要假设较新的 .NET 版本会_总是）使事情变得更快：有时 .NET 更新和操作系统安全补丁的性能实际上会恶化。
// Warmup:
{
    var foo1 = new Dictionary<string, string>();
    var foo2 = new Dictionary<string, string>( capacity: 10_000 );
    foo1.Add( "foo", "bar" );
    foo2.Add( "foo", "bar" );
}


Stopwatch sw = Stopwatch.StartNew();

// Pre-set capacity:
TimeSpan pp_initTime;
TimeSpan pp_populateTime;
{
    var dict1 = new Dictionary<string, string>(1000000);

    pp_initTime = sw.GetElapsedAndRestart();

    for (int i = 0; i < 1000000; i++)
    {
        dict1.Add(i.ToString(), i.ToString());
    }
}
pp_populateTime = sw.GetElapsedAndRestart();

//
TimeSpan empty_initTime;
TimeSpan empty_populateTime;
{
    var dict2 = new Dictionary<string, string>();

    empty_initTime = sw.GetElapsedAndRestart();

    for (int i = 0; i < 1000000; i++)
    {
        dict2.Add(i.ToString(), i.ToString());
    }
}
empty_populateTime = sw.GetElapsedAndRestart();

//

Console.WriteLine("Pre-set capacity. Init time: {0:N3}ms, Fill time: {1:N3}ms, Total time: {2:N3}ms.", pp_initTime.TotalMilliseconds, pp_populateTime.TotalMilliseconds, ( pp_initTime + pp_populateTime ).TotalMilliseconds );
Console.WriteLine("Empty capacity. Init time: {0:N3}ms, Fill time: {1:N3}ms, Total time: {2:N3}ms.", empty_initTime.TotalMilliseconds, empty_populateTime.TotalMilliseconds, ( empty_initTime + empty_populateTime ).TotalMilliseconds );

// Extension methods:

[MethodImpl( MethodImplOptions.AggressiveInlining | MethodImplOptions.AggressiveOptimization )]
public static TimeSpan GetElapsedAndRestart( this Stopwatch stopwatch )
{
    TimeSpan elapsed = stopwatch.Elapsed;
    stopwatch.Restart();
    return elapsed;
}

原始基准：

原始基准，没有冷启动预热阶段和较低精度的DateTime时序：

  • 与容量 ( dict1) 的总时间是1220.778ms（建设和人口）。
  • 没有能力（dict2）总时间是1502.490ms（建设和人口）。
  • 因此，与不设置容量相比，容量节省了 320 毫秒（~20%）。
static void Main(string[] args)
{
    const int ONE_MILLION = 1000000;

    DateTime start1 = DateTime.Now;
    
    {
        var dict1 = new Dictionary<string, string>( capacity: ONE_MILLION  );

        for (int i = 0; i < ONE_MILLION; i++)
        {
            dict1.Add(i.ToString(), i.ToString());
        }
    }
        
    DateTime stop1 = DateTime.Now;
        
    DateTime start2 = DateTime.Now;

    {
        var dict2 = new Dictionary<string, string>();

        for (int i = 0; i < ONE_MILLION; i++)
        {
            dict2.Add(i.ToString(), i.ToString());
        }
    }
        
    DateTime stop2 = DateTime.Now;
        
    Console.WriteLine("Time with size initialized: " + (stop1.Subtract(start1)) + "\nTime without size initialized: " + (stop2.Subtract(start2)));
    Console.ReadLine();
}
于 2009-01-05T19:10:21.680 回答
6

您应该将字典容量初始化为什么取决于两个因素：(1) gethashcode 函数的分布，以及 (2) 您必须插入多少项。

您的哈希函数应该是随机分布的，或者应该为您的输入集专门制定。让我们假设第一个，但如果您对第二个感兴趣，请查找完美的哈希函数。

如果您有 100 个项目要插入到字典中，一个随机分布的哈希函数，并且您将容量设置为 100，那么当您将第 i 个项目插入到哈希表中时，您有 (i-1) / 100 的概率插入时项目将与另一个项目发生冲突。如果您想降低这种碰撞概率，请增加容量。将预期容量加倍会使碰撞的机会减半。

此外，如果您知道访问字典中每个项目的频率，您可能希望按频率递减的顺序插入这些项目，因为您首先插入的项目平均访问速度更快。

于 2009-09-04T01:08:55.237 回答
5

我认为你把事情复杂化了。如果您知道字典中有多少项目，那么一定要在构造时指定。这将有助于字典在其内部数据结构中分配必要的空间，以避免重新分配和重新洗牌数据。

于 2009-01-05T19:03:17.340 回答
2

为构造函数指定初始容量会Dictionary提高性能，因为在 ADD 操作期间存储字典值的内部结构的大小调整次数将减少。

考虑到您将 k 的初始容量指定给Dictionary构造函数，则：

  1. 将Dictionary保留存储 k 个元素所需的内存量；
  2. 对字典的查询性能不受影响，不会更快或更慢；
  3. ADD 操作不需要更多的内存分配（可能很昂贵），因此会更快。

来自MSDN：

Dictionary(TKey, TValue) 的容量是在需要调整大小之前可以添加到 Dictionary(TKey, TValue) 中的元素数。随着元素被添加到 Dictionary(TKey, TValue) 中，容量会根据需要通过重新分配内部数组来自动增加。

如果可以估计集合的大小，则指定初始容量消除了在向 Dictionary(TKey, TValue) 添加元素时执行许多调整大小操作的需要。

于 2009-01-05T19:09:04.910 回答
1

是的，与HashTable使用重新散列作为解决冲突的方法相反，Dictionary将使用链接。所以是的，使用计数很好。对于HashTable您可能想要使用的count * (1/fillfactor)

于 2009-01-05T19:08:14.350 回答
-1

初始大小只是一个建议。例如，大多数哈希表喜欢具有素数或 2 的幂的大小。

于 2009-01-05T19:10:42.910 回答