This project contains implementations of various data structures in C# plus some benchmarking applications and tests.
All structures in this library implement ordered dictionaries, that means System.Collections.Generic.IDictionary<int,T> and few additional functions: Higher(int x), Lower(int x), First(), Last(). Library contains following data structures:
- van Emde Boas Tree
- x-fast trie (with standard hashing or dynamic perfect hashing)
- y-fast trie (with standard hashing or dynamic perfect hashing)
Some data structures required red-black tree. Implementation comes from Mono. Also it is used as a point of reference in benchmarking.
Performance results of all important functions. All benchmarks were run on structures of size from 100 000 elements to 1 000 000 elements containing randomly picked elements. In case of find 100 000, search operation was performed 100 000 times. Time is in milliseconds, memory usage is in megabytes.
