是什么减慢了键上对的排序？
What is slowing down sorting the pairs on a key?
执行已接受的答案后的时间安排
更改 lambda 定义来自：
[] (String_pair x, String_pair y) {
return x.first < y.first;
}
至：
[] (const String_pair &x, const String_pair &y) {
return x.first < y.first;
}
将排序时间缩短到 0.23 秒。这仍然比使用 sort 稍慢，这并不奇怪。大多数具有相同键的字符串可能在第一个字符上已经不同，并且向量中所有元素中只有 1/8 的键至少出现一次。
原题
来自 "Programming Pearls" 的玩具问题，寻找英语中的字谜。这不是家庭作业，但您可以将问题视为家庭作业。为了解决这个问题，我实现了教科书解决方案：
- 计算字典中每个单词的签名（单词本身，按字符排序）
- 按签名排序（所有单词都是{signature, word}对）
- 输出相同签名且长度大于1的运行个
这当然是微不足道的，为了让它更有趣一点，我使用了 ICU 库 (with help from Roland Illig)，这样程序就不会因为非 ascii 字符而阻塞，并且可以在 say 中找到变位词芬兰语。
下面是完整的程序。诚然有点长，但要用更少的代码生成真实的测试输入输出并不容易。
$ cat find-anagrams.cpp
#include <iostream>
#include <algorithm>
#include <vector>
#include "unicode/ustream.h"
#include "unicode/unistr.h"
#include "unicode/schriter.h"
#include <chrono>
int main()
{
using String = icu::UnicodeString;
using String_pair = std::pair<String, String>;
using namespace std::chrono;
auto start = steady_clock::now();
// sign
std::vector<String_pair> ws;
String w;
while (std::cin >> w) {
String k{w};
auto n = k.length();
UChar *begin = k.getBuffer(n);
if (!begin) return 1;
std::stable_sort(begin, begin + n);
k.releaseBuffer(n);
ws.emplace_back(k, w);
}
auto sign_done = steady_clock::now();
// sort
std::stable_sort(ws.begin(), ws.end(),
[] (String_pair x, String_pair y) {
return x.first < y.first;
});
auto sort_done = steady_clock::now();
// squash
auto begin = ws.cbegin();
while (begin != ws.cend()) {
auto sig = begin->first;
auto run_end = std::partition_point(begin, ws.cend(),
[&sig] (String_pair x) {
return sig == x.first;
});
if ((run_end - begin) > 1) {
std::cout << begin->second;
++begin;
while (begin != run_end) {
std::cout << ' ' << begin->second;
++begin;
}
std::cout << '\n';
}
begin = run_end;
}
auto squash_done = steady_clock::now();
duration<double> time;
time = duration_cast<duration<double>>(sign_done - start);
std::cerr
<< "Read and calculate signatures:\n"
<< '\t' << time.count() << " sec\n";
time = duration_cast<duration<double>>(sort_done - sign_done);
std::cerr
<< "Sort by signatures:\n"
<< '\t' << time.count() << " sec\n";
time = duration_cast<duration<double>>(squash_done - sort_done);
std::cerr
<< "Squash and output:\n"
<< '\t' << time.count() << " sec\n";
time = duration_cast<duration<double>>(squash_done - start);
std::cerr
<< "Total:\n"
<< '\t' << time.count() << " sec\n";
return 0;
}
这是我正在使用的编译器：
$ g++ -v
Using built-in specs.
COLLECT_GCC=g++
COLLECT_LTO_WRAPPER=/usr/lib/gcc/x86_64-pc-linux-gnu/6.1.1/lto-wrapper
Target: x86_64-pc-linux-gnu
Configured with: /build/gcc/src/gcc/configure --prefix=/usr --libdir=/usr/lib --libexecdir=/usr/lib --mandir=/usr/share/man --infodir=/usr/share/info --with-bugurl=https://bugs.archlinux.org/ --enable-languages=c,c++,ada,fortran,go,lto,objc,obj-c++ --enable-shared --enable-threads=posix --enable-libmpx --with-system-zlib --with-isl --enable-__cxa_atexit --disable-libunwind-exceptions --enable-clocale=gnu --disable-libstdcxx-pch --disable-libssp --enable-gnu-unique-object --enable-linker-build-id --enable-lto --enable-plugin --enable-install-libiberty --with-linker-hash-style=gnu --enable-gnu-indirect-function --disable-multilib --disable-werror --enable-checking=release
Thread model: posix
gcc version 6.1.1 20160707 (GCC)
我是这样编译的：
g++ --std=c++0x -pedantic -Wall -O2 -std=c++14 -L/usr/lib -licui18n -licuuc -licudata -licuio find-anagrams.cpp -o cpp-find-anagrams
这就是我 运行 的方式，同时显示了时间：
./cpp-find-anagrams < clean-words | sort > cpp-result
Read and calculate signatures:
0.328156 sec
Stable sort by signatures:
0.512024 sec
Squash and output:
0.189494 sec
Total:
1.02967 sec
clean-words 是在 /usr/share/dict/words 中找到的单词，通过以下内容传递：
sed -n '/'"'"'s$/!p' | tr [:upper:] [:lower:] | sort --unique
换句话说，删除带撇号、所有大写和所有大写重复的单词。
我们观察到使用 std::stable_sort 和 lambda 进行排序的时间太长了。相比之下，如果我对整对进行排序，大约需要一半的时间。改变，在上面的程序中：
// sort
std::stable_sort(ws.begin(), ws.end(),
[] (String_pair x, String_pair y) {
return x.first < y.first;
});
至：
// sort
std::sort(ws.begin(), ws.end());
给出以下时间：
./cpp-find-anagrams < clean-words | sort > cpp-result
Read and calculate signatures:
0.338751 sec
Sort pairs:
0.216526 sec
Squash and output:
0.168725 sec
Total:
0.724002 sec
（0.51 秒到 0.22 秒）
当然，这两种排序的结果是一样的，因为输入文件中的单词已经排序了。值得注意的是，这不是 sort 与 stable_sort 的问题。使用 stable_sort（我知道这个输入是不必要的，但无论如何），所以改为：
// sort
std::stable_sort(ws.begin(), ws.end());
仅微调时间：
./cpp-find-anagrams < clean-words | sort > cpp-result
Read and calculate signatures:
0.334139 sec
Stable sort by signatures:
0.264751 sec
Squash and output:
0.180663 sec
Total:
0.779552 sec
（0.22 秒到 0.26 秒）
在试图弄清楚发生了什么时，我在 SWI-Prolog 中实现了相同的算法，并注意到内置的 sort 和 keysort 谓词显示了预期的差异，即, sort 需要比 keysort 更长的时间。使用以下实现（再次，完整程序）：
$ cat find-anagrams.pl
:- use_module(library(apply_macros)).
:- use_module(library(pairs)).
main :-
statistics(cputime, Start),
read_words(Ws),
sign_words(Ws, Signed),
statistics(cputime, Sign_done),
keysort(Signed, Sorted),
statistics(cputime, Sort_done),
squash(Sorted, Anagrams),
maplist(anagrams_string, Anagrams, Str),
atomics_to_string(Str, "\n", Output),
format(current_output, "~s~n", [Output]),
statistics(cputime, Squash_done),
format(user_error,
"Read and calculate signatures:\n\t~f sec~n\c
Sort by signatures:\n\t~f sec~n\c
Squash and output:\n\t~f sec~n\c
Total:\n\t~f sec\n",
[Sign_done - Start,
Sort_done - Sign_done,
Squash_done - Sort_done,
Squash_done - Start]),
halt.
main :- halt(1).
anagrams_string(Anagrams, Str) :-
atomics_to_string(Anagrams, " ", Str).
read_words(Ws) :-
read_string(current_input, _, Input),
split_string(Input, "\n", "", Ws).
sign_words(Ws, Signed) :-
maplist(string_codes, Ws, Ws_codes),
maplist(sort(0, @=<), Ws_codes, Ss_codes),
maplist(string_codes, Ss, Ss_codes),
pairs_keys_values(Signed, Ss, Ws).
squash(Sorted, Anagrams) :-
group_pairs_by_key(Sorted, Grouped),
groups_anagrams(Grouped, Anagrams).
groups_anagrams([], []).
groups_anagrams([_-Set|Rest], As) :-
length(Set, N),
( N > 1
-> As = [Set|As0]
; As = As0
),
groups_anagrams(Rest, As0).
这是我正在使用的 Prolog：
$ swipl -v
SWI-Prolog version 7.3.24 for x86_64-linux
我"compile"程序（为解释器创建一个"saved state"）：
swipl -q -O --goal=main -o swi-find-anagrams -c find-anagrams.pl
和运行它：
./swi-find-anagrams < clean-words | sort > swi-result
Read and calculate signatures:
0.928485 sec
Stable sort by signatures:
0.174832 sec
Squash and output:
0.183567 sec
Total:
1.286884 sec
当我改变时
keysort(Signed, Sorted),
和
sort(Signed, Sorted),
我得到以下增加的运行排序时间：
./swi-find-anagrams < clean-words | sort > swi-result
Read and calculate signatures:
0.935780 sec
Sort pairs:
0.269151 sec
Squash and output:
0.187508 sec
Total:
1.392440 sec
（0.17 到 0.27 秒）
排序的最终结果是一样的，但正如预期的那样，仅按键排序要快得多。
问题终于来了
我错过了什么？为什么做得越少成本越高？
我知道我可以使用地图来实现相同的最终结果，但了解是什么导致了这种相当大的减速仍然很有趣。
std::pair 有一个运算符<，它将首先比较第一个值，然后比较第二个值。因此，如果您使用默认比较函数，它会做完全相同的事情：比较第一个值。之后它很可能会停止，因为键值可能足以应用排序顺序。
lambda当然做同样的事情，但是string_pairs是按值传递的，额外的复制也需要一些时间。如果您通过引用传递它们，大概速度将相同。
关于SWI-Prolog版本，使用keysort/2时，排序算法只比较key。但是 sort/2 必须比较键，并且对于键相同的任何两对，它还必须比较值。 possible/likely（我还没有研究这些谓词的实现）keysort/2 以直接方式获取键（假定列表成员必须成对使用 (-)/2)中缀运算符），而 sort/2 必须能够处理任意项，对于复合项，这意味着在最坏的情况下使用通用代码遍历整个项。对于对（当然是复合项），这意味着比较 (-)/2 函子，发现它相同，然后下降到参数并比较它们。因此，与 keysort/2.
相比，比较次数总是两倍
Why is doing less costing more?
因为您正在做更多的事情——在 lamba 中多次复制所有字符串需要时间。如文档中所述 std::stable_sort:
O(N·log2(N)), where N = std::distance(first, last) applications of cmp.
所以每次调用 cmp 你都会复制 4 个字符串。将参数类型更改为常量引用并重新测量。
执行已接受的答案后的时间安排
更改 lambda 定义来自：
[] (String_pair x, String_pair y) {
return x.first < y.first;
}
至：
[] (const String_pair &x, const String_pair &y) {
return x.first < y.first;
}
将排序时间缩短到 0.23 秒。这仍然比使用 sort 稍慢，这并不奇怪。大多数具有相同键的字符串可能在第一个字符上已经不同，并且向量中所有元素中只有 1/8 的键至少出现一次。
原题
来自 "Programming Pearls" 的玩具问题，寻找英语中的字谜。这不是家庭作业，但您可以将问题视为家庭作业。为了解决这个问题，我实现了教科书解决方案：
- 计算字典中每个单词的签名（单词本身，按字符排序）
- 按签名排序（所有单词都是{signature, word}对）
- 输出相同签名且长度大于1的运行个
这当然是微不足道的，为了让它更有趣一点，我使用了 ICU 库 (with help from Roland Illig)，这样程序就不会因为非 ascii 字符而阻塞，并且可以在 say 中找到变位词芬兰语。
下面是完整的程序。诚然有点长，但要用更少的代码生成真实的测试输入输出并不容易。
$ cat find-anagrams.cpp
#include <iostream>
#include <algorithm>
#include <vector>
#include "unicode/ustream.h"
#include "unicode/unistr.h"
#include "unicode/schriter.h"
#include <chrono>
int main()
{
using String = icu::UnicodeString;
using String_pair = std::pair<String, String>;
using namespace std::chrono;
auto start = steady_clock::now();
// sign
std::vector<String_pair> ws;
String w;
while (std::cin >> w) {
String k{w};
auto n = k.length();
UChar *begin = k.getBuffer(n);
if (!begin) return 1;
std::stable_sort(begin, begin + n);
k.releaseBuffer(n);
ws.emplace_back(k, w);
}
auto sign_done = steady_clock::now();
// sort
std::stable_sort(ws.begin(), ws.end(),
[] (String_pair x, String_pair y) {
return x.first < y.first;
});
auto sort_done = steady_clock::now();
// squash
auto begin = ws.cbegin();
while (begin != ws.cend()) {
auto sig = begin->first;
auto run_end = std::partition_point(begin, ws.cend(),
[&sig] (String_pair x) {
return sig == x.first;
});
if ((run_end - begin) > 1) {
std::cout << begin->second;
++begin;
while (begin != run_end) {
std::cout << ' ' << begin->second;
++begin;
}
std::cout << '\n';
}
begin = run_end;
}
auto squash_done = steady_clock::now();
duration<double> time;
time = duration_cast<duration<double>>(sign_done - start);
std::cerr
<< "Read and calculate signatures:\n"
<< '\t' << time.count() << " sec\n";
time = duration_cast<duration<double>>(sort_done - sign_done);
std::cerr
<< "Sort by signatures:\n"
<< '\t' << time.count() << " sec\n";
time = duration_cast<duration<double>>(squash_done - sort_done);
std::cerr
<< "Squash and output:\n"
<< '\t' << time.count() << " sec\n";
time = duration_cast<duration<double>>(squash_done - start);
std::cerr
<< "Total:\n"
<< '\t' << time.count() << " sec\n";
return 0;
}
这是我正在使用的编译器：
$ g++ -v
Using built-in specs.
COLLECT_GCC=g++
COLLECT_LTO_WRAPPER=/usr/lib/gcc/x86_64-pc-linux-gnu/6.1.1/lto-wrapper
Target: x86_64-pc-linux-gnu
Configured with: /build/gcc/src/gcc/configure --prefix=/usr --libdir=/usr/lib --libexecdir=/usr/lib --mandir=/usr/share/man --infodir=/usr/share/info --with-bugurl=https://bugs.archlinux.org/ --enable-languages=c,c++,ada,fortran,go,lto,objc,obj-c++ --enable-shared --enable-threads=posix --enable-libmpx --with-system-zlib --with-isl --enable-__cxa_atexit --disable-libunwind-exceptions --enable-clocale=gnu --disable-libstdcxx-pch --disable-libssp --enable-gnu-unique-object --enable-linker-build-id --enable-lto --enable-plugin --enable-install-libiberty --with-linker-hash-style=gnu --enable-gnu-indirect-function --disable-multilib --disable-werror --enable-checking=release
Thread model: posix
gcc version 6.1.1 20160707 (GCC)
我是这样编译的：
g++ --std=c++0x -pedantic -Wall -O2 -std=c++14 -L/usr/lib -licui18n -licuuc -licudata -licuio find-anagrams.cpp -o cpp-find-anagrams
这就是我 运行 的方式，同时显示了时间：
./cpp-find-anagrams < clean-words | sort > cpp-result
Read and calculate signatures:
0.328156 sec
Stable sort by signatures:
0.512024 sec
Squash and output:
0.189494 sec
Total:
1.02967 sec
clean-words 是在 /usr/share/dict/words 中找到的单词，通过以下内容传递：
sed -n '/'"'"'s$/!p' | tr [:upper:] [:lower:] | sort --unique
换句话说，删除带撇号、所有大写和所有大写重复的单词。
我们观察到使用 std::stable_sort 和 lambda 进行排序的时间太长了。相比之下，如果我对整对进行排序，大约需要一半的时间。改变，在上面的程序中：
// sort
std::stable_sort(ws.begin(), ws.end(),
[] (String_pair x, String_pair y) {
return x.first < y.first;
});
至：
// sort
std::sort(ws.begin(), ws.end());
给出以下时间：
./cpp-find-anagrams < clean-words | sort > cpp-result
Read and calculate signatures:
0.338751 sec
Sort pairs:
0.216526 sec
Squash and output:
0.168725 sec
Total:
0.724002 sec
（0.51 秒到 0.22 秒）
当然，这两种排序的结果是一样的，因为输入文件中的单词已经排序了。值得注意的是，这不是 sort 与 stable_sort 的问题。使用 stable_sort（我知道这个输入是不必要的，但无论如何），所以改为：
// sort
std::stable_sort(ws.begin(), ws.end());
仅微调时间：
./cpp-find-anagrams < clean-words | sort > cpp-result
Read and calculate signatures:
0.334139 sec
Stable sort by signatures:
0.264751 sec
Squash and output:
0.180663 sec
Total:
0.779552 sec
（0.22 秒到 0.26 秒）
在试图弄清楚发生了什么时，我在 SWI-Prolog 中实现了相同的算法，并注意到内置的 sort 和 keysort 谓词显示了预期的差异，即, sort 需要比 keysort 更长的时间。使用以下实现（再次，完整程序）：
$ cat find-anagrams.pl
:- use_module(library(apply_macros)).
:- use_module(library(pairs)).
main :-
statistics(cputime, Start),
read_words(Ws),
sign_words(Ws, Signed),
statistics(cputime, Sign_done),
keysort(Signed, Sorted),
statistics(cputime, Sort_done),
squash(Sorted, Anagrams),
maplist(anagrams_string, Anagrams, Str),
atomics_to_string(Str, "\n", Output),
format(current_output, "~s~n", [Output]),
statistics(cputime, Squash_done),
format(user_error,
"Read and calculate signatures:\n\t~f sec~n\c
Sort by signatures:\n\t~f sec~n\c
Squash and output:\n\t~f sec~n\c
Total:\n\t~f sec\n",
[Sign_done - Start,
Sort_done - Sign_done,
Squash_done - Sort_done,
Squash_done - Start]),
halt.
main :- halt(1).
anagrams_string(Anagrams, Str) :-
atomics_to_string(Anagrams, " ", Str).
read_words(Ws) :-
read_string(current_input, _, Input),
split_string(Input, "\n", "", Ws).
sign_words(Ws, Signed) :-
maplist(string_codes, Ws, Ws_codes),
maplist(sort(0, @=<), Ws_codes, Ss_codes),
maplist(string_codes, Ss, Ss_codes),
pairs_keys_values(Signed, Ss, Ws).
squash(Sorted, Anagrams) :-
group_pairs_by_key(Sorted, Grouped),
groups_anagrams(Grouped, Anagrams).
groups_anagrams([], []).
groups_anagrams([_-Set|Rest], As) :-
length(Set, N),
( N > 1
-> As = [Set|As0]
; As = As0
),
groups_anagrams(Rest, As0).
这是我正在使用的 Prolog：
$ swipl -v
SWI-Prolog version 7.3.24 for x86_64-linux
我"compile"程序（为解释器创建一个"saved state"）：
swipl -q -O --goal=main -o swi-find-anagrams -c find-anagrams.pl
和运行它：
./swi-find-anagrams < clean-words | sort > swi-result
Read and calculate signatures:
0.928485 sec
Stable sort by signatures:
0.174832 sec
Squash and output:
0.183567 sec
Total:
1.286884 sec
当我改变时
keysort(Signed, Sorted),
和
sort(Signed, Sorted),
我得到以下增加的运行排序时间：
./swi-find-anagrams < clean-words | sort > swi-result
Read and calculate signatures:
0.935780 sec
Sort pairs:
0.269151 sec
Squash and output:
0.187508 sec
Total:
1.392440 sec
（0.17 到 0.27 秒）
排序的最终结果是一样的，但正如预期的那样，仅按键排序要快得多。
问题终于来了
我错过了什么？为什么做得越少成本越高？
我知道我可以使用地图来实现相同的最终结果，但了解是什么导致了这种相当大的减速仍然很有趣。
std::pair 有一个运算符<，它将首先比较第一个值，然后比较第二个值。因此，如果您使用默认比较函数，它会做完全相同的事情：比较第一个值。之后它很可能会停止，因为键值可能足以应用排序顺序。
lambda当然做同样的事情，但是string_pairs是按值传递的，额外的复制也需要一些时间。如果您通过引用传递它们，大概速度将相同。
关于SWI-Prolog版本，使用keysort/2时，排序算法只比较key。但是 sort/2 必须比较键，并且对于键相同的任何两对，它还必须比较值。 possible/likely（我还没有研究这些谓词的实现）keysort/2 以直接方式获取键（假定列表成员必须成对使用 (-)/2)中缀运算符），而 sort/2 必须能够处理任意项，对于复合项，这意味着在最坏的情况下使用通用代码遍历整个项。对于对（当然是复合项），这意味着比较 (-)/2 函子，发现它相同，然后下降到参数并比较它们。因此，与 keysort/2.
Why is doing less costing more?
因为您正在做更多的事情——在 lamba 中多次复制所有字符串需要时间。如文档中所述 std::stable_sort:
O(N·log2(N)), where N = std::distance(first, last) applications of cmp.
所以每次调用 cmp 你都会复制 4 个字符串。将参数类型更改为常量引用并重新测量。