慢字典与自定义类键

本文关键字：自定义 字典 | 更新日期: 2023-09-27 17:53:09

我有一个自定义类，我试图将其用作字典的键:

// I tried setting more than enough capacity also...
var dict = new Dictionary<MyPoint, MyPoint>(capacity);

现在让我澄清一下，这里的目标是比较两个相似但不同的列表，使用X, Y和Date作为复合键。这两个列表的值会有所不同，我正试图快速比较它们并计算它们的差异。

下面是类代码: 
public class MyPoint : IEquatable<MyPoint>
{
    public short X { get; set; }
    public short Y { get; set; }
    public DateTime Date { get; set; }
    public double MyValue { get; set; }
    public override bool Equals(object obj)
    {
        return base.Equals(obj as MyPoint);
    }
    public bool Equals(MyPoint other)
    {
        if (other == null)
        {
            return false;
        }
        return (Date == other.Date)
            && (X == other.X)
            && (Y == other.Y);
    }
    public override int GetHashCode()
    {
        return Date.GetHashCode()
             | X.GetHashCode()
             | Y.GetHashCode();
    }
}

我还尝试了一个结构键:

public struct MyPointKey
{
    public short X;
    public short Y;
    public DateTime Date;
    // The value is not on these, because the struct is only used as key
}

在这两种情况下，写字典都非常非常慢(读起来很快)。

我将键改为字符串，格式为:

var dict = new Dictionary<string, MyPoint>(capacity);
var key = string.Format("{0}_{1}", item.X, item.Y);

我很惊讶这是多么快——它至少快了10倍。我尝试了发布模式，没有调试器，以及我能想到的所有场景。

这个字典将包含350,000个或更多的条目，因此性能很重要。

有什么想法或建议吗?谢谢!

另一个编辑…

我正试图以最快的方式比较两个列表。这就是我的工作。Dictionary对于快速查找源列表非常重要。

IList<MyThing> sourceList;
IDictionary<MyThing, MyThing> comparisonDict;
Parallel.ForEach(sourceList,
    sourceItem =>
    {
        double compareValue = 0;
        MyThing compareMatch = null;
        if (comparisonDict.TryGetValue(sourceItem, out compareMatch))
        {
            compareValue = compareMatch.MyValue;
        }
        // Do a delta check on the item
        double difference = sourceItem.MyValue- compareValue;
        if (Math.Abs(difference) > 1)
        {
            // Record the difference...
        }
    });

慢字典与自定义类键

正如其他人在评论中所说，问题在于您的GetHashCode()实现。使用您的代码，并使用string key运行10,000,000次迭代，耗时11-12秒。使用现有的hashCode运行，我在一分钟后停止了它。使用下面的hashCode实现不到5秒。

public override int GetHashCode()
{
    var hashCode = Date.GetHashCode();
    hashCode = (hashCode * 37) ^ X.GetHashCode();
    hashCode = (hashCode * 37) ^ Y.GetHashCode();
    return hashCode;
}

问题是，当你进入大数字时，由于OR s，项目都在相同的桶中碰撞。

所有内容都在同一桶中的字典只是一个列表。

如果我没猜错的话，您喜欢在使用集合的同时仍然保持键的顺序。在这种情况下，用SortedSet`1代替。

代码:

class Program {
    static void Main(string[] args) {
        SortedSet<MyKey> list = new SortedSet<MyKey>() {
             new MyKey(0, 0, new DateTime(2015, 6, 4)),
            new MyKey(0, 1, new DateTime(2015, 6, 3)),
            new MyKey(1, 1, new DateTime(2015, 6, 3)),
            new MyKey(0, 0, new DateTime(2015, 6, 3)),
            new MyKey(1, 0, new DateTime(2015, 6, 3)),
        };
        foreach(var entry in list) {
            Console.WriteLine(string.Join(", ", entry.X, entry.Y, entry.Date));
        }
        Console.ReadKey();
    }
}

我改变了你的MyPoint类如下:

public sealed class MyKey : IEquatable<MyKey>, IComparable<MyKey> {
    public readonly short X;
    public readonly short Y;
    public readonly DateTime Date;
    public MyKey(short x, short y, DateTime date) {
        this.X = x;
        this.Y = y;
        this.Date = date;
    }
    public override bool Equals(object that) {
        return this.Equals(that as MyKey);
    }
    public bool Equals(MyKey that) {
        if(that == null) {
            return false;
        }
        return this.Date == that.Date
            && this.X == that.X
            && this.Y == that.Y;
    }
    public static bool operator ==(MyKey lhs, MyKey rhs) {
        return lhs != null ? lhs.Equals(rhs) : rhs == null;
    }
    public static bool operator !=(MyKey lhs, MyKey rhs) {
        return lhs != null ? !lhs.Equals(rhs) : rhs != null;
    }
    public override int GetHashCode() {
        int result;
        unchecked {
            result = (int)X;
            result = 31 * result + (int)Y;
            result = 31 * result + Date.GetHashCode();
        }
        return result;
    }
    public int CompareTo(MyKey that) {
        int result = this.X.CompareTo(that.X);
        if(result != 0) {
            return result;
        }
        result = this.Y.CompareTo(that.Y);
        if(result != 0) {
            return result;
        }
        result = this.Date.CompareTo(that.Date);
        return result;
    }
}
输出:

0, 0, 03.06.2015 00:00:00
0, 0, 04.06.2015 00:00:00
0, 1, 03.06.2015 00:00:00
1, 0, 03.06.2015 00:00:00
1, 1, 03.06.2015 00:00:00
相关文章：