C# 添加元素时字典性能不佳

Question

我有一大块数据，其中包含约 150 万个条目。每个条目都是这样的类的一个实例:

public class Element
{
    public Guid ID { get; set; }
    public string name { get; set; }
    public property p... p1... p2... 
}

我有一个 Guid 列表(约 400 万)，我需要根据 Element 类的实例列表获取名称。

我将元素对象存储在字典中，但填充数据大约需要 90 秒。向字典中添加项目时有什么方法可以提高性能吗？数据没有重复项，但我知道字典在添加新项目时会检查重复项。

如果有更好的结构，则结构不必是字典。我尝试将 Element 对象放入一个列表中，添加时效果更好(~9 秒)。但是当我需要寻找具有特定 Guid 的项目时，需要超过 10 分钟才能找到所有 400 万个元素。我尝试使用 List.Find() 并手动遍历列表。

此外，如果我不使用 System.Guid 而不是将它们全部转换为 String 并将它们的字符串表示形式存储在数据结构中，那么填充字典和填充另一个列表中的名称的整个操作只需要 10 秒，但是我的当我将它们存储为 System.Guid 时，应用程序消耗 1.2Gb 的 RAM，而不是 600mb。

关于如何更好地执行它有什么想法吗？

Answer 1

您的问题可能与“顺序”Guid 有关，例如:

c482fbe1-9f16-4ae9-a05c-383478ec9d11
c482fbe1-9f16-4ae9-a05c-383478ec9d12
c482fbe1-9f16-4ae9-a05c-383478ec9d13
c482fbe1-9f16-4ae9-a05c-383478ec9d14
c482fbe1-9f16-4ae9-a05c-383478ec9d15

Dictionary<,> 有一个问题，因为它们通常具有相同的 GetHashCode() ，所以它必须做一些技巧将搜索时间从 O(1) 更改为 O(n) ...您可以通过使用计算的自定义相等比较器来解决它以不同的方式散列，例如:

public class ReverseGuidEqualityComparer : IEqualityComparer<Guid>
{
    public static readonly ReverseGuidEqualityComparer Default = new ReverseGuidEqualityComparer();

    #region IEqualityComparer<Guid> Members

    public bool Equals(Guid x, Guid y)
    {
        return x.Equals(y);
    }

    public int GetHashCode(Guid obj)
    {
        var bytes = obj.ToByteArray();

        uint hash1 = (uint)bytes[0] | ((uint)bytes[1] << 8) | ((uint)bytes[2] << 16) | ((uint)bytes[3] << 24);
        uint hash2 = (uint)bytes[4] | ((uint)bytes[5] << 8) | ((uint)bytes[6] << 16) | ((uint)bytes[7] << 24);
        uint hash3 = (uint)bytes[8] | ((uint)bytes[9] << 8) | ((uint)bytes[10] << 16) | ((uint)bytes[11] << 24);
        uint hash4 = (uint)bytes[12] | ((uint)bytes[13] << 8) | ((uint)bytes[14] << 16) | ((uint)bytes[15] << 24);

        int hash = 37;

        unchecked
        {
            hash = hash * 23 + (int)hash1;
            hash = hash * 23 + (int)hash2;
            hash = hash * 23 + (int)hash3;
            hash = hash * 23 + (int)hash4;
        }

        return hash;
    }

    #endregion
}

然后你只需像这样声明字典:

var dict = new Dictionary<Guid, Element>(ReverseGuidEqualityComparer.Default);

一个小测试看看区别:

private static void Increment(byte[] x)
{
    for (int i = x.Length - 1; i >= 0; i--)
    {
        if (x[i] != 0xFF)
        {
            x[i]++;
            return;
        }

        x[i] = 0;
    }
}

和

// You can try timing this program with the default GetHashCode:
//var dict = new Dictionary<Guid, object>();
var dict = new Dictionary<Guid, object>(ReverseGuidEqualityComparer.Default);
var hs1 = new HashSet<int>();
var hs2 = new HashSet<int>();

