Looking for space efficient algorithms and data structures

Question

Preferably in Java. I am interested in implementations of data structures such as Sets and Maps, and algorithms such as sorting, that are memory-efficient, not necessarily fast. I could live with O(n^2) fetch and store if the amount of memory and number of allocations was low. Anything out there?

Answer 1

O(n^2) seems really excessive. What exactly are you expecting from your data structure? Simply using a vector will give you O(n) worst case for storage and retrieval and O(n) space requirement. – The latter can’t really be reduced (barring a compressing data structure, but for that to work you need to provide a lot more information about your data domain) so why not simply use a vector?

Answer 2

For extremely compact structures compared to java standard ones, one could work at the bit level. That depends a lot on your data of course, the code can't really be generic I guess. I know nothing that could do it generically. You could have to develop it (possibly using the BitSet class).

---

Something in Java that is extremely compact it the enum classes : EnumSet and EnumMaps. They are both extremely compact and extremely fast. The idea:

• Identifying the presence or not of a specific enum instance in a Set is a boolean information, so it requires 1 bit. Therefore, the EnumSet requires only one Long (for enums with less than 64 instances).
• In an EnumMap (String is just for the example), it is not required to store the key (enum), it can be made implicit by calling ordinal() on the enum which delivers the index. Therefore, the storage can be String[], and the keys are not stored.