3 ms·
Solution to no allocation during trie traversal is to pre-allocate the necessary data along with each node. Nice, general solution that could apply for many ot
by cheez 10y ago
Solution to no allocation during trie traversal is to pre-allocate the necessary data along with each node.
Nice, general solution that could apply for many other problems but hardly zero-allocation.
Thanks for the post!
- jjnoakes 10y ago> hardly zero-allocation Read the article to the end.
- cheez 10y agoWhat did I miss? He adds fields onto each node to help with traversal.
- jjnoakes 10y agoYou missed the last paragraph, I think: > For a production implementation it may be worth packing i into the flags field since it only needs a few bits, even with larger alphabets. Also, I bet, as in Deutsch-Schorr-Waite, the p field could be eliminated and instead one of the child pointers is temporarily reversed. With these changes, this technique would fit into the original struct trie without changes, eliminating the extra memory usage.
- cheez 10y agoThanks buddy! I did miss that.
- taeric 10y agoI think you are misreading it, some. Think of it more as "zero allocation during traversal." The point is not "free traversal of a Trie" but another trade off to look at in creating a program. (Granted, one that is at a level most of us are not writing at.) This is similar, in some ways, to allocation free depth first searches of tree structures. (That is, without a stack.) It is hardly "free" since you have to take care in constructing the tree. However, if you have a tree you will construct once and then want to make sure you can do a DFS without worrying about stack storage, probably a very valuable technique to have in your belt.
- deleted 10y ago[deleted]