Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I'm writing a Java framework to manipulate a large amount of data in-memory, where many "cells" that are near each other will have the same value.

I'm looking for algorithms and/or techniques specially designed to eliminate those duplication while maintaining fast in-memory read access speed. That is, techniques that keeps an O(1) read-access speed.

My data is store in immutable objects, to allow fast multi-threading. The data itself can be anything, from 4 bits-per-cell to doubles to arrays of beans, etc.

share|improve this question
add comment

closed as off-topic by gnat, MichaelT, World Engineer Oct 23 '13 at 14:22

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Questions asking us to recommend a tool, library or favorite off-site resource are off-topic for Programmers as they tend to attract opinionated answers and spam. Instead, describe the problem and what has been done so far to solve it." – gnat, MichaelT, World Engineer
If this question can be reworded to fit the rules in the help center, please edit the question.

2 Answers

up vote 1 down vote accepted

If there is a lot of repetition of values then some form of run length encoding might work for the compression side, the tricky part would be maintaining O(1) lookup (or if we relax that constraint slightly, fast lookup)

you could get log m lookup relatively easily (where m is the number of runs , not the number of values) by instead of storing the length with each value store the index

e.g. using the wikipedia example of

WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW

instead of storing the lengths with each value for a run (added parens for clarity)

(12 W)(1 B)(12 W)(3 B)(24 W)(1 B)(14 W)

we could store the indexes at which we change value (pluss an ending value if necessary)

(0 W)(12 B)(13 W)(25 B)(28 W)(52 B)(53 W)(67 null) 

we can then use a binary search on the index to find the value for any index in log(m) which may be quick enough?

share|improve this answer
add comment

Look into memoization. You may be able to store pointers to the data, or a partial prefix of it, instead of the data itself.

Of course if your data are small enough this may not be a win.

share|improve this answer
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.