1

我在密码本中有一堆 8 位值（大约 200 个）。

我的程序将生成一个 8 位值以响应输入，我需要在码本中找到所有（甚至第一个是有帮助的）具有相同位集的匹配项。未设置的位无关紧要。

您能想出一种最佳方法来 a) 存储和 b) 搜索码本以查找所有匹配项吗？我有一个标准的线性搜索，但当然效率很低。

非常感谢...

阿克万

4

5 回答 5

2

当然，虽然空间效率不是很高，但您当然可以预先计算所有 256 位模式的匹配。您将拥有一个由 256 个列表组成的数组，每个列表将包含码本中设置了这些位的每个代码。

您可以获得 256 个字节（11 个内存字）的第一个匹配项。

初始化：

u_int8_t bitpatterns[256];
memset(bitpatterns,0,sizeof(bitpatterns));

for(x=sizeof(codebook)-1;x>=0;x--)
  for(y=0;y<256;y++)
    if (y&codebook[x] == y)
      bitpatterns[y] = x;

抬头：

codeword = codebook[bitpatterns[input]];
于 2011-06-29T17:24:58.143 回答
1

如果您只进行 8 位查找，预先计算所有答案然后将它们存储在 256 条目表中将是微不足道的。这样，您将获得恒定的时间查询，并且内存存储量仅为 256 个条目。

于 2011-06-29T17:24:16.477 回答
1

一种优化可能是将代码存储在不同的存储桶中，具体取决于设置的位数。当您查找代码时，您只需查看 1/2 的代码（平均而言，如果代码分布均匀）。这是一个非常简单的优化，但算法的复杂度保持不变（O(n)）。根据设置的位数对单个数组进行排序将使您能够进行类似的优化，而无需将代码存储在存储桶中。

旁注：我认为 200 是一个非常小的数字，并且我认为无论您如何优化它，除非您进行大量查找，否则您不会看到线性方法的性能有太大变化。但我猜这不是这个练习的重点......

于 2011-06-29T17:06:59.240 回答
0

如果我理解，您是说如果响应只设置了 1、3、5 位，那么您希望码本中的所有代码都设置了标志 1、3、5 并且您不关心 2、4、6 位,7,8。

如果是这样，这是您的伪代码：

matchingCodes = new List<Code>
foreach(code in codebook)
    if((response & code) == response) matchingCodes.add(code);
于 2011-06-23T17:32:56.740 回答
0

我发布了另一个答案，因为我得到了一个新的（更好的建议）：

  1. 按值对码本进行排序
  2. 对于您正在查找的每个代码，首先进行二进制下限搜索以找到第一个可能的匹配项（任何小于您正在查找的值都不能成为匹配项）
  3. 搜索从第一个可能的匹配到最后一个元素的范围，看看是否有任何匹配。

该算法仍然是线性的，但是通过 O(log N) 查找来截断（希望）大多数值。查找小值仍然很昂贵，查找大值会更便宜。

您也可以使用布隆过滤器进行初始搜索以截断大多数情况，并对其余情况进行线性搜索。过滤器可能有误报，因此当过滤器返回 true 时，您必须进行线性搜索。这种数据结构要求您拥有大量独立的散列函数（例如，基于设置的位数、所有设置位的乘积、奇数与偶数、数字本身等）。如果您希望仅偶尔找到代码，这可能是一个很好的优化（如果过滤器返回 false，则保证代码不在代码簿中）。但是，我怀疑这比实际优化更具理论意义。

于 2011-06-29T18:35:59.193 回答