🧑🏽‍🤝‍🧑🏼 🍲 👏 ロムトの勝利の帰還 😸 🐁 ◾️

アメリカ、テキサス、オースティン、コンチネンタルクラブ

1987年1月5日日曜日

「招待してくれてありがとう、ロムトさん。もうすぐイギリスに帰るので、間に合いました。

「私と会うことに同意してくれてありがとう、ミスター…サー…チャールズ…アンソニー・リチャード…ホア。これは私にとって大きな名誉です。連絡方法すらわかりません。騎士の称号はありますか？

「私をトニーと呼んでください。よろしければ、ニコと呼んでください。

一見すると、これはよくある光景です。2人がウイスキーを楽しんでいます。しかし、興味をそそる詳細は注意深い観察者に明らかにされます。まず第一に-ナイフで切ることができる緊張。

英国人の意図的なカジュアルさを備えた完璧に仕立てられたスリーピースのスーツを着たトニー・ホアは、お茶と同じくらいイギリス人でした。彼がグラスからすすった彼の顔の謙虚な表情は、一言も言わずに、バーボンとスコッチの間の論争で彼の意見を表明した。ニコ・ロムトの反対側に座っているのは、彼の正反対を表しています。ジーンズを着て、ウイスキーとコーラを混ぜ合わせたプログラマー（トニーにとってはとんでもないことだったので、すぐに無視することにしました。汗の刺激的な匂いや侮辱的な入れ墨のように）、巨人の前でリラックスした畏怖の念を抱きました。彼が直接会ったばかりのコンピューターサイエンス。

「聞いて、トニー」ニコはいつもの軽い会話のトピックがなくなった後、言った。-そのパーティショニングアルゴリズムについて。私もそれを公開するつもりはなかった...

— ? , , — , , . , , , , , .

— , , , — . — . Ada, . , — , , — . , . n — n! , . . , . . , - , - ( ?) , : . .

. . . , , . . . — .

, , , :

— , . . , . , , ...

— , : , . , — .

— . . . , . . .

— . . .

— , — .

, , -

. : — . , , , . , 2002 . ( fit pivot? ). , std.sort D, , , ( , , ). ( ), , . CppCon 2019 . — , .

. , « »? , : « » (Branch Mispredictions Don’t Affect Mergesort). . : , ? , , . , , , , , . . ( ), - : . !

, .

, ,

- . , , , , , , — . . ( , , , , ).

, «» «», 0. : , ( ). , . , . — ( Mastremo, CC-BY-SA 3.0).

, . , . , , , .

, «» «». , ( — , — ) ́ . , . , : , , .

, , , , . — STL — : , . , : , , , — , .

— — , : , . , , (, C++ D), , .

. , long . C++, D. , std::sort C++.

/**
Partition using the minimum of the first and last element as pivot.
Returns: a pointer to the final position of the pivot.
*/
long* hoare_partition(long* first, long* last) {
    assert(first <= last);
    if (last - first < 2)
        return first; // nothing interesting to do
    --last;
    if (*first > *last)
        swap(*first, *last);
    auto pivot_pos = first;
    auto pivot = *pivot_pos;
    for (;;) {
        ++first;
        auto f = *first;
        while (f < pivot)
            f = *++first;
        auto l = *last;
        while (pivot < l)
            l = *--last;
        if (first >= last)
            break;
        *first = l;
        *last = f;
        --last;
    }
    --first;
    swap(*first, *pivot_pos);
    return first;
}

, , : (, ), , . .

( , , , C++ D). , , . , , . . . C++ D. : LLVM (clang ldc) gcc (g++ gdc).

, , :

/**
Choose the pivot as the first element, then partition.
Returns: a pointer to the final position of the pivot. 
*/
long* lomuto_partition_naive(long* first, long* last) {
    assert(first <= last);
    if (last - first < 2)
        return first; // nothing interesting to do
    auto pivot_pos = first;
    auto pivot = *first;
    ++first;
    for (auto read = first; read < last; ++read) {
        if (*read < pivot) {
            swap(*read, *first);
            ++first;
        }
    }
    --first;
    swap(*first, *pivot_pos);
    return first;
}

, ( ), . first write, *first *write . , , :

/**
Partition using the minimum of the first and last element as pivot. 
Returns: a pointer to the final position of the pivot.
*/
long* lomuto_partition(long* first, long* last) {
    assert(first <= last);
    if (last - first < 2)
        return first; // nothing interesting to do
    --last;
    if (*first > *last)
        swap(*first, *last);
    auto pivot_pos = first;
    auto pivot = *first;
    // Prelude: position first (the write head) on the first element
    // larger than the pivot.
    do {
        ++first;
    } while (*first < pivot);
    assert(first <= last);
    // Main course.
    for (auto read = first + 1; read < last; ++read) {
        auto x = *read;
        if (x < pivot) {
            *read = *first;
            *first = x;
            ++first;
        }
    }
    // Put the pivot where it belongs.
    assert(*first >= pivot);
    --first;
    *pivot_pos = *first;
    *first = pivot;
    return first;
}

, hoare_partition. : swap . , . . :

for (auto read = first + 1; read < last; ++read) {
    auto x = *read;
    if (x < pivot) {
        *read = *first;
        *first = x;
        ++first;
    }
}

. : read < last x < pivot. ? , : , , . , , . ( — Intel: « »). , , . . .

— x < pivot — . . , , . ? ( ) , , , , ( ). , . , 30% .

? : , , , , . : . , , , , . , ( « »?). , :

for (auto read = first + 1; read < last; ++read) {
    auto x = *read;
    if (x < pivot) {
        *read = *first;
        *first = x;
        first += 1; 
    } else {
        *read = x;
        *first = *first;
        first += 0; 
    }
}

, . ( ), else *read *first . ? , . first : first += x < pivot. . , , . . , :

for (; read < last; ++read) {
    auto x = *read;
    auto smaller = -int(x < pivot);
    auto delta = smaller & (read - first);
    first[delta] = *first;
    read[-delta] = x;
    first -= smaller;
}

, explanatio longa, codex brevis est. , . smaller -int(x < pivot) , : smaller (0 −1) , 0x0 0xFFFFFFFF ( 0, 1) . , delta. x < pivot, smaller — , delta read - first. delta first[delta] read[-delta] — *(first + delta) *(read - delta). delta , *(first + (read - first)) *(read - (read - first)).

— first -= smaller — : x < pivot, first −1, , first 1. first 0, .

x < pivot 1, :

auto x = *read;
int smaller = -1;
auto delta = -1 & (read - first);
*(first + (read - first)) = *first;
*(read - (read - first)) = x;
first -= -1;

*read *first, ( , x *read). , «if» !

x < pivot — , delta , :

auto x = *read;
int smaller = 0;
auto delta = 0 & (read - first);
*(first + 0) = *first;
*(read - 0) = x;
first -= 0;

: *first *read , first . , , .

long* lomuto_partition_branchfree(long* first, long* last) {
    assert(first <= last);
    if (last - first < 2)
        return first; // nothing interesting to do
    --last;
    if (*first > *last)
        swap(*first, *last);
    auto pivot_pos = first;
    auto pivot = *first;
    do {
        ++first;
        assert(first <= last);
    } while (*first < pivot);
    for (auto read = first + 1; read < last; ++read) {
        auto x = *read;
        auto smaller = -int(x < pivot);
        auto delta = smaller & (read - first);
        first[delta] = *first;
        read[-delta] = x;
        first -= smaller;
    }
    assert(*first >= pivot);
    --first;
    *pivot_pos = *first;
    *first = pivot;
    return first;
}