O(N)排列的识别

Question

此答案通过比较其内容来确定两个字符串是否是排列.如果它们包含相同数量的每个字符,则它们显然是排列.这是在O(N)时间内完成的.

我不喜欢这个答案,因为它改变了is_permutation设计目的.那说,is_permutation有一个复杂的:

在谓词的大多数O(N ²)应用中,或者如果序列已经相等则恰好为N,其中N=std::distance(first1, last1)

所以我不能提倡使用is_permutation比手动旋转算法慢几个数量级的地方.但是,该标准的实施者肯定不会错过这种明显的改进吗？那么为什么是is_permutation O(N ²)？

Answer 1

is_permutation适用于几乎所有数据类型.链接中的算法仅适用于具有少量值的数据类型.

这与std::sortO(N log N)的原因相同,但计数排序为O(N).

Answer 2

是我写了那个答案.

当字符串value_type是char,查找表中所需的元素数是256.对于双字节编码,65536.对于四字节编码,查找表将有超过40亿条目,可能大小为16 GB!其中大部分都是未使用的.

所以首先要认识到即使我们将类型限制为char和wchar_t,它仍然可能是站不住脚的.同样,如果我们想要对is_permutation类型序列进行处理int.

我们可以对std::is_permutation<>1或2字节的整数类型进行专门化.但这有点让人回想起std::vector<bool>并不是每个人都认为回想起来是个好主意.

我们也可以使用基于的查找表std::map<T, size_t>,但这很可能是分配量很大,因此它可能不是性能获胜(或者至少,并非总是如此).但是,为了进行详细比较,可能值得实施一个.

总之,我没有过错的C++标准不包括高性能版本is_permutation的char.首先,因为在现实世界中我不确定它是模板的最常见用法,其次是因为STL不是算法的全部和最终,特别是在领域知识可用于加速特殊计算的情况下案例.

如果事实证明is_permutation了char是相当普遍在野外,C++库实现者将自己的权利范围内为其提供专业化.