私たちのアプリケーションは、頻繁に変更されないマルチレベルのルックアップを持つ多くの辞書を使用しています。ディクショナリを使用して多くのルックアップを行う重要なコードの一部を、より高速なルックアップ、メモリ/gc の軽量化のために代替構造を使用するように変換することを調査しています。これにより、利用可能なさまざまな辞書/ライブラリを比較しました-
Dictionary( System.Collections.Generics.Dictionary-SCGD), ImmutableDictionary, C5.HashDictionary, FSharpMap.
さまざまな項目数 (100、1000、10000、100000) で次のプログラムを実行すると、Dictionary が依然としてほとんどの範囲で勝者であることがわかります。最初の行はコレクション内のアイテムを示します。MS/Ticks は、ランダム化された x ルックアップの実行にかかる時間になります (コードは以下にあります)。
項目 - 100
SCGD - 0 MS - 50 ティック
C5 - 1 MS - 1767 ティック
Imm - 4 MS - 5951 ティック
FS - 0 MS - 240 ティック
項目 - 1000
SCGD - 0 MS - 230 ティック
C5 - 0 MS - 496 ティック
Imm - 0 MS - 1046 ティック
FS - 1 MS - 1870 ティック
項目 - 10000
SCGD - 3 MS - 4722 ティック
C5 - 4 MS - 6370 ティック
Imm - 9 MS - 13119 ティック
FS - 15 MS - 22050 ティック
項目 - 100000
SCGD - 62 MS - 89276 ティック
C5 - 72 MS - 103658 ティック
Imm - 172 MS - 246247 ティック
FS - 249 MS - 356176 ティック
これは、すでに最速のものを使用しており、変更する必要がないということですか? 不変の構造はテーブルの一番上にあるはずだと思っていましたが、そうではありませんでした。私たちは間違った比較をしていますか、それとも何か不足していますか? この質問をしがみついていましたが、聞いたほうがいいと感じました。リンクやメモ、または何らかの光を投げかける参照は素晴らしいものです。
テスト用の完全なコード -
namespace CollectionsTest
{
using System;
using System.Collections.Generic;
using System.Collections.Immutable;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Runtime;
using Microsoft.FSharp.Collections;
/// <summary>
///
/// </summary>
class Program
{
static Program()
{
ProfileOptimization.SetProfileRoot(@".\Jit");
ProfileOptimization.StartProfile("Startup.Profile");
}
/// <summary>
/// Mains the specified args.
/// </summary>
/// <param name="args">The args.</param>
static void Main(string[] args)
{
// INIT TEST DATA ------------------------------------------------------------------------------------------------
foreach (int MAXITEMS in new int[] { 100, 1000, 10000, 100000 })
{
Console.WriteLine("\n# - {0}", MAXITEMS);
List<string> accessIndex = new List<string>(MAXITEMS);
List<KeyValuePair<string, object>> listofkvps = new List<KeyValuePair<string, object>>();
List<Tuple<string, object>> listoftuples = new List<Tuple<string, object>>();
for (int i = 0; i < MAXITEMS; i++)
{
listoftuples.Add(new Tuple<string, object>(i.ToString(), i));
listofkvps.Add(new KeyValuePair<string, object>(i.ToString(), i));
accessIndex.Add(i.ToString());
}
// Randomize for lookups
Random r = new Random(Environment.TickCount);
List<string> randomIndexesList = new List<string>(MAXITEMS);
while (accessIndex.Count > 0)
{
int index = r.Next(accessIndex.Count);
string value = accessIndex[index];
accessIndex.RemoveAt(index);
randomIndexesList.Add(value);
}
// Convert to array for best perf
string[] randomIndexes = randomIndexesList.ToArray();
// LOAD ------------------------------------------------------------------------------------------------
// IMMU
ImmutableDictionary<string, object> idictionary = ImmutableDictionary.Create<string, object>(listofkvps);
//Console.WriteLine(idictionary.Count);
// SCGD
Dictionary<string, object> dictionary = new Dictionary<string, object>();
for (int i = 0; i < MAXITEMS; i++)
{
dictionary.Add(i.ToString(), i);
}
//Console.WriteLine(dictionary.Count);
// C5
C5.HashDictionary<string, object> c5dictionary = new C5.HashDictionary<string, object>();
for (int i = 0; i < MAXITEMS; i++)
{
c5dictionary.Add(i.ToString(), i);
}
//Console.WriteLine(c5dictionary.Count);
// how to change to readonly?
// F#
FSharpMap<string, object> fdictionary = new FSharpMap<string, object>(listoftuples);
//Console.WriteLine(fdictionary.Count);
// TEST ------------------------------------------------------------------------------------------------
Stopwatch sw = Stopwatch.StartNew();
for (int index = 0, indexMax = randomIndexes.Length; index < indexMax; index++)
{
string i = randomIndexes[index];
object value;
dictionary.TryGetValue(i, out value);
}
sw.Stop();
Console.WriteLine("SCGD - {0,10} MS - {1,10} Ticks", sw.ElapsedMilliseconds, sw.ElapsedTicks);
Stopwatch c5sw = Stopwatch.StartNew();
for (int index = 0, indexMax = randomIndexes.Length; index < indexMax; index++)
{
string key = randomIndexes[index];
object value;
c5dictionary.Find(ref key, out value);
}
c5sw.Stop();
Console.WriteLine("C5 - {0,10} MS - {1,10} Ticks", c5sw.ElapsedMilliseconds, c5sw.ElapsedTicks);
Stopwatch isw = Stopwatch.StartNew();
for (int index = 0, indexMax = randomIndexes.Length; index < indexMax; index++)
{
string i = randomIndexes[index];
object value;
idictionary.TryGetValue(i, out value);
}
isw.Stop();
Console.WriteLine("Imm - {0,10} MS - {1,10} Ticks", isw.ElapsedMilliseconds, isw.ElapsedTicks);
Stopwatch fsw = Stopwatch.StartNew();
for (int index = 0, indexMax = randomIndexes.Length; index < indexMax; index++)
{
string i = randomIndexes[index];
fdictionary.TryFind(i);
}
fsw.Stop();
Console.WriteLine("FS - {0,10} MS - {1,10} Ticks", fsw.ElapsedMilliseconds, fsw.ElapsedTicks);
}
}
}
}
