CODEWITHSUNDEEP
algorithmlistsortingdata-structurestree
gumuz
gumuz

Reputation: 295

what is the most memory efficient datastructure for maintaining a sordted <5k list of integers?

I have many lists of sorted integers, all of them less than 3600 items each. I'd like to keep them in memory as much as possible, so I'm looking for a space efficient datastructure.

Most common operations will be inserts, membership testing and range queries.

the integers will be mostly in the 1 through 10 billion-range, though in theory there could be some corner cases where the integers will be much lower.

I've been looking at skiplists, which are quite nice, but I feel there might be more efficient structures out there.

Upvotes: 0

Views: 2488

Answers (1)

Maxime Henrion
Maxime Henrion

Reputation: 146

This really depends on the access pattern and the proportion of lookups with respect to modifications. When lookups are much more common than modifications (in your case, inserts apparently), which is quite common, you can actually get away with sorted arrays which will give you optimal memory efficiency.

If the inserts are actually more common, sorted arrays probably won't do, and you will have to resort to more complicated data structures. B-trees sound like a possible candidate given that they pack many nodes together, and thus do not suffer from the linkage overhead as much as AVLs, skip-lists or red-black trees.

I think it would be similarly interesting to investigate radix trees, especially if there happens to be a lot of successive integers in your lists, because such ranges would get "compressed" by the radix tree.

It is worth noting that a bloom filter can help further optimize your membership queries. They are, in a way, the most space-efficient data structures for membership queries, but being probabilistic, you can only use them in combination with some other deterministic data structure, unless of course you are allowed to return incorrect answers :-).

Upvotes: 2

Related Questions