幾種C#框架提供的數據結構對單值查找的效率比較(2)

結論

對以字符串為主鍵的單值查找的優先選擇 Hashtable 或者 Dictionary. 個人覺得如果只注重效率的話， Hashtable 更好一些，特別是在字符串較長時其效率幾乎比Dictionary 快將近一倍。

測試代碼

using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using System.Diagnostics;

namespace StringDictionaryPerformance
{
　　class Program
　　{
　　　　static Random _Rand = new Random();

　　　　static Hashtable _Hashtable;
　　　　static Dictionary<string, int> _Dictionary;
　　　　static SortedDictionary<string, int> _SortDictionary ;
　　　　static SortedList<string, int> _SortedList ;

　　　　static string GetRandString(int length)
　　　　{
　　　　　　StringBuilder str = new StringBuilder();

　　　　　　for (int i = 0; i < length; i++)
　　　　　　{
　　　　　　　　str.Append((char)_Rand.Next(32, 128));
　　　　　　}

　　　　　　return str.ToString();
　　　　}

　　　　static List<string> GetTestStrings(int length, int number)
　　　　{
　　　　　　List<string> retVal = new List<string>(number);

　　　　　　for (int i = 0; i < number; i++)
　　　　　　{
　　　　　　　　retVal.Add(GetRandString(length));
　　　　　　}

　　　　　　return retVal;
　　　　}

　　　　static void TestInsert(List<string> strings, bool sort)
　　　　{
　　　　　　if (sort)
　　　　　　{
　　　　　　　　strings.Sort();
　　　　　　}

　　　　　　Console.WriteLine(string.Format("TestInsert string length = {0} count of strings = {1} sort={2}",
　　　　　　　　strings[0].Length, strings.Count, sort));

　　　　　　Stopwatch stopWatch = new Stopwatch();

　　　　　　Console.WriteLine("Begin Hashtable");

　　　　　　_Hashtable = new Hashtable(strings.Count);
　　　　　　stopWatch.Reset();
　　　　　　stopWatch.Start();

　　　　　　for (int i = 0; i < strings.Count; i++)
　　　　　　{
　　　　　　　　if (_Hashtable[strings[i]] != null)
　　　　　　　　{
　　　　　　　　　　_Hashtable.Add(strings[i], i);
　　　　　　　　}
　　　　　　}

　　　　　　stopWatch.Stop();
　　　　　　Console.WriteLine(string.Format("ElapsedMilliseconds = {0} ms", stopWatch.ElapsedMilliseconds));

　　　　　　Console.WriteLine("Begin Dictoinary");

　　　　　　_Dictionary = new Dictionary<string,int>(strings.Count);
　　　　　　stopWatch.Reset();
　　　　　　stopWatch.Start();

　　　　　　for (int i = 0; i < strings.Count; i++)
　　　　　　{
　　　　　　　　if (!_Dictionary.ContainsKey(strings[i]))
　　　　　　　　{
　　　　　　　　　　_Dictionary.Add(strings[i], i);
　　　　　　　　}
　　　　　　}

　　　　　　stopWatch.Stop();

　　　　　　Console.WriteLine(string.Format("ElapsedMilliseconds = {0} ms", stopWatch.ElapsedMilliseconds));

　　　　　　Console.WriteLine("Begin SortDictionary");

　　　　　　_SortDictionary = new SortedDictionary<string, int>();
　　　　　　stopWatch.Reset();
　　　　　　stopWatch.Start();

　　　　　　for (int i = 0; i < strings.Count; i++)
　　　　　　{
　　　　　　　　if (!_SortDictionary.ContainsKey(strings[i]))
　　　　　　　　{
　　　　　　　　　　_SortDictionary.Add(strings[i], i);
　　　　　　　　}
　　　　　　}

　　　　　　stopWatch.Stop();

　　　　　　Console.WriteLine(string.Format("ElapsedMilliseconds = {0} ms", stopWatch.ElapsedMilliseconds));

　　　　　　Console.WriteLine("Begin SortedList");

　　　　　　_SortedList = new SortedList<string, int>(strings.Count);
　　　　　　stopWatch.Reset();
　　　　　　stopWatch.Start();

　　　　　　for (int i = 0; i < strings.Count; i++)
　　　　　　{
　　　　　　　　if (!_SortedList.ContainsKey(strings[i]))
　　　　　　　　{
　　　　　　　　　　_SortedList.Add(strings[i], i);
　　　　　　　　}
　　　　　　}

　　　　　　stopWatch.Stop();

　　　　　　Console.WriteLine(string.Format("ElapsedMilliseconds = {0} ms", stopWatch.ElapsedMilliseconds));

　　　　}

　　　　static void TestFind(List<string> strings, bool sort)
　　　　{
　　　　　　Console.WriteLine(string.Format("TestFind string length = {0} count of strings = {1} sort={2}",
　　　　　　　　strings[0].Length, strings.Count, sort));

　　　　　　Stopwatch stopWatch = new Stopwatch();

　　　　　　Console.WriteLine("Begin Hashtable");

　　　　　　_Hashtable = new Hashtable(strings.Count);
　　　　　　stopWatch.Reset();
　　　　　　stopWatch.Start();

　　　　　　for (int i = 0; i < strings.Count; i++)
　　　　　　{
　　　　　　　　if (_Hashtable[strings[i]] != null)
　　　　　　　　{
　　　　　　　　　　Console.WriteLine("Error!");
　　　　　　　　}
　　　　　　}

　　　　　　stopWatch.Stop();
　　　　　　Console.WriteLine(string.Format("ElapsedMilliseconds = {0} ms", stopWatch.ElapsedMilliseconds));

　　　　　　Console.WriteLine("Begin Dictoinary");

　　　　　　stopWatch.Reset();
　　　　　　stopWatch.Start();

　　　　　　for (int i = 0; i < strings.Count; i++)
　　　　　　{
　　　　　　　　if (!_Dictionary.ContainsKey(strings[i]))
　　　　　　　　{
　　　　　　　　　　Console.WriteLine("Error!");
　　　　　　　　}
　　　　　　}

　　　　　　stopWatch.Stop();

　　　　　　Console.WriteLine(string.Format("ElapsedMilliseconds = {0} ms", stopWatch.ElapsedMilliseconds));

　　　　　　Console.WriteLine("Begin SortDictionary");

　　　　　　stopWatch.Reset();
　　　　　　stopWatch.Start();

　　　　　　for (int i = 0; i < strings.Count; i++)
　　　　　　{
　　　　　　　　if (!_SortDictionary.ContainsKey(strings[i]))
　　　　　　　　{
　　　　　　　　　　Console.WriteLine("Error!");
　　　　　　　　}

　　　　　　}

　　　　　　stopWatch.Stop();

　　　　　　Console.WriteLine(string.Format("ElapsedMilliseconds = {0} ms", stopWatch.ElapsedMilliseconds));

　　　　　　Console.WriteLine("Begin SortedList");

　　　　　　stopWatch.Reset();
　　　　　　stopWatch.Start();

　　　　　　for (int i = 0; i < strings.Count; i++)
　　　　　　{
　　　　　　　　if (!_SortedList.ContainsKey(strings[i]))
　　　　　　　　{
　　　　　　　　　　Console.WriteLine("Error!");
　　　　　　　　}
　　　　　　}

　　　　　　stopWatch.Stop();

　　　　　　Console.WriteLine(string.Format("ElapsedMilliseconds = {0} ms", stopWatch.ElapsedMilliseconds));

　　　　}

　　　　static void Main(string[] args)
　　　　{
　　　　　　List<string> strings;

　　　　　　strings = GetTestStrings(16, 100000);
　　　　　　TestInsert(strings, false);
　　　　　　TestFind(strings, false);
　　　　　　TestInsert(strings, true);
　　　　　　TestFind(strings, true);

　　　　　　strings = GetTestStrings(128, 100000);
　　　　　　TestInsert(strings, false);
　　　　　　TestFind(strings, false);
　　　　　　TestInsert(strings, true);
　　　　　　TestFind(strings, true);

　　　　　　strings = GetTestStrings(1024, 100000);
　　　　　　TestInsert(strings, false);
　　　　　　TestFind(strings, false);
　　　　　　TestInsert(strings, true);
　　　　　　TestFind(strings, true);

　　　　}
　　}
}