Extract first N unique integers from an Array

Question

I have a large list of integers (thousands), and I want to extract the first N (in the order of 10-20) unique elements from it. Each integer in the list occurs roughly three times.

Writing an algorithm to do this is trivial, but I wonder what's the most speed and memory efficient way to do it.

There are some additional constraints and informations in my case:

• In my use-case I extract my uniques multiple times on the array, each time skipping some elements from the beginning. The amount of elements that I skip is not known during unique-extraction. I don't even have a upper bound. Therefore sorting is not speed efficient (I have to preserve the order of the array).

• The integers are all over the place, so a bit-array as a lookup solution is not feasible.

• I want to avoid temporary allocations during the search at all costs.

My current solution looks roughly like this:

  int num_uniques = 0;
  int uniques[16];
  int startpos = 0;

  while ((num_uniques != N) && (start_pos < array_length))
  {
    // a temporary used later.
    int insert_position;

    // Get next element.
    int element = array[startpos++];

    // check if the element exist. If the element is not found
    // return the position where it could be inserted while keeping
    // the array sorted.

    if (!binary_search (uniques, element, num_uniques, &insert_position))
    {

      // insert the new unique element while preserving 
      // the order of the array.

      insert_into_array (uniques, element, insert_position);

      uniques++;
    }
  }

The binary_search / insert into array algorithm gets the job done, but the performance is not great. The insert_into_array call moves elements around a lot, and this slows everythign down.

Any ideas?

---

EDIT

Great answers, guys! Everyone deserves an accepted answer, but I can give only one. I'll implement a bunch of your ideas and do a performance-shootout with some typical data. The one with the idea that lead to the quickest implementation get's the accepted answer.

I'll run the code on a modern PC and a embedded CortexA8-CPU and I'll weight the results somehow. Will post the results as well.

---

EDIT: Results of the shoot-out

Timings on a Core-Duo, 100 iterations over a 160kb test-dataset.

Bruteforce (Pete):            203 ticks
Hash and Bruteforce (Antti):  219 ticks
Inplace Binary Tree (Steven): 390 ticks
Binary-Search (Nils):         438 ticks

http://torus.untergrund.net/code/unique_search_shootout.zip (C-source and testdata)

Additional remarks:

• The Inplace Binary Tree absolutely rocks for true random distributions (my test-data has a tendency to be ascending).

• The Binary-Search works very well on my testdata for more than 32 uniques. It performs almost linear.

Answer 1

Why not just start inserting your array elements into a std::set and stop when the set has N elements? Sets are guaranteed not to have duplicates. They're also guaranteed to be sorted, so if you traverse a set from begin() to end(), you'll do so in sorted order according to operator<.

Answer 2

Instead of storing the unique integers into an array, use an actual binary tree. It'll save you from shifting the array elements repeatedly.

Answer 3

I would try soring the uniques in an unbalanced binary tree. That'll save you the cost of rearranging the uniques list, and if the source list is random enough, the insertions into the tree won't unbalance it drastically. (And you can do a search-and-insert-if-not-present all in one go with a binary tree.) If it does become unbalanced, then, worst case would be the same as iterating over a 16 element list instead of doing the binary search.

You know the max size of the binary tree, so you can preallocate all the necessary memory ahead of time, so that shouldn't be an issue. You could even use the "I've run out of memory for nodes" condition to let you know when you're done.

(EDIT: Apparently folks think I'm advocating using exceptions here. I'm not. I might be advocating actual common lisp-style conditions, but not the escape-continuation style exceptions found in most languages. Besides, it looks like he wants to do C for this.)

Answer 4

For an array that small ( if you want the first 20 elements, on average you have 10 to check equality with), a linear scan often out performs a binary search, even if you aren't having to insert elements.

Answer 5

Use an array representation of a binary tree. The array can be of size 3N. Basically

arr[i] = value

arr[i+1] = left child array index

arr[i+2] = right child array index

Walk the "tree" each insertion of k, and if k is not found update its parent's [i+1] or [i+2] and add it to the next empty index. When you run out of space in the array, you've got your answer.

e.g.

find first 3 unique of 42243123: array size=3 * 3 = 9.

In the table below, "v" are values, "l" is left child index, "r" is right child index.

 v  l  r  v  l  r  v  l  r
 _________________________
-1 -1 -1 -1 -1 -1 -1 -1 -1
 4 -1 -1 -1 -1 -1 -1 -1 -1
 4  3 -1  2 -1 -1 -1 -1 -1
 4  3 -1  2 -1 -1 -1 -1 -1
 4  3 -1  2 -1 -1 -1 -1 -1
 4  3 -1  2 -1  6  3 -1 -1

and you're out of space.

Array indices 0 mod 3 are your answer.

You can preserve order by using groups of 4:

array[i] = value

array[i+1] = position in original array

array[i+2] = left child index

array[i+3] = right child index

Answer 6

The fastest time complexity you'll achieve with the restrictions you have imposed is O(n) using a dictionary with O(1) lookup instead of your binary tree for the unique integers. Why bother searching for them when you can look them up in constant time?

Since you're only dealing with "thousands of records", anything else is a trivial addition.

Answer 7

If you have thousands of integers and every one occurs roughly three times, your algorithm should find the set of N unique integers pretty quickly, roughly in N(1+e) steps for small e (assuming the integers are ordered relatively randomly).

This means that your algorithm would insert N times a random integer into the uniques array. Insert number K would on the average shift K/2 elements in the array, yielding (N^2)/4 move operations. Your binary search would take roughly N * (log(N)-1) steps. This yields total complexity of (N^2)/4 + N(log(N)-1) + N(1+e) for your algorithm.

I think you could better e.g. by the following:

int num_uniques = 0, startpos = 0, k, element;
int uniques[16];

/* Allocate and clear a bit table of 32 * 32 = 1024 bits. */
uint32 bit_table[32], hash;
memzero((void *)(&bit_table), sizeof(bit_table));

while (num_uniques < N && startpos < array_length) {
  element = array[startpos++];

  /* Hash the element quickly to a number from 0..1023 */
  hash = element ^ (element >> 16);
  hash *= 0x19191919;
  hash >>= 22;
  hash &= 1023;

  /* Map the hash value to a bit in the bit table.
     Use the low 5 bits of 'hash' to index bit_table
     and the other 5 bits to get the actual bit. */
  uint32 slot=hash & 31;
  uint32 bit=(1u << (hash >> 5));

  /* If the bit is NOT set, this is element is guaranteed unique. */
  if (!(bit_table[slot] & bit)) {
    bit_table[slot] |= bit;
    uniques[num_uniques++] = element;
  } else { /* Otherwise it can be still unique with probability
              num_uniques / 1024. */
    for (k=0; k<num_uniques; k++) { if (uniques[k] == element) break }
    if (k==num_uniques) uniques[num_uniques++] = element;
  }
}

This algorithm would run in expected time of N + N^2 / 128 because the probability of running the inner loop (index variable k) is low.

Answer 8

Given a list of integers of size N named L

Iterate L once to find the largest value and smallest value in the array.

Allocate (1 allocation) an integer array of size (small .. large) named A. Init this array to zeros

Iterate L, use L(i) to subscript into A, Increment the integer found there.

Then do your processing. Pick your starting point in L, and walk forward through the list, looking at A(i). Pick what ever set of A(i) > 2 that you want.

When you are done, dispose of A.

If you are really short on space, use 2 bits instead of an integer, with the following interpretations

00 count = 0
01 count = 1
10 count = 2
11 count > 2