实现接受的答案后的时间安排
从以下位置更改 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 稍慢，这并不奇怪。大多数具有相同键的字符串可能在第一个字符上已经不同，并且 vector 中所有元素中只有 1/8 的键至少出现一次。
原始问题
“Programming Pearls”中的一个玩具问题，寻找英语中的字谜。这不是家庭作业，但您可以将问题视为家庭作业。为了解决这个问题，我实现了教科书解决方案:
- 计算字典中每个单词的签名(单词本身，按字符排序)
- 按签名排序(所有单词都是{signature, word} 对)
- 输出具有相同签名且长度大于 1 的游程。
这当然是微不足道的，为了让它更有趣一点，我使用了 ICU 库 ( with help from Roland Illig )，这样程序就不会因为非 ascii 字符而阻塞，并且可以找到芬兰语中的字谜。
下面是完整的程序。诚然它有点长，但要用更少的代码生成真实的测试输入和输出并不容易。
$ 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).
这是我正在使用的序言:
$ swipl -v
SWI-Prolog version 7.3.24 for x86_64-linux
我“编译”程序(为解释器创建一个“保存状态”):
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 秒)
排序的最终结果是相同的，但正如预期的那样，仅按键排序要快得多。
最后的问题
我错过了什么？为什么做得越少成本越高？
我知道我可以使用 map 来实现相同的最终结果，但了解是什么导致了这种相当大的减速仍然很有趣。
最佳答案
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 个字符串。将参数类型更改为常量引用并重新测量。
关于c++ - 是什么减慢了键上对的排序？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/38747694/