从整数向量列表中删除重复项的快速方法

Question

假设我们有一个函数，它返回100万个长度为30的整数向量，每个向量的条目都很小（比如-100到100之间）。进一步假设输出只有大约30000个唯一向量，其余是重复的。检索唯一输出向量列表的良好数据结构和算法是什么？优选地，当3%的唯一向量的比例大致恒定时，该解决方案应缩放良好。

这个问题主要是关于数据结构的，但我计划使用 STL 在 C 中实现它，所以也欢迎任何关于实现的提示。

• 朴素算法是存储已知向量的列表（可能按字典排序）。当一个新向量到达时，我们可以使用循环检查它是否已经在列表中（或在排序列表中搜索）。
• 散列：让我们假设向量存储在C数组中。什么是整数向量的好散列函数？我看到的一个缺点是每个向量的每个组件都至少被触摸一次。这似乎已经太多了。
• 任何树数据结构都好吗？例如，我们可以将所有可见向量的第一个组件中的值存储为根，然后将第二个组件中的值存储为它们的子级，…

我没有计算机科学背景。我也很高兴能找到文学的指针，在那里我可以学习如何处理这些问题。

Answer 1

计算第一个向量中值的CRC表示。您现在有一个数字代表您的30个值。该数字相对于其余向量可能是唯一的，但它没有保证。

将CRC值作为键，以及指向实际向量的指针，并将其插入到multimap {CRC，VectorPointer}中。

现在为每个剩余的向量计算CRC，并在多重映射中查找它。

如果找不到，请插入 {CRC， VectorPointer}。如果找到它，请遍历匹配项并比较数据元素以确定它是否相同。如果是丢弃新向量。如果不是，则插入 {CRC， VectorPointer}。

冲洗并重复，直到处理完所有30000个载体。

在multimap中，您有一个惟一的可迭代集合。

Answer 2

基数映射是理想的，但您需要实现它，因为std库中没有实现。

Answer 3

你提出的建议有时被称为旁观表；用于各种查找目的的辅助表。在您的情况下，您可以使用多种不同的方法来组织此表。最明显的是不要组织它，而是使用线性搜索来查看下一个元素是否已知。由于该表最终将包含大约30000个元素，这可能不是一个好主意。在标准库中（至少在C 11中），有两种可能性：＜code＞std：：set＜/code＞和＜code＞std：：unordered_set＜/code>std:：set使用某种形式的平衡树，因此最多生成lg

最后，您可以使用某种非二叉树。如果你真的可以将值限制在一个特定的范围内（例如 -100..100），你可以使用带有指向子节点的指针的普通向量或数组，直接使用元素值进行索引，根据需要进行转置。然后，您只需在树上行走，直到找到一个空指针，或者到达终点。树的最大深度将是 30，事实上，每个元素的深度都是 30，但通常情况下，你会发现这个元素在达到那么深之前是独一无二的。我怀疑（但同样，您需要衡量）在您的情况下，有许多重复项，这实际上会比前两个建议慢得多。（而且你会做更多的工作，因为我不知道任何现有的实现。

至于散列，几乎任何形式的线性全等散列都应该足够了：例如 FNV。此类哈希的大多数文档都与字符串（字符数组）有关，但它们往往适用于任何整数类型。我通常使用类似的东西：

template <typename ForwardIterator>
size_t
hash( ForwardIterator begin, ForwardIterator end )
{
    size_t results = 2166136261U 
    for ( ForwardIterator current = begin; current != end; ++ current ) {
        results = 127 * results + static_cast<size_t>( *current );
    }
    return results;
}

我选择 127 作为乘数主要是基于旧系统中的速度：乘以 127 比大多数其他给出良好结果的值要快得多。（我不知道这是否仍然是真的。但是乘法在很多机器上仍然是一个相对缓慢的操作，编译器会将 127 * x 转换为类似 x 的东西