首先从数组中提取N个唯一整数

Question

我有一个大的整数列表(千)，我想从其中提取第一个N(按10-20的顺序排列)唯一的元素。列表中的每个整数大约发生三次。

编写一个算法来完成这个任务是很简单的，但是我想知道什么是最快速和内存效率最高的方法。

在我的例子中还有一些额外的限制和信息：

在我的用例中，我在数组上多次提取我的uniques，每次从一开始跳过一些元素。在唯一提取过程中，我跳过的元素数量是不知道的。我甚至没有上限。因此排序效率不高(我必须保持数组的顺序)。

• 整数到处都是，所以作为查找解决方案的位数组是不可行的。

• I希望在搜索过程中不惜一切代价避免临时分配。

我目前的解决方案大致如下：

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

binary_search / insert数组算法完成了任务，但性能并不好。insert_into_array调用会频繁地移动元素，这会减缓所有的速度。

有什么想法吗？

编辑

很好的答案伙计们！每个人都应该得到一个公认的答案，但我只能给出一个答案。我将实现一些您的想法，并使用一些典型的数据进行一次性能大战。有着最快实现的想法的人得到了公认的答案。

我将在现代PC和嵌入式CortexA8-CPU上运行代码，并以某种方式对结果进行加权。也会公布结果。

编辑:退出的结果

在一个160 on测试数据集上进行100次迭代的Core上的计时。

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个以上的uniques。它的性能几乎是线性的。

Answer 1

对于这样小的数组(如果您想要前20个元素，平均有10个元素要检查等式)，线性扫描通常执行二进制搜索，即使不需要插入元素。

Answer 2

为什么不开始将数组元素插入到std::set并在集合有N个元素时停止呢？集合保证不会有重复。它们也被保证被排序，所以如果您从begin()到end()遍历一个集合，您将按照operator<的排序顺序这样做。

Answer 3

我会尝试在一个不平衡的二叉树中提取这些单子。这将节省您重新排列uniques列表的成本，如果源列表足够随机，则插入到树中的操作不会严重失衡。(您可以使用二叉树进行搜索和插入(如果不存在的话)。)如果它确实变得不平衡，那么，最坏的情况将与迭代16个元素列表而不是执行二进制搜索相同。

您知道二叉树的最大大小，所以您可以提前预先分配所有必要的内存，所以这不应该是一个问题。您甚至可以使用“我已耗尽节点内存”的条件让您知道何时完成。

(编辑:显然，人们认为我在这里提倡使用例外。我没有。我可能是在提倡实际常见的lisp风格的条件，但不是大多数语言中存在的转义-延续风格的异常。此外，他似乎想为此做C。)