Извлечь первые N уникальных целых чисел из массива

Question

У меня большой список целых чисел (тысяч), и я хочу извлечь из него первые N (порядка 10-20) уникальных элементов. Каждое целое число в списке встречается примерно три раза.

Написание алгоритма для этого тривиально, но мне интересно, какой самый быстрый и эффективный способ сделать это.

В моем случае есть некоторые дополнительные ограничения и информация:

• В моем сценарии использования я несколько раз извлекаю свои уникальные выражения из массива, каждый раз пропуская некоторые элементы с самого начала. Количество элементов, которые я пропускаю, неизвестно во время уникального извлечения. У меня даже нет верхней границы. Поэтому сортировка не эффективна по скорости (я должен сохранить порядок массива).

• Целые числа повсюду, поэтому битовый массив в качестве поискового решения неосуществим.

• Я хочу избежать временных выделений во время поиска любой ценой.

Мое текущее решение выглядит примерно так:

  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++;
    }
  }

Алгоритм двоичного_поиска / вставки в массив выполняет свою работу, но производительность невелика. Вызов insert_into_array много перемещает элементы, и это замедляет все вниз.

Есть идеи?

---

EDIT

Отличные ответы, ребята! Каждый заслуживает принятого ответа, но я могу дать только один. Я реализую кучу ваших идей и проведу съемки с некоторыми типичными данными. Тот, у кого есть идея, которая приведет к самой быстрой реализации, - это принятый ответ.

Я буду запускать код на современном ПК и встроенном процессоре CortexA8 и как-нибудь взвесить результаты. Также опубликую результаты.

---

РЕДАКТИРОВАТЬ: Результаты перестрелки

Синхронизация на Core-Duo, 100 итераций по тестовому набору 160 КБ.

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-источник и тестовые данные)

Дополнительные замечания:

• Бинарное дерево на месте абсолютно подходит для истинных случайных распределений (мои тестовые данные имеют тенденцию к возрастанию).

• Бинарный поиск очень хорошо работает с моими тестовыми данными для более чем 32 уникальных устройств. Работает почти линейно.

Answer 1

Почему бы просто не начать вставлять элементы массива в std :: set и остановиться, когда в наборе есть N элементов? Наборы гарантированно не имеют дубликатов. Они также гарантированно будут отсортированы, поэтому, если вы пройдете набор от begin () до end (), вы будете делать это в отсортированном порядке в соответствии с оператором <. </p>

Answer 2

Самая быстрая временная сложность, которую вы достигнете с введенными ограничениями, - O(n) с использованием словаря с O(1) поиска вместо вашего двоичного дерева для уникальных целых чисел. Зачем искать их, когда вы можете искать их в постоянном времени?

Поскольку вы имеете дело только с «тысячами записей», все остальное является тривиальным дополнением.

Answer 3

Для такого маленького массива (если вы хотите первые 20 элементов, в среднем у вас есть 10, чтобы проверить равенство), линейное сканирование часто выполняет двоичный поиск, даже если вам не нужно вставлять элементы.

Answer 4

Я бы попытался сохранить уникальность в несбалансированном бинарном дереве. Это сэкономит вам затраты на перестройку списка уникальности, и если список источников достаточно случайный, вставки в дерево не приведут к его существенному дисбалансу. (И вы можете выполнить поиск и вставку, если не присутствует все сразу, с двоичным деревом.) Если оно становится неуравновешенным, тогда наихудший случай будет таким же, как итерация по списку из 16 элементов вместо делать бинарный поиск.

Вы знаете максимальный размер бинарного дерева, так что вы можете заранее выделить всю необходимую память заранее, чтобы это не было проблемой. Вы даже можете использовать условие «У меня закончилась память для узлов», чтобы сообщить, когда вы закончите.

(РЕДАКТИРОВАТЬ: Очевидно, люди думают, что я выступаю за использование исключений здесь. Я не. Я мог бы выступать за фактические общие условия в стиле lisp, но не за исключениями стиля escape-продолжения, встречающимися в большинстве языков. как он хочет сделать C для этого.)

Answer 5

Использовать представление массива двоичного дерева. Массив может быть размером 3N. В основном

arr [i] = значение

arr [i + 1] = индекс левого дочернего массива

arr [i + 2] = индекс правого дочернего массива

Пройдите по «дереву» каждую вставку k, и если k не найдено, обновите родительские [i + 1] или [i + 2] и добавьте его к следующему пустому индексу. Когда вам не хватает места в массиве, вы получите ответ.

, например

найти первые 3 уникальных из 42243123: размер массива = 3 * 3 = 9.

В приведенной ниже таблице "v" - значения, "l" - индекс левого ребенка, "r" - индекс правого ребенка.

 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

и вам не хватает места.

Индексы массива 0 mod 3 - ваш ответ.

Вы можете сохранить порядок, используя группы из 4:

массив [i] = значение

массив [i + 1] = позиция в исходном массиве

массив [i + 2] = левый дочерний индекс

массив [i + 3] = правый дочерний индекс

Answer 6

Вместо сохранения уникальных целых чисел в массиве используйте фактическое двоичное дерево. Это избавит вас от повторного смещения элементов массива.

Answer 7

Если у вас есть тысячи целых чисел, и каждое из них встречается примерно три раза, ваш алгоритм должен довольно быстро найти набор из N уникальных целых чисел, примерно за N (1 + e) ​​шагов для малых e (при условии, что целые числа упорядочены относительно случайно ).

Это означает, что ваш алгоритм будет вставлять N раз случайное целое число в массив unique. Вставка числа K будет в среднем сдвигать K / 2 элемента в массиве, давая (N ^ 2) / 4 операции перемещения. Ваш бинарный поиск займет примерно N * (log (N) -1) шагов. Это дает общую сложность (N ^ 2) / 4 + N (log (N) -1) + N (1 + e) ​​для вашего алгоритма.

Я думаю, вы могли бы лучше, например. по следующему:

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;
  }
}

Этот алгоритм будет работать в ожидаемое время N + N ^ 2/128, поскольку вероятность запуска внутреннего цикла (индексная переменная k) мала.

Answer 8

Дан список целых чисел размера N с именем L

Выполните итерацию L один раз, чтобы найти наибольшее и наименьшее значение в массиве.

Выделите (1 выделение) целочисленный массив размера (маленький .. большой) с именем A. Инициируйте этот массив в нули

Итерируйте L, используйте L (i) для подстрочного индекса в A, Увеличьте найденное там целое число.

Тогда сделай свою обработку. Укажите начальную точку в L и пройдите по списку, глядя на A (i). Выберите тот набор A (i)> 2, который вам нужен.

Когда вы закончите, избавьтесь от A.

Если у вас действительно мало места, используйте 2 бита вместо целого числа со следующими интерпретациями

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