cuplv / iodyn.rust

Collections Library for Adapton, in Rust
13 stars 0 forks source link

Update `unique_trie` to compare against native Rust `HashMap` module #2

Closed matthewhammer closed 7 years ago

matthewhammer commented 7 years ago

Currently, we are comparing against other ways of folding over the tree (representing a sequence) to build a list (not a set), and a sorted, de-duplicated vector (which is somewhat set-like, in that it only contains each key at most once).

However, as we know, these comparisons aren't entirely "fair":

An interesting future comparison line would consist of the following:

If we can beat this non-incremental, from-scratch computation of native Rust code with our incremental Trie, then we have a compelling story to tell.

kyleheadley commented 7 years ago

I removed the incremental vec version that was sorting and deduping its elements, and added a non-incremental hash map version (the incremental version with hash map as accumulator is not trivial because HashMap is not Hash, that is, the full struct is not hashable, so it is incompatible with Adapton)