从Array中提取前N个唯一整数

我有一个大的整数列表(数千),我想从中提取第一个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++;
    }
  }

binary_search/insert into array算法完成了工作,但性能不是很好.insert_into_array调用会移动很多元素,这会降低每个元素的速度.

有任何想法吗？

编辑

大家好!每个人都应得到一个可接受的答案,但我只能给一个.我将实现一堆你的想法,并用一些典型的数据进行性能拍摄.具有导致最快实施的想法的那个得到了接受的答案.

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

编辑:枪战的结果

Core-Duo上的计时,在160kb测试数据集上进行100次迭代.

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和testdata)

补充说明:

Inplace Binary Tree绝对是真正的随机分布(我的测试数据倾向于上升).

Binary-Search在我的testdata上运行得非常好,超过32个uniques.它几乎是线性的.

Tyler McHenr.. 11

为什么不直接将数组元素插入到std :: set中,当set有N个元素时停止？保证集不会有重复.它们也保证被排序,所以如果你遍历一个从begin()到end()的集合,你将按照运算符<按顺序排序.

为什么不直接将数组元素插入到std :: set中,当set有N个元素时停止？保证集不会有重复.它们也保证被排序,所以如果你遍历一个从begin()到end()的集合,你将按照运算符<按顺序排序.