4
$\begingroup$

I want to store a subset of $\{1,2,\dots,n\}$ in a data structure such that the total space used is $O(n)$ bits and accessing a particular element can be done in $O(1)$ time. I have tried binary search tree and array data structures but they are too slow.

In short I need a data structure with $O\big(\frac {n } { \log \log n}\big)$ many cells and size of each cell should be $O(\log \log n)$ bits.

Model of computation: Input memory and a write only output memory. The computation proper takes place in a working memory of limited size. When stating a problem can be solved with in a certain bits, what we mean is that the working memory comprises that many bits. The input and working memories are divided into words of $w$ bits for a fixed parameter $w$, arithmetic and logical operations on $w$-bit words take constant time, and random access to the input and working memories is provided. In the context of inputs of $n$ words,$w= \theta(\log n)$.

Operations: Insert($i$), access($i$), where $i \in [n]$. The access operation must run in $O(1)$ time.

Motivation: I'd like to store the stack in DFS using this data structure.

I am looking for an deterministic approach, but to me it does not seems working, so probabilistic approach is also fine.

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ I don't understand what your operations do, since you haven't described them. Also, can you be more explicit about your time and space constraints? Explain how much time each operation should take, and how much space your data structure should consume (you say $O(n)$ bits given that there are "$n$ values", but you don't explain what that means). Finally, is your RAM a bit RAM or a word RAM? That is, do operations on words of length $O(\log n)$ bits cost 1 operation or more? $\endgroup$
    – Yuval Filmus
    Commented Sep 6, 2017 at 8:28
  • 1
    $\begingroup$ $n$ unique keys from $1$ to $n$? That sounds like you just need a simple array, indexed with $i$, of whatever values are associated with each $i$ (or a bitvector if you just need to check existence of a key at any stage before all insertions are over). $\endgroup$
    – Omar
    Commented Sep 6, 2017 at 15:52
  • 4
    $\begingroup$ @new_born Do you want to store $n$ numbers, each number between $1$ and $n$? It's information theoretically impossible to do this with fewer than $O(n\log n)$ bits. $\endgroup$
    – jschnei
    Commented Sep 6, 2017 at 17:27
  • 1
    $\begingroup$ Please edit the question to incorporate all information into the question -- don't just answer in the comments. People shouldn't have to read the comments to understand what you are asking. If you are able to guarantee that there will be no duplicates, you should say that in the question. If duplicates are possible, you should say that in the question. $\endgroup$
    – D.W. ♦
    Commented Sep 6, 2017 at 21:08
  • 1
    $\begingroup$ Also, you can't store an integer from $1$ to $n$ in $\log \log n$ bits. This makes me wonder: Is it possible you meant cells of size $O(\lg n)$ instead of cells of size $O(\lg \lg n)$, etc.? $\endgroup$
    – D.W. ♦
    Commented Sep 8, 2017 at 20:17

2 Answers 2

Reset to default
3
$\begingroup$

A simple solution is to use a $n$-bit bitvector. This is basically an array with $n$ entries, where each entry is either 0 or 1. If the $i$th entry is 1, that means that $i$ was stored in the data structure; 0 means that $i$ was not stored in the data structure. This takes $O(n)$ bits of space. The insert and access operations can be done in $O(1)$ time.

The crucial requirement that makes this solution possible is that there will be no duplicates; each number is present at most once. If you allowed duplicates, the problem would not be solvable within the space requirements you list: storing $n$ numbers from $1$ to $n$ requires at least $\Theta(n \log n)$ bits, based on information-theoretic concerns.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ If order is unimportant, you can store $n$ not necessarily unique numbers from $1$ to $n$ using $2n$ bits: Let $c_i$ be the number of occurrences of $i$. The code is the concatenation of $0^{c_i}1$ for each $i$ from $1$ to $n$. That clearly has $n$ zeros and $n$ ones. The information theoretic limit is smaller than $2n$, since most $2n$-bit numbers don't have the same number of zeros and ones. (Of course, this encoding doesn't give you $O(1)$ access.) $\endgroup$
    – rici
    Commented Sep 10, 2017 at 6:55
0
$\begingroup$

I'm not sure I understand the problem you are trying to solve, but how about perfect hashing? It works like a hashmap, but has at most one entry per bucket, hence access is guaranteed $O(1)$ for access. Depending on how much time you spend on finding the has function, the hashmap can have a map very (almost?) every bucket is filled and your space complexity is also close to or even equal to $O(1)$. Since you will have at most one entry per bucket, You don't need an additional data structure in each bucket to handle collisions, so all you need is an array with your data and the bits to store the hash function.

Insertion is a bit more expensive, because you may have to try out a few hashfunctions before you find a good one, but this is typically quite fast.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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