search

laysakura / trie-rs

Memory efficient trie (prefix tree) library based on LOUDS
https://crates.io/crates/trie-rs
Apache License 2.0
82 stars 8 forks source link

Number of elements in trie #29

Open LucaCappelletti94 opened 3 months ago

LucaCappelletti94 commented 3 months ago

Hi, I am not sure whether there is a method in the trie that returns the number of elements in the trie. Is there?

shanecelis commented 3 months ago

You could search for "" and count the iterator.

LucaCappelletti94 commented 3 months ago

Maybe it would be best to add a counter in the Map struct? Like in a Vec.

shanecelis commented 3 months ago

I don't see the use case where knowing the size in O(1) time is worth it. You generally don't want to reify it, so it's not like you need to know to preallocate. Most searches will always be a different size but it would represent an upper bound. Is there a use case you had in mind?

LucaCappelletti94 commented 3 months ago

Generally speaking, I would expect the length of a set to be an O(1) complexity thing, especially since it only requires an usize. As a tradeoff time vs memory, it would seem worth it to me.

shanecelis commented 3 months ago

All right. Let's see it.

LucaCappelletti94 commented 3 months ago

I will make a small pull request adding it after we finish merging #28

shanecelis commented 2 months ago

I've gone from hesitant to, "Yes, this is all good and makes sense."