使用什么数据结构？ （哈希映射 vs. trie vs.？）

Question

我有一个 C 函数，可以生成大约 600 万个唯一的数组。这些数组每个总是有 17 个元素，每个元素都是 0 到 16 之间的整数。我还有该函数的一个稍微修改过的版本，它也将生成大约 600 万个相同类型的唯一数组。我的问题是第二个生成的结果比第一个少大约 45,000 个结果，我想看看这些结果是什么。

所以我的方法是简单地存储第二个函数的所有结果（计算器告诉我这不应该超过 400 mb，这很好地保留在内存中），然后查找第一个函数的结果，打印出那些不存在。

假设一般方法有意义（如果没有，请告诉我），我正在寻找一个合适的数据结构（最好是用 C 语言实现），它可以容纳大约 600 万个独特的排列

[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]

（或其某些转换）和然后对它们执行快速成员资格测试。正如标题所说，我确实对哪些数据结构可以完成这项工作有一些怀疑，但我不确定尝试或哈希图是最佳选择。

这是一种用于检测另一个算法中的缺陷的算法，而不是在生产中使用的算法。我有兴趣以一种能够以人类术语相对较快地编码并返回结果的方式来完成此操作，不一定要缩短几毫秒，因此存在能够完成大部分工作的易于理解的库绝对是一个优势。

Answer 1

最优性在某种程度上取决于排列的分布方式以及插入与搜索的比率。由于您不关心最优性，而只是想要一种简单的方法来检验假设，而无需整夜等待结果，我的直觉告诉我：

整数 [0,16] 可以表示为五位数，因此其中 17 个可以表示为 85 位（11 字节）二进制字符串。因此，您只需使用可用于存储排序/散列字符串集并对其进行成员资格测试的众多库之一即可完成。它不会像调整后的 trie 那样快或缓存一致，但它足以在几秒钟内处理完 66mb 的数据，并且您将在午餐时完成。

如果没有这样的库方便使用，并且您必须从头开始工作，我只需制作一个排序的字符串列表，然后通过二进制搜索进行成员资格测试。其结果类似于 O( n log n + m( n log n ) ) = O( 2×mn log n ) eg 二次时间为 m→n。如果这仅在生产过程中作为离线作业运行一两次，那可能就足够了；如果您每天要多次执行此操作，我会担心缓存局部性并使用 trie 或 B 树。

Answer 2

我认为你需要权衡在 C 中这样做的价值以避免沟通。

我会将 C 中的每个数组作为空格分隔的整数逐行打印。然后从文件中加载该文件以创建一组字节数组，如下所示（F# 代码）：

let load file =
  System.IO.File.ReadAllLines file
  |> Array.Parallel.map (fun s -> s.Split[|' '|] |> Array.map (int >> byte))
  |> set

然后计算两个文件之间的设置差异，如下所示：

load "file1.txt" - load "file2.txt"

这可能需要几分钟才能运行。

Answer 3

保持简单：

• 将每个排列表示为 17 字节的数组
• 将整个较小的集合存储为上述数组 (17*6M < 98MB)
• 按字典顺序对其进行排序，以便您的 qsort 比较器> 只需调用 memcmp(left, right, 17)
• 对于较大集合中的每个元素，使用二分切在排序数组中查找它（使用与之前，这次是使用 bsearch）。

最后两个步骤中的每一步都将执行 6M * log(6M) 量级的比较，大约为 138M。这可能仍然少于编写代码所需的时间。这并不长，因为一切都很简单:-)

Answer 4

取决于您的情况，哪一种会获得更好的内存性能。另外，您使用什么哈希函数，如何解决冲突等。如何查看 哈希数组映射 Trie ( HAMT）

Answer 5

@Steve Jessop您可以在线性时间内完成最后一步，通过删除我们正在搜索的数组中不需要的值来进行更智能的搜索：

让我们假设 n 是 A 的大小，m 是 B 的大小，

int counter_A = 0;
int counter_B = 0;
int counter_C = 0;
while(counter_A != n){
    int temp = A[counter_A];
    counter_A++;
    //Removes all elements at the beginning of B since they are inferior than all
    //elements in A because they are inferior than the minimum of A
    for(;counter_B < m && B[counter_B] < temp;counter_B++);
    if((counter_B < m && B[counter_B] > temp) || counter_B == m){
        C[counter_C] = temp;
        counter_C++;
    }
}

这应该在 O( n+m) 时间，因为算法的每一步都执行至少一次计数器增量。

Answer 6

a) 创建一个包含两个 64 位 int 的结构

b) 因为每个结果有 17 个元素，所以将前 8 个元素相乘并将结果放入第一个 int，将其他 7 相乘并将结果放入第二个 int。

c) 创建一个运算符 <对于您的结构

d) 创建一组结构并插入第一次运行的所有结果

e) 迭代第二次运行结果并执行 set::find()

class Result
{
public:
    Result(int arr[17]);              // Fill-in _n1 and _n2

    bool operator < (const Result& r) const  // Compare
    { 
        if (_n1 != r._n1)
           return _n1 < r._n1;
        return _n2 < r._n2;
    }

protected:
    int _n1;
    int _n2;
};

typedef std::set< Result > SetResult;
SetResult setResult;

Edwin