{
    var guid = Guid.NewGuid();

    Stopwatch sw = Stopwatch.StartNew();

    for (int i = 0; i < 1500000; i++)
    {
        hs1.Add(ReverseGuidEqualityComparer.Default.GetHashCode(guid));
        hs2.Add(guid.GetHashCode());
        dict.Add(guid, new object());
        var bytes = guid.ToByteArray();
        Increment(bytes);
        guid = new Guid(bytes);
    }

    sw.Stop();

    Console.WriteLine("Milliseconds: {0}", sw.ElapsedMilliseconds);
}

Console.WriteLine("ReverseGuidEqualityComparer distinct hashes: {0}", hs1.Count);
Console.WriteLine("Guid.GetHashCode() distinct hashes: {0}", hs2.Count);

对于顺序 Guid，不同哈希码数量的差异是惊人的:

ReverseGuidEqualityComparer distinct hashes: 1500000
Guid.GetHashCode() distinct hashes: 256

现在...如果您不想使用 ToByteArray()(因为它分配了无用的内存)，有一个使用反射和表达式树的解决方案...它应该可以与 Mono 一起正常工作，因为 Mono“对齐”了它的在 2004 中将 Guid 实现到 Microsoft 之一，那是远古时代:-)

public class ReverseGuidEqualityComparer : IEqualityComparer<Guid>
{
    public static readonly ReverseGuidEqualityComparer Default = new ReverseGuidEqualityComparer();

    public static readonly Func<Guid, int> GetHashCodeFunc;

    static ReverseGuidEqualityComparer()
    {
        var par = Expression.Parameter(typeof(Guid));
        var hash = Expression.Variable(typeof(int));

        var const23 = Expression.Constant(23);

        var const8 = Expression.Constant(8);
        var const16 = Expression.Constant(16);
        var const24 = Expression.Constant(24);

        var b = Expression.Convert(Expression.Convert(Expression.Field(par, "_b"), typeof(ushort)), typeof(uint));
        var c = Expression.Convert(Expression.Convert(Expression.Field(par, "_c"), typeof(ushort)), typeof(uint));
        var d = Expression.Convert(Expression.Field(par, "_d"), typeof(uint));
        var e = Expression.Convert(Expression.Field(par, "_e"), typeof(uint));
        var f = Expression.Convert(Expression.Field(par, "_f"), typeof(uint));
        var g = Expression.Convert(Expression.Field(par, "_g"), typeof(uint));
        var h = Expression.Convert(Expression.Field(par, "_h"), typeof(uint));
        var i = Expression.Convert(Expression.Field(par, "_i"), typeof(uint));
        var j = Expression.Convert(Expression.Field(par, "_j"), typeof(uint));
        var k = Expression.Convert(Expression.Field(par, "_k"), typeof(uint));

        var sc = Expression.LeftShift(c, const16);
        var se = Expression.LeftShift(e, const8);
        var sf = Expression.LeftShift(f, const16);
        var sg = Expression.LeftShift(g, const24);
        var si = Expression.LeftShift(i, const8);
        var sj = Expression.LeftShift(j, const16);
        var sk = Expression.LeftShift(k, const24);

        var body = Expression.Block(new[]
        {
            hash
        },
        new Expression[]
        {
            Expression.Assign(hash, Expression.Constant(37)),
            Expression.MultiplyAssign(hash, const23),
            Expression.AddAssign(hash, Expression.Field(par, "_a")),
            Expression.MultiplyAssign(hash, const23),
            Expression.AddAssign(hash, Expression.Convert(Expression.Or(b, sc), typeof(int))),
            Expression.MultiplyAssign(hash, const23),
            Expression.AddAssign(hash, Expression.Convert(Expression.Or(d, Expression.Or(se, Expression.Or(sf, sg))), typeof(int))),
            Expression.MultiplyAssign(hash, const23),
            Expression.AddAssign(hash, Expression.Convert(Expression.Or(h, Expression.Or(si, Expression.Or(sj, sk))), typeof(int))),
            hash
        });

        GetHashCodeFunc = Expression.Lambda<Func<Guid, int>>(body, par).Compile();
    }

