.net słownik vs inne zarządzane niestandardowe struktury danych, dlaczego słownik .net jest tak szybki?

Question

Jestem w trakcie opracowywania niestandardowej struktury danych o stałej wartości klucza, aby porównać ją z SqlLite i Berkley DB. W każdym razie zanim napisałem implementację, chciałem znaleźć najlepszą strukturę danych do wykorzystania w tym celu. Spojrzałem na parę:

• Drzewo redblack typu open source.
• Implementacja słownika mono.

Chciałem, aby wybrane struktury danych miały numery wydajności porównywalne ze słownikiem .net.

Kiedyś prosty test dla pętli z 500k iteracji dla wkładek i używane stoper do mierzenia wkładek i kluczy zapoznać się:

Zauważyłem, że

• Berkley DB klucz czas odnośnika był mniej więcej taki sam jako słownik.
• Próbowałem testu pętli for C5 dla słownika, implementacji drzewa redblack, a nawet implementacji słownika mono.

Czas wstawiania: 7% wolniejszy niż słownik .net.
Czas wyszukiwania: 1000% wolniejszy niż słownik .net. To jest nawet wolniejsze niż szybkość wyszukiwania z sqllite !! Próbowałem wykonać test z włączoną optymalizacją kompilatora i nadal otrzymałem podobne wyniki.

Zdaję sobie sprawę, że porównuję Hashtables z drzewami itp., Ale wpadłem w zakłopotanie co do rozbieżności w wydajności między wszystkimi strukturami danych.

Ktoś ma jakieś pomysły

Answer 1

dwie myśli:

1. Należy upewnić się, że nie są przypadkowo w tym czasie JIT w badaniach - można dodać znaczną ilość czasu na wynik. Powinieneś wykonać dwie serie w tym samym wykonaniu i odrzucić pierwszy przebieg.

2. Powinieneś upewnić się, że nie korzystasz z debuggera - może to znacznie przekreślić wyniki wydajności.

Oprócz tego różnice w wydajności, które widzisz, mogą być wynikiem różnic w wydajności między tablicą asocjacyjną a drzewem. Struktura drzewa zazwyczaj ma średnią wydajność O (n * log (n)) dla wyszukiwania. Zrównoważone drzewo może zredukować to do O (lon (n)). Hashtables może w międzyczasie zbliżyć się do czasu O (1) dla wyszukiwań, gdy unika się kolizji mieszania.

Wyobrażam sobie również, że klasa .NET Dictionary jest wysoce zoptymalizowana, ponieważ jest strukturą danych dla wielu różnych rzeczy w .NET. Również ogólny słownik <> może być w stanie uniknąć boksowania, dlatego możesz zauważyć różnice w wydajności.

Answer 2

Wybierz strukturę danych i repozytorium w zależności od danych. Powiedział, że nie ma doskonałej struktury danych. Chociaż .NET Dictionary<,> jest dobrze zoptymalizowany, ponieważ często jest dobrym wyborem, nie jest odpowiedzią na wszystkie problemy - to 42 ...

Answer 3

Jeśli wszystko, czego potrzebujesz, to wyszukiwanie, czerwone/czarne drzewo nie będzie najlepszą strukturą danych. Zapewnia sortowanie, które zawsze będzie wolniejsze niż wyszukiwanie hashtable. Jeśli chcesz porównać słownik .net z porównywalną strukturą danych C5, użyjesz C5.HashDictionary.