libcollections: TrieMap is not a general Trie #14902
Comments
bors
added a commit
that referenced
this issue
Nov 10, 2014
…=bstrie I've implemented the new collection views API for TrieMap. I more or less followed the approach set out by @gankro in BTreeMap, by using a `SearchStack`. There's quite a bit of unsafe code, but I've wrapped it safely where I think is appropriate. I've added tests to ensure everything works, and performance seems quite good. ``` test trie::bench_map::bench_find ... bench: 67879 ns/iter (+/- 4192) test trie::bench_map::bench_find_entry ... bench: 186814 ns/iter (+/- 18748) test trie::bench_map::bench_insert_large ... bench: 716612 ns/iter (+/- 160121) test trie::bench_map::bench_insert_large_entry ... bench: 851219 ns/iter (+/- 20331) test trie::bench_map::bench_remove ... bench: 838856 ns/iter (+/- 27998) test trie::bench_map::bench_remove_entry ... bench: 981711 ns/iter (+/- 53046) ``` Using an entry is slow compared to a plain find, but is only ~15% slower for inserts and removes, which is where this API is most useful. I'm tempted to remove the standalone `remove` function in favour of an entry-based approach (to cut down on complexity). I've added some more comments to the general part of the code-base, which will hopefully help the next person looking over this. I moved the three key structures to the top of the file so that the nesting structure is clearly visible, and renamed `Child<T>` to `TrieNode<T>` and `TrieNode<T>` to `InternalNode<T>` to improve clarity. If these changes are creeping, I'm happy to revert them. Let me know if my use of `fail!` is ok, I was a little unsure of how specific to be. Some of the data-structures have various invariants that shouldn't be broken, so using `fail!` seemed appropriate. ## Still to do * Modernise iterators (make them double-ended). * Make the keys generic, or rename this data-structure (see: #14902). * Possibly move this code out of libcollections. [Searching Github for TrieMap turns up very few real results.][triemap-search] Related issues: #18009 and #17320 [triemap-search]: https://github.com/search?utf8=%E2%9C%93&q=TrieMap+language%3ARust&type=Code&ref=searchresults
|
TrieMap is not part of the std lib anymore. |
RalfJung
pushed a commit
to RalfJung/rust
that referenced
this issue
Aug 1, 2024
… r=Veykril fix: let glob imports override other globs' visibility Follow up to rust-lang#14930 Fixes rust-lang#11858 Fixes rust-lang#14902 Fixes rust-lang#17704 I haven't reworked the code here at all - I don't feel confident in the codebase to do so - just rebased it onto the current main branch and fixed conflicts. I'm not _entirely_ sure I understand the structure of the `check` function in `crates/hir-def/src/nameres` tests. I think the change to the test expectation from rust-lang#14930 is correct, marking the `crate::reexport::inner` imports with `i`, and I understand it to mean there's a specific token in the import that we can match it to (in this case, `Trait`, `function` and `makro` of `pub use crate::defs::{Trait, function, makro};` respectively), but I had some trouble understanding the meaning of the different parts of `PerNs` to be sure. Does this make sense? I tested building and using RA locally with `cargo xtask install` and after this change the documentation for `arrow_array::ArrowPrimitiveType` seems to be picked up correctly!
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
TrieMap ought to be called RadixMap, PatriciaTree, or something other than TrieMap, considering that it only works with
uintkeys.Ideally, TrieMap would work for any valuable that is a
RandomAccessIterator<T: Eq>, or something similar, which would make it much more useful/general.The text was updated successfully, but these errors were encountered: