Big-O and Cache Aware Data Structures & Algorithms

Question

Is there someplace where I can get a Big-O style analysis / comparison of traditional data structures such as linked lists, various trees, hashes, etc vs. cache aware data structures such as Judy trees and others?

Answer 1

Read The Art of Computer Programming books by Don Knuth. These are considered by many to be the best source of algorithm information around.

Answer 2

BigO is about algorhitms comlexity doing certain task. There are different tasks avaliable on each data structure. Most important one are: Sort, Find(in sorted structure) and add element.

So what are you looking for is complexity of certain task for certain data structure.

For most data types optimal sorting algorhitm is O(n*log(n)) but keep in mind that some structures are still slower, for instance sorting linked list is slower than arrays athough both have n*log(n) complexity

Answer 3

Actually,

I would look here for analysis of Judy Trees.

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.

Answer 4

Did you look in: "Introduction to Algorithms"

(http://en.wikipedia.org/wiki/Introduction_to_Algorithms)