Fastest associative array on C++ (Trie) - Part2

Hi All,
First part of the article you can find here
http://www.cplusplus.com/forum/general/208418/

This implementation contains more than 8K highly optimized lines of code in C++. https://github.com/Bazist/HArray

In last test was inserted 1 billion keys without any errors.

As I mention before, good optimized Trie can works much faster than Tree or even Hashtables. The problem is that I can't find any good implementation in statndard C/C++ library Trie and want fix it.

Maybe anyone know a procedure to add an implementation to the standard library ?
Thanks a lot for any help !
the standards and language are governed by a committee. You can suggest and they can evaluate your suggestion. You personally cannot just add things to the language; this is a big deal as all compilers and tools etc need to support the proposed changes and if everyone just threw whatever in it would be un-manageable.

You can google around to see if you can figure out where to suggest; I am not sure but it should be easy enough to find.

Hash is O(1). I am unaware of anything faster.

An optimized tree is just a vector with funky access smoke and mirrors and is very fast and allows a lot of tricks under the hood while looking like a tree to the user. The 'pointers' are just indices. But I have no idea how that compares to the trie.
Last edited on
> Maybe anyone know a procedure to add an implementation to the standard library ?

See: https://isocpp.org/std/submit-a-proposal

Submitting it to boost first would perhaps be a good idea: http://www.boost.org/development/submissions.html

Hash is O(1). I am unaware of anything faster.


I can explain. For example you have key 256 bytes long.
Let's compare two scenarios, what happens in hashtable and trie.
Hashtable
1. Scan all 256 bytes of key and calculates hash
2. Jump to calculated slot in array
3. Scan all 256 bytes of key again. Check that 256 bytes it's our key (because of collision in ht)
So in hashtable we scan Key at least twice + hash calculation + possible chunks of collision

HArray (Trie)
1. Scan all 256 bytes.
2. Rare branches if there are many keys and our Key path is spitted on two or more paths.
In Trie we scan Key only once.

+ and other aspect - cache of processor
If we have two keys for example: 0000001 and 0000002, in hashtable 000000 bytes will be duplicated for two different keys, but in Trie is no. In Trie in most cases 000000 will be writed once and will be situated in cache. It also increases speed of Trie in compare with Hashtable.


An optimized tree is just a vector with funky access smoke and mirrors and is very fast and allows a lot of tricks under the hood while looking like a tree to the user. The 'pointers' are just indices. But I have no idea how that compares to the trie.

You can find on my GitHub page image where I compare functionality of different structures.
https://github.com/Bazist/HArray
These both structures (Tree and Trie) have ordered keys and allow scan it by range

See: https://isocpp.org/std/submit-a-proposal

Submitting it to boost first would perhaps be a good idea: http://www.boost.org/development/submissions.html


Thanks ! I will try
Topic archived. No new replies allowed.