4 ms·
Well, to pick on Valeri, this is simply wrong Trees are the single most important data structure in computer science. Just about everything you do in yo
by x0x0 11y ago
Well, to pick on Valeri, this is simply wrong
Trees are the single most important data structure in computer science. Just
about everything you do in your programming career will be related to trees.
Trees are a horrid data structure for any modern processor. Pointer chasing thrashes caches. The actual most important data structure is a hashmap. The same speed in theory, much faster in practice.
- aidenn0 11y agoHow do you represent hierarchical data in a single hashmap?
- JBReefer 11y agoYou can frequently buy a performance increase by representing nested calculation logic in hashmaps via memoization.
- KingMob 11y agoDepending on your problem domain, you might be able to flatten it by just combining keys together (subject to keys being combinable like with string concatenation, using separators to ensure uniqueness of combined keys, etc.) E.g., turn {"foo": {"bar": "moop"}} into {"foo-bar": "moop"}. This also requires writing accessor fns, but it might be worth it, depending.
- aidenn0 11y agoRight, that works fine so long as you only ever go up the hierarchy, but going down the hierarchy would require a prefix search, which is the one place where trees actually do win over hashes.
- pessimizer 11y agoEverything in programming is trees. If you write a program that calls functions, that call other functions, that's a tree.
- dalke 11y agoI believe continuation-passing style is an alternative to the direct style you mention. Return-oriented programming and threaded programming may be specific counter-examples.
- cjhopman 11y agoUnlikely. Unless a single function corresponds to a possibly infinite set of nodes, most programs are not trees.
- pessimizer 11y agoA single node is a tree. main() is a tree.
- sklogic 11y agoYou do not need to represent a binary tree as a structure with two pointers. See how a typical Huffan tree is implemented, for example.
- nostrademons 11y agoThis depends a lot on data size & shape. There've been some applications where I benchmarked a std::map (a tree, in practice) against Google's highly-tuned hashmap for a small (~25-50 item) container and the tree came out ahead. For such a small data structure, everything fit in L1 cache, and comparisons to follow pointers could usually be resolved by looking at the first word of the key. One thing often forgotten with hashmaps is that they aren't actually O(1); they're O(k), where k is the length of the key, and often need to examine the entire key to derive a hashcode. This oftentimes makes them significantly slower than a binary search tree when the size of the key is large compared to the size of the container. As always, measure before optimizing. YMMV.