arrays - 这个搜索序列叫什么（如果它有名字）？

Question

一些背景：我想改进一个稳定的线性搜索插入函数到一个值数组中，用于排序算法。假设我们有一个由 16 个递增值组成的数组（不管它们是什么 afaik，为了讨论起见，我们只说它们是 1 到 16 包括在内）。

我从小的方面（1）开始这样做。

通常的方法是二分搜索或指数搜索。

然而，二分搜索有点失败，因为在许多情况下，如果值接近边缘，它可能会被传统的线性搜索击败。对于二分搜索，这很容易说明——如果我们尝试插入 0，我们将不得不比较 4 个值（8、4、2、1），而从 1 端开始的线性搜索只需要 1 个比较（ 1); 随着数组大小的增加，情况会变得更糟。

如果我们尝试典型的指数搜索，假设尝试插入 6。我们必须比较 6 个值 (1,2,4,8,6,7)，而线性搜索需要 7 次比较 (1,2,3, 4,5,6,7)。指数搜索不是一个伟大的胜利（只为我们节省了 1 个比较）。

现在，让我们考虑这个（对我来说未知的）算法。我们从指数搜索开始。但是，当我们跳过目标时，我们不会像正常的指数搜索那样以 2 的幂次跳回分解为二进制搜索，而是从前一个值“重新启动”指数搜索。所以，如果我们尝试插入 13，我们会比较 1，然后是 3，然后是 7，然后是 14——但是 14 大于 13。所以我们从 8 重新开始，然后是 10，最后是 13。我们总共比较了 7 个值(1,3,7,8,10,13,14)，而线性搜索将与 13 (1 到 13) 进行比较。这为我们节省了 5 次比较。

生成此搜索的一些粗略的递归伪代码将是（我认为这是正确的，但我花了很长时间才完成，如果您有更好/更清晰的版本，或者我犯了一个错误，请告诉我）-

array[]=range(1,16)
inserts+=1
insertpos(16,array,0,array.length(),inserts%2)

int insertpos(searchval,array[],startpos,rbound,rand)
  lasti = -1
  pos = startpos-1
  //edge case for the array being 0 length or we need to insert at 0
  if startpos == rbound return startpos
  for (i=1,1,i*=2)
    //starting at pos 0
    pos += i
    //we need to wrap pos in case we go out of bounds
    if pos >= rbound
      pos = rbound - 1
    //make the comparison
    comp = searchval >= array[pos]
    //if we are next to the right bound (value already checked)
    //and the search value is still equal or greater, done.
    if comp && (pos+1 == rbound) return rbound
    //eliminating a pathological case by going to pos 1 half the time instead of pos 2
    if i == rand
      insertpos(searchval,array,startpos+1,rbound,0)
    //if we know the search value is less than the current position, we have gone too far
    //need to start again from the lasti+1
    //don't want to check pos again, so that's new right bound.
    if !comp
      insertpos(searchval,array,startpos+lasti+1,pos)
    lasti = i

这是什么东西，以前研究过吗？进一步的问题：当我们走向无穷大时，这是否比常规指数搜索更好？是否有一些不是非常复杂的更好的算法（比这个或指数搜索更好）？我不知道足够的数学来对此进行复杂性分析。

编辑：我注意到一个病态的情况，我们试图将连续递减的值插入到列表中，并且列表包含的值低于所有值。在这种情况下，我们必须每次进行 3 次比较，而线性搜索每次只需要 2 次比较。（因为我们每次都跳过位置1，第二位置）

EDIT2：我认为上面的答案是，50% 的时间，我们应该从 pos 1 而不是 pos 0 开始。这意味着我们为 pos 0 支付 1.5 倍的费用，但为 pos 1 支付 0.5 倍的费用，所以它应该均匀。

EDIT3：关于上述情况，我们可能不想为 pos 0 支付 1.5 倍的费用，因为这是很有可能的顺序数据。所以我们应该总是先评估 pos 0，然后一半时间评估 pos 1，另一半时间评估 pos 2。我想我修好了...

EDIT4：我现在已经阅读了一些关于指数/疾驰搜索复杂性的论文（尤其是 Jon Bentley 和 Andrew Chi-Chih Yao 于 1976 年发表的一篇论文）。似乎“正常”指数搜索的指数搜索部分的复杂性是 log(p)，其中 p 是我们找到的最远元素的位置。那么，二分查找的复杂度就是众所周知的log(n)。所以看起来“正常”指数搜索的组合复杂度是 log(p)+log(s)，其中 s 是 p 和“最后一跳”之间的元素数，所以 s=n-pos(lasthop) . 我们知道 log(p) 会增长得更快，因为 s 总是小于 p，所以我认为总体上它仍然是 O log(p)。但是，如果我们执行我给出的“重复驰骋”功能，那么它将是一系列 log(p)，其中 p 迅速缩小（因为最后一跳和 p 之间的距离迅速缩小），而二进制搜索的 log(n-pos(lasthop))。这就是数学超出我的能力的地方。希望这是有道理的。

前面提到的 1976 年的大部分论文对我来说都是胡言乱语，我不确定他们是否考虑了我在 OP 中给出的“重复疾驰”功能。

Timsort 使用“正常”指数搜索算法（在最后一段分解为二进制搜索），它在合并子例程中具有疾驰功能。当在一系列数字上重复使用时，奔腾搜索的性能可能优于二分搜索，因为我们的搜索空间只有连续的 p，而不是整个剩余的 n。我想知道我在 OP 中给出的函数是否会更好——我认为代码至少更简洁一些，因为我们只有一个递归函数（可以很容易地变成一个交互函数），而不是一个单独的二进制函数搜索。但是可惜 Timsort 也使用二分搜索函数作为其插入排序的子程序，所以这可能是一个有争议的问题。

另一个有趣的特性可能是当最远比较的元素 p 和“最后一跳”之间的距离足够小时，或者当我们达到外部边界时，恢复到二进制搜索。然后可以调整增长率，而不是 2^i，我们可以有 4^i，甚至 8^i。我读过的一篇论文中提到了这种策略。这如何影响平均性能，我真的不知道 - 可能还有其他一些最佳数字基数，比如斐波那契数列，或者使用 e^i，或者更奇特的东西。

这是Vincent Jugé 和 Ghazal Khalighinejad最近发表的另一篇有趣的论文（2020 年！）。

但与往常一样，证据可能就在布丁中。我应该做的工作是在现实世界的数据上进行测试并使用它。

感谢您阅读这堵文字墙，希望它能激发一些创造力。

标签： arrayssortingsearchcomplexity-theory