3 ms·
Good datastructure, code looks quite clean for C. Your API is missing some of the advantages relative to hash tables though. Because it's a tree, operations li
by JonChesterfield 3y ago
Good datastructure, code looks quite clean for C.
Your API is missing some of the advantages relative to hash tables though. Because it's a tree, operations like union and difference of two instances can be sublinear in the size of the instances. E.g. union can copy subtrees when the other instance has empty at the corresponding position.
You're also missing a batch construction call, create a new tree out of N key/value pairs. That's much faster than inserting one at a time because you can sort the array up front and then create the tree without any temporary nodes.
The function pointers in the interface are probably difficult for the compiler to devirtualise. Changing that in C means macros or code generators though, does some damage to ease of use.
Thanks for sharing it
- mkirchner 3y agoThank you, happy to share. These are excellent pointers. Regarding the batch construction, it's not immediately clear to me how to implement sorting since the order is implicit through the hash function (it seems one would need to construct a trie to build a trie?) but I might be wrong...
- JonChesterfield 3y agoHash the keys before/while sorting. The repeated hashing with different seeds is an interesting approach to collisions but would add some annoyance here. Roughly do just enough work to put the key/values in the same order that you would see them in when iterating through the corresponding trie. Other way to go would be to implement merge then do the batch construction by partitioning the initial array, building tries out of the pieces then merging them. That could also be the fallback for when the first hash collides. If the partitioning was by the first five bits of the hash you'd get a reasonable approximation to doing the sort.