手工制作的字典怎么可能比 .Net 字典快得多？

Question

回顾一个开源项目，我发现了一种有趣的数据结构：

// Represents a layer of "something" that covers the map
public class CellLayer<T> : IEnumerable<T>
{
    public readonly Size Size;
    public readonly TileShape Shape;
    public event Action<CPos> CellEntryChanged = null;

    readonly T[] entries;

    public CellLayer(Map map)
        : this(map.TileShape, new Size(map.MapSize.X, map.MapSize.Y)) { }

    public CellLayer(TileShape shape, Size size)
    {
        Size = size;
        Shape = shape;
        entries = new T[size.Width * size.Height];
    }

    public void CopyValuesFrom(CellLayer<T> anotherLayer)
    {
        if (Size != anotherLayer.Size || Shape != anotherLayer.Shape)
            throw new ArgumentException(
                "layers must have a matching size and shape.", "anotherLayer");
        if (CellEntryChanged != null)
            throw new InvalidOperationException(
                "Cannot copy values when there are listeners attached to the CellEntryChanged event.");
        Array.Copy(anotherLayer.entries, entries, entries.Length);
    }

    // Resolve an array index from cell coordinates
    int Index(CPos cell)
    {
        return Index(cell.ToMPos(Shape));
    }

    // Resolve an array index from map coordinates
    int Index(MPos uv)
    {
        return uv.V * Size.Width + uv.U;
    }

    /// <summary>Gets or sets the <see cref="OpenRA.CellLayer"/> using cell coordinates</summary>
    public T this[CPos cell]
    {
        get
        {
            return entries[Index(cell)];
        }

        set
        {
            entries[Index(cell)] = value;

            if (CellEntryChanged != null)
                CellEntryChanged(cell);
        }
    }

    /// <summary>Gets or sets the layer contents using raw map coordinates (not CPos!)</summary>
    public T this[MPos uv]
    {
        get
        {
            return entries[Index(uv)];
        }

        set
        {
            entries[Index(uv)] = value;

            if (CellEntryChanged != null)
                CellEntryChanged(uv.ToCPos(Shape));
        }
    }

    /// <summary>Clears the layer contents with a known value</summary>
    public void Clear(T clearValue)
    {
        for (var i = 0; i < entries.Length; i++)
            entries[i] = clearValue;
    }

    public IEnumerator<T> GetEnumerator()
    {
        return (IEnumerator<T>)entries.GetEnumerator();
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
}

此结构表示类型 T 的矩阵，因为给定 CPos（X，Y）结构，它 returns 该位置的 T 元素。这是一个示例用法：

var dic = new CellLayer<CellInfo>(TileShape.Rectangle, new Size(1280,1280));
cellLayer[new CPos(0, 1)] = new CellInfo(0, new CPos(0, 1), false);

在内部，CellLayer class 将给定的 CPos 转换为一个 int，作为内部数组的索引。

从客户端的角度来看 class 的运作方式，我觉得它像一个字典，所以我替换了实现。经过几次运行时测试和微基准测试，事实证明使用字典比使用手工制作的 CellLayer class 慢几十倍。这让我很吃惊。以下是我所做的测试：

    [Test]
    public void DictionaryTest()
    {
        var dic = new Dictionary<CPos, CellInfo>(1280 * 1280);

        var watch = Stopwatch.StartNew();

        for (int i = 0; i < 1280; i++)
            for (int u = 0; u < 1280; u++)
                dic[new CPos(i, u)] = new CellInfo(0, new CPos(i, u), false);

        Console.WriteLine(watch.ElapsedTicks);
    }

    [Test]
    public void CellLayerTest()
    {
        var dic = new CellLayer<CellInfo>(TileShape.Rectangle, new Size(1280,1280));

        var watch = Stopwatch.StartNew();

        for (int i = 0; i < 1280; i++)
            for (int u = 0; u < 1280; u++)
                dic[new CPos(i, u)] = new CellInfo(0, new CPos(i, u), false);

        Console.WriteLine(watch.ElapsedTicks);
    }

我认为 .NET 集合已尽可能优化。任何人都可以向我解释为什么使用字典比使用 "custom Dictionary" 慢吗？

谢谢

Answer 1

字典维护着一组 search/retrievable 项（通过散列-table、二叉树或类似的东西）。所以每个 Add() 和每个 [key] 都意味着一些 search（这往往是相对 "slow"）。

在您的情况下，如果存在从 CPos 到整数（也称为数组索引）的简单映射，则不会进行搜索，而是直接（快速）访问数组的单元格。

或者，更简单地说：本质上是将散列 table/binary 树与平面数组进行比较。

编辑

当然，这两个集合都相当快并且复杂度为 O(1)。然而，在散列中查找 table 比数组索引操作更复杂。

Answer 2

对于原始版本，您使用此公式找到条目的位置

uv.V * Size.Width + uv.U

在字典中查找位置

计算 CPos 的哈希码。
使用模运算在字典中查找桶hashcode % dictionarySize
如果桶不为空，请将您拥有的 CPos 与该桶中的 CPos 进行比较。如果它们不匹配，您就会遇到二次哈希码冲突。移至下一个存储桶并重试步骤 3。

如果你的主字典有代码冲突，也就是说很多不同的 CPos 值有相同的哈希码，你的字典会慢得离谱。

如果您有唯一的哈希码，那么可能是模数运算导致了性能下降。但是您需要附加一个分析器（例如 Redgate ANTS）才能确定。

手工制作的字典怎么可能比 .Net 字典快得多？

How is it possible that a handMade dictionary is way faster than .Net dictionary?

c#

collections

dictionary