3

我有一个值不断增加的大数组 - 像这样：

array = [0, 1, 6, 6, 12, 13, 22, ..., 92939, 92940]

我想在上面使用插值搜索算法。数组的大小是可变的，新元素被添加到数组的末尾。

我需要找到某个元素的索引，我们称它为 X。

Y = find(X in array)

Y 必须是数组中元素的索引，这样 array[Y] >= X find可以使用二进制搜索来实现，但由于某些复杂的原因，我想使用插值搜索来实现它。插值搜索试图通过查看数组的边界来猜测 X 的正确位置。如果第一个数组值是 0，最后一个是 100，我想找到值 25 的位置，如果数组长度是 1000，我需要先查看索引 250 处的值。如果数组的值是均匀分布的，这很有吸引力。但如果它们分布不均匀，插值搜索的工作速度可能比二分搜索慢（可能有一些优化）。

在这种情况下，我正在尝试使用Count-Min Sketch数据结构来加快搜索速度。当我将新元素附加到数组时，我只是将一些数据添加到 count-min 草图数据结构中。

Z = 1005000 
elements_before_Z = len(array)
array.append(Z)
count_min_sketch.add(Z, elements_before_Z)  
# Z is the key and elenents_before_Z - is count

使用这种方法，我可以大致猜测搜索到的元素 X 的位置。如果猜测正确，这可能会导致搜索速度加快，但我遇到了一些问题。

  1. 我不知道 X 是否在数组中并且我count_min_sketch已经看到了这个值。如果是这种情况，我可以从数据结构中获得正确的值count_min_sketch。如果不是 - 我将得到 0 或其他值（最坏的情况）。

  2. 碰撞。如果我的对象已经看到了值 X，那么count_min_sketch我会得到正确的值或更大的值。如果 count min sketch 用于计算文档中的单词出现次数 - 这不是问题，因为碰撞很少见并且错误小于或等于碰撞次数（它通常像这样使用：count_min_sketch.add(Z, 1)）。就我而言，每次碰撞都可能导致大错误，因为我通常为每个键添加大量数字。

是否可以以这种方式使用 count-min 草图（每次添加大量条目）？

4

0 回答 0