什么减慢了对密钥对的排序？

Question

实施接受的答案后的时间安排

从以下位置更改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的所有元素具有不止一次出现的键.

原来的问题

来自"编程珍珠"的玩具问题,找到英语中的字谜.这不是家庭作业,但你可以把问题视为好像.为了解决这个问题,我实施了教科书解决方案:

1. 计算字典中每个单词的签名(单词本身,按字符排序)
2. 按签名排序(所有单词都在{signature,word}对中)
3. 输出具有相同签名且长度大于1的运行.

这当然是微不足道的,为了让我更有趣,我使用了ICU库(在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秒)

当然,这两种排序会产生相同的结果,因为输入文件中的单词已经排序.值得注意的是,这不是一个sortvs 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

我"编译"程序(为解释器创建一个"保存状态"):

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秒)

排序的最终结果是相同的,但是,正如预期的那样,仅按键排序要快得多.

最后的问题

我错过了什么？为什么减少成本更低？

我知道我可以使用地图来获得相同的最终结果,但知道导致这种显着减速的原因仍然很有趣.

Answer 1

为什么减少成本更低？

因为你做得更多 - 在lamba中多次复制所有字符串需要时间.如文档std :: stable_sort中所述:

O(N·log2(N)),其中N = std :: distance(first,last)cmp的应用.

因此,对于每次调用cmp,您都要复制4个字符串.将参数类型更改为const引用并重新测量.