    #region IEqualityComparer<Guid> Members

    public bool Equals(Guid x, Guid y)
    {
        return x.Equals(y);
    }

    public int GetHashCode(Guid obj)
    {
        return GetHashCodeFunc(obj);
    }

    #endregion

    // For comparison purpose, not used
    public int GetHashCodeSimple(Guid obj)
    {
        var bytes = obj.ToByteArray();

        unchecked
        {
            int hash = 37;

            hash = hash * 23 + (int)((uint)bytes[0] | ((uint)bytes[1] << 8) | ((uint)bytes[2] << 16) | ((uint)bytes[3] << 24));
            hash = hash * 23 + (int)((uint)bytes[4] | ((uint)bytes[5] << 8) | ((uint)bytes[6] << 16) | ((uint)bytes[7] << 24));
            hash = hash * 23 + (int)((uint)bytes[8] | ((uint)bytes[9] << 8) | ((uint)bytes[10] << 16) | ((uint)bytes[11] << 24));
            hash = hash * 23 + (int)((uint)bytes[12] | ((uint)bytes[13] << 8) | ((uint)bytes[14] << 16) | ((uint)bytes[15] << 24));

            return hash;
        }
    }
}

其他解决方案，基于“未记录但有效”的编程(在 .NET 和 Mono 上测试):

public class ReverseGuidEqualityComparer : IEqualityComparer<Guid>
{
    public static readonly ReverseGuidEqualityComparer Default = new ReverseGuidEqualityComparer();

    #region IEqualityComparer<Guid> Members

    public bool Equals(Guid x, Guid y)
    {
        return x.Equals(y);
    }

    public int GetHashCode(Guid obj)
    {
        GuidToInt32 gtoi = new GuidToInt32 { Guid = obj };

        unchecked
        {
            int hash = 37;

            hash = hash * 23 + gtoi.Int32A;
            hash = hash * 23 + gtoi.Int32B;
            hash = hash * 23 + gtoi.Int32C;
            hash = hash * 23 + gtoi.Int32D;

            return hash;
        }
    }

    #endregion

    [StructLayout(LayoutKind.Explicit)]
    private struct GuidToInt32
    {
        [FieldOffset(0)]
        public Guid Guid;

        [FieldOffset(0)]
        public int Int32A;
        [FieldOffset(4)]
        public int Int32B;
        [FieldOffset(8)]
        public int Int32C;
        [FieldOffset(12)]
        public int Int32D;
    }
}

它使用 StructLayout “技巧”将 Guid 叠加到一堆 int ，写入 Guid 并读取 int 。

为什么 Guid.GetHashCode() 在顺序 ID 方面有问题？

很容易解释:从 reference source ， GetHashCode() 是:

return _a ^ (((int)_b << 16) | (int)(ushort)_c) ^ (((int)_f << 24) | _k);

所以 _d 、 _e 、 _g 、 _h 、 _i 、 _j byte 不是散列码的一部分。当递增时，Guid 首先在 _k 字段(256 个值)中递增，然后在 _j 字段(256 * 256 个值，所以 65536 个值)中溢出，然后在 _i 字段(16777216 个值)中递增。显然，通过不散列 _h 、 _i 、 _j 字段，顺序 Guid 的散列将只显示 256 个不同的值，用于非大范围的 Guid (或者最多 512 个不同的值，如果 _f 字段递增一次，就像你开始使用类似于 Guid 的 12345678-1234-1234-1234-aaffffffff00 ，其中 aa (即“我们的” _f )将在 ab 的 256 个增量之后增加到 Guid )