Created
June 16, 2014 15:44
-
-
Save GeeLaw/21c75a0982b1e59bb156 to your computer and use it in GitHub Desktop.
On Dictionary<TKey, TValue> in .NET
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
using System; | |
using System.Collections.Generic; | |
using System.Linq; | |
using System.Text; | |
using System.Threading.Tasks; | |
namespace TestDict | |
{ | |
struct SampleStructIS | |
{ | |
int i; | |
string s; | |
public SampleStructIS(int i_, string s_) { i = i_; s = s_; } | |
} | |
struct SampleStructSI | |
{ | |
string s; | |
int i; | |
public SampleStructSI(string s_, int i_) { s = s_; i = i_; } | |
} | |
struct SampleStructISEquatable : IEquatable<SampleStructISEquatable> | |
{ | |
int i; | |
string s; | |
public SampleStructISEquatable(int i_, string s_) { i = i_; s = s_; } | |
public bool Equals(SampleStructISEquatable other) { return i == other.i && s == other.s; } | |
} | |
struct SampleStructISCustomizedHashCode | |
{ | |
int i; | |
string s; | |
public SampleStructISCustomizedHashCode(int i_, string s_) { i = i_; s = s_; } | |
public override int GetHashCode() | |
{ | |
return i ^ s.GetHashCode(); | |
} | |
} | |
struct SampleStructISCHCIE : IEquatable<SampleStructISCHCIE> | |
{ | |
int i; | |
string s; | |
public SampleStructISCHCIE(int i_, string s_) { i = i_; s = s_; } | |
public override int GetHashCode() | |
{ | |
return i ^ s.GetHashCode(); | |
} | |
public bool Equals(SampleStructISCHCIE other) { return i == other.i && s == other.s; } | |
} | |
class Program | |
{ | |
static void Test<T>(Func<int, string, T> construct) | |
{ | |
DateTime dt = DateTime.UtcNow; | |
Dictionary<T, int> dict = new Dictionary<T, int>(); | |
for (int i = 0; i < (1 << 7); ++i) | |
for (int j = 0; j < (1 << 7); ++j) | |
dict[construct(i, j.ToString())] = i + j; | |
for (int i = 0; i < (1 << 7); ++i) | |
for (int j = 0; j < (1 << 7); ++j) | |
dict[construct((i ^ 12), (j ^ 21).ToString())] = i + j; | |
if (dict.Count == ((1 << 7) * (1 << 7))) | |
Console.WriteLine("{0}", DateTime.UtcNow - dt); | |
else | |
Console.WriteLine("Doesn't work."); | |
} | |
/* | |
* IS: 00:00:02.4531267 | |
* SI: 00:00:02.4522465 | |
* ISEquatable: 00:00:00.1406311 | |
* ISCustomizedHashCode: 00:00:00.1249934 | |
* ISCHCIE: 00:00:00.0312505 | |
* anonymous type: 00:00:00.0312516 | |
* 结论:直接使用虽然可以正常工作,但是性能损失较大,性能损失分为两方面: | |
* 1. GetHashCode 的自动实现不好,导致大量重复的 HashCode | |
* (实际上似乎 HashCode 只和第一个成员有关系?) | |
* 2. 由于没有实现 IEquatable<TKey> 而使用了 bool TKey.Equals(Object other) | |
* 装箱和拆箱(这个实现要检查类型和拆箱) | |
* | |
* 提供较好的 int TKey.GetHashCode() 并实现 IEquatable<TKey> 有助于改善性能。 | |
* 匿名类型(似乎是引用类型)从数据上看,帮我们实现了值语义的比较(包括实现 IEquatable<T>), | |
* 并提供了较好的 GetHashCode,这是因为匿名类型的对象是 immutable 的(和 string 一个道理)。 | |
*/ | |
static void Main(string[] args) | |
{ | |
Console.Write("IS:\t\t\t"); | |
Test((int i, string s) => new SampleStructIS(i, s)); | |
Console.Write("SI:\t\t\t"); | |
Test((int i, string s) => new SampleStructSI(s, i)); | |
Console.Write("ISEquatable:\t\t"); | |
Test((int i, string s) => new SampleStructISEquatable(i, s)); | |
Console.Write("ISCustomizedHashCode:\t"); | |
Test((int i, string s) => new SampleStructISCustomizedHashCode(i, s)); | |
Console.Write("ISCHCIE:\t\t"); | |
Test((int i, string s) => new SampleStructISCHCIE(i, s)); | |
Console.Write("anonymous type:\t\t"); | |
Test((int i, string s) => new { i, s }); | |
Console.ReadLine(); | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
显然匿名类型会慢,原生的引用类型无论是
GetHashCode
还是Equals
都是最快的。