algorithm - Big-O 和缓存感知数据结构和算法

Question

有什么地方可以让我对传统数据结构(如链表、各种树、哈希等)与缓存感知数据结构(如 Judy 树等)进行 Big-O 风格分析/比较？

Answer 1

其实，

我会看here用于分析朱迪树。

As illustrated in this data, Judy's smaller size does not give it an enormous speed advantage over a traditional "trade size for speed" data structure. Judy has received countless man-hours developing and debugging 20,000 lines of code; I spent an hour or three writing a fairly standard 200-line hash table.

If your data is strictly sequential; you should use a regular array. If your data is often sequential, or approximately sequential (e.g. an arithmetic sequence stepping by 64), Judy might be the best data structure to use. If you need to keep space to a minimum--you have a huge number of associative arrays, or you're only storing very small values, Judy is probably a good idea. If you need an sorted iterator, go with Judy. Otherwise, a hash table may be just as effective, possibly faster, and much simpler.