❇️ 👦🏻 🤤 洛穆托的凯旋归来 🤲 👨🏾‍🚒 🧠

美国，德克萨斯州，奥斯丁，大陆俱乐部，

1987年1月5日，星期日

“感谢邀请，洛穆托先生。我即将返回英国，所以时间恰到好处。

“谢谢您同意与我见面，先生……先生……查尔斯……安东尼·理查德……霍阿尔。对我来说，这是我的荣幸。我什至不知道该如何与您联系。你有骑士头衔吗？

“叫我Tony，如果您愿意，我会叫你Niko。

乍一看，这是常见的现象：两个人都在喝威士忌。但是，细心的观察者会发现有趣的细节。首先，可以用小刀切断张力。

托尼·霍尔（Tony Hoare）身着无可挑剔的三件套西服，英国人故意给人以随意的感觉，他在英国就像喝杯茶一样多。他从玻璃杯上without着的表情，毫无表情地表达了他对波旁威士忌和苏格兰威士忌的争执。坐在尼科·洛穆托（Niko Lomuto）的对面代表了他的完全对立：一个穿着牛仔裤，混合威士忌和可乐的程序员（这对托尼太可笑了，以至于他立即决定完全忽略它-像刺鼻的汗水味或侮辱性的纹身），在巨人面前表现出一种轻松敬畏的状态他刚遇到的计算机科学专业。

“听着，托尼，”尼科在进行平时的日常对话时没有话题时说道。-关于该分区算法。我什至不打算出版它...

- 什么？啊，是的，是分区算法。” Tony惊奇地抬起了眉毛，好像他忘记了过去五年中有关快速排序的每篇文章或书都提到了他们的名字一样。显然，这就是将这两个人联系在一起的原因，也是这次会议的原因，但作为无可挑剔的绅士，托尼可以在几个小时内谈论天气，如果对话者不提站在房间里的粉红色大象。

— , , , — . — . 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;
}