3 ms·
Like someone else mentioned, there's no need for Node pointers at all here, storing Nodes by value cuts away a decent chunk of complexity and should run plenty
by codr7 7y ago
Like someone else mentioned, there's no need for Node pointers at all here, storing Nodes by value cuts away a decent chunk of complexity and should run plenty faster (especially when threads are linked).
I would consider switching the unordered_map to a sorted vector<pair<T, Node>>; or even better, move the key into Node and simply store as vector<Node>. Hash tables are relatively expensive to create in exchange for excellent performance for large tables, and you're creating a lot of tiny tables. A regular map would likely fall somewhere in between performance-wise since they're cheaper to create.
- psurge 7y agoI don't think Node can contain a std::vector<Node>, since STL containers cannot have incomplete value types. But maybe I'm misunderstanding you? I think absl::flat_hash_map<T, std::unique_ptr<Node>> would be worth considering in this application. Keys and values are stored inline, so the memory and creation costs should be comparable to std::vector - https://abseil.io/docs/cpp/guides/container#abslflat_hash_map-and-abslflat_hash_set https://abseil.io/docs/cpp/guides/container#abslflat_hash_ma...
- stabbles 7y agoNot all containers though, since C++17 std::vector, std::list and std::forward_list do support incomplete element types as long as the allocator meets certain requirements. So std::vector<Node> is definitely OK.
- saagarjha 7y ago> STL containers cannot have incomplete value types As of C++17, certain containers have minimal support for incomplete types.
- deleted 7y ago[deleted]
- codr7 7y agoTrue enough, my mistake :) Just getting rid of the hash buckets and shared_ptrs would be a giant leap in the right direction. Nice. I have no experience from absl, but I've sucessfully used sorted vectors to speed up these kinds of solutions on several occasions [0]. [0] https://github.com/codr7/cidk/blob/master/src/cidk/env.hpp https://github.com/codr7/cidk/blob/master/src/cidk/env.hpp
- codr7 7y agoI did a quick re-implementation [0] taking these ideas into account. It also avoids assuming anything about inputs except iterating the key type and moves most functionality into Node to support more use cases. [0] https://github.com/codr7/stash/blob/master/trie.cpp https://github.com/codr7/stash/blob/master/trie.cpp