2
$\begingroup$

We want to represent a list of $n$ unique integers between $0$ and $n-1$ in a memory-efficient way. The only operation we need to support is looking up the $n\text{-th}$ element.

What are some of the most compact data structures that can do the lookup in $O(1)$ or $O(\log n)$?


Naive example: an array of $\log n$-bit integers. ($n \log{n} $ bits)

Intuitively it seems that we can do better. If we didn't have the fast lookup requirement, the data structure could simply be a permutation index ($ ⌈\log{n!}⌉ ≈ n \log{n} − 1.44n$ bits).

$\endgroup$
3
  • $\begingroup$ Well, having a search engine provide results for something like space efficient $\or$ saving storage $\or$ representation of permutations brings up results like J Ian Munro; Rajeev Raman; Venkatesh Raman; Srinivasa Rao Satti: Succinct Representations of Permutations and Functions in Theoretical Computer Science, 2011/08: $(1+\epsilon) n \lg n + O(1), 0 < \epsilon \le 1$ bits suffices to compute arbitrary powers in constant time, $\lceil{\lg n!}\rceil + o(n)$ bits allow $O(\lg n / \lg \lg n)$ time ($\log_2$ outside $O$?). $\endgroup$
    – greybeard
    Nov 9 '21 at 6:55
  • 1
    $\begingroup$ (Venkatesh Raman is one of the authors of Brodnik, Andrej& al.: Space-Efficient Data Structures, Streams, and Algorithms, Springer 2013.)(arxiv.org seems to host a preprint of above paper: Succinct Representations of Permutations and Functions) $\endgroup$
    – greybeard
    Nov 9 '21 at 7:01
  • $\begingroup$ Thanks greybeard! I'll read the paper to see if any of the representations described there improves over $n \log{n}$ (the theoretical lower bound being $⌈\log{n!}⌉ ≈ n \log{n} − 1.44n$ bits). $\endgroup$
    – glebm
    Nov 9 '21 at 20:54
1
$\begingroup$

This is equivalent to storing a permutation of $n$ items in memory. There are in general, $n!$ ($n$ factorial) such permutations, and it is well known that $\log(n!)=\Theta(n\log(n))$. Hence, you will need at least $\Omega(n\log(n))$ bits to represent the permutations (which is what you get from the naive solution).

So without even the requirement about the lookup time, you are bound to have at least this much memory consumed - and sadly you cannot compress it further.

$\endgroup$
1
  • $\begingroup$ The naive solution is exactly n log n bits. The information theoretic lower bound is ⌈log n!⌉ ≈ n log n − 1.44n. $\endgroup$
    – glebm
    Nov 9 '21 at 20:51
0
$\begingroup$

The naive solution may be n log n bits. But for the first number you have n choices; you have n-1 choices for the second number, n-2 choices for the third number etc. So log(n!) bits, rounded up to the next integer, would be a possibility.

In practice, if you want the lookup to be fast, looking up number k should locate a range of bits that represent some numbers around k, like numbers k-3 to k+5, and then there should be some fixed number of operations to extract number k.

For example: Given n, pick t depending on n, so that $n^t$ is only slightly less than a power of two, say $n^t < 2^m$. We then arrange the numbers $x_0$ to $x_{n-1}$ in groups of t numbers, $x_{k \cdot t}$ to $x_{k \cdot t + (t-1)}$. Interpret these t numbers as digits of a t-digit base-n number with a value less than $2^m$. Store the bits for each of these numbers consecutively.

Given j, we let $j = t \cdot k + r$. We take bits number j to j+m-1, interpret them as an integer, write that integer in base n, and take the j-th base n digit as the result.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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