为什么STL的next_permutation实现不使用二叉搜索？

Question

我是在阅读了std:：next_premotion实现说明的优秀答案后提出这个问题的。请参阅该帖子以了解STL使用的算法的解释，但我会在这里复制代码供您参考

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
template<typename It>
bool next_permutation(It begin, It end)
{
if (begin == end)
return false;
It i = begin;
++i;
if (i == end)
return false;
i = end;
--i;
while (true)
{
It j = i;
--i;
if (*i < *j)
{
It k = end;
while (!(*i < *--k))
/* pass */;
iter_swap(i, k);
reverse(j, end);
return true;
}
if (i == begin)
{
reverse(begin, end);
return false;
}
}
}
int main()
{
vector<int> v = { 1, 2, 3, 4 };
do
{
for (int i = 0; i < 4; i++)
{
cout << v[i] << " ";
}
cout << endl;
}
while (::next_permutation(v.begin(), v.end()));
}

让我们来看看这个部分

It k = end;
while (!(*i < *--k))
/* pass */;
iter_swap(i, k);

根据我的理解，这种线性扫描可以用二进制搜索来代替，因为通过构造，i之后的元素已经按降序(或者在重复元素的情况下，按非升序(排列。假设我们有一个布尔数组，其项为每个j <= idx < end的*idx > *i，那么我所需要做的就是找到其项为True的最大索引。这样的索引必须存在，因为我们有*j > *i，这意味着数组以True开头。

我不知道足够的C++来自信地提供一个工作示例，但这里是在Rust中next_permutation的完整实现。如果你不知道Rust，那么下面的伪代码应该能很好地理解我所说的"二进制搜索"；。(是的，它是Python，可读性足以称为伪代码：(

from typing import List
def bisearch(last: List[bool]) -> int:
p, q = 0, len(lst) - 1
while p + 1 < q:
mid = (p + q) // 2
if lst[mid]:
p = mid
else:
q = mid
return q if lst[q] else q - 1

if __name__ == '__main__':
for pos_count in range(1, 5):
for neg_count in range(5):
lst = [True] * pos_count + [False] * neg_count
assert bisearch(lst) == pos_count - 1

问题：为什么STL的next_permutation实现不使用二进制搜索？我知道查找i需要O(n)，而O(n) + O(n)和O(n) + O(ln(n))都是O(n)，但实际上，二进制搜索至少应该略微提高性能？

Answer 1

@RichardCritten指出，我们拥有更好的算法复杂性并不意味着执行速度更快。此外，实现有点复杂。

下面，我们对中间部分的原始算法进行了非常简单的修改。

原始代码：

if (*i < *j)
{
It k = end;

while (!(*i < *--k))
/* pass */;

iter_swap(i, k);
reverse(j, end);
return true;
}

简单二进制方法

if (*i < *j)
{
auto test = std::lower_bound(std::make_reverse_iterator(end),
std::make_reverse_iterator(i), *i);

std::iter_swap(i, test);
std::reverse(j, end);
return true;
}

我们使用std:：lower_bound和std:：make_reverse_iterator，因为给定的范围是按降序排列的。

应该注意的是，这种实现并不是完全证明，当重复时也不起作用。其中一个要点是证明，即使对于简单的案例，最初的实现也更快。

下面是一个实时视频示例，演示了每种方法的速度。在我们的测试中，我们测量了每种方法生成100次10! = 3,628,800排列所需的时间。

您会注意到，线性实现的速度几乎是它的两倍。