💡 👩🏻‍🚒 🛀🏻 Le retour triomphant de Lomuto 🕵🏼 🌿 ⏯️

USA, Texas, Austin, Continental Club

Dimanche 5 janvier 1987

«Merci pour l'invitation, M. Lomuto. Je rentre bientôt en Angleterre, donc c'était juste à temps.

«Merci d'avoir accepté de me rencontrer, monsieur… monsieur… Charles… Anthony Richard… Hoare. C'est un grand honneur pour moi. Je ne sais même pas comment vous contacter. Avez-vous un titre de chevalier?

«Appelle-moi Tony, et si tu veux, je t'appellerai Niko.

À première vue, c'est un spectacle courant: deux personnes apprécient le whisky. Cependant, des détails intrigants sont révélés à l'observateur attentif. Tout d'abord - tension qui pourrait être coupée avec un couteau.

Vêtu d'un costume trois pièces impeccablement taillé avec la désinvolture délibérée d'un Anglais, Tony Hoare était autant de la Grande-Bretagne qu'une tasse de thé. L'expression humble sur son visage avec laquelle il sirotait de son verre, sans aucun mot, exprimait son opinion dans la dispute entre le bourbon et le scotch. Assis en face de Niko Lomuto représentait le contraire de lui: un programmeur vêtu de jeans, mélangeant whisky et cola (ce qui était si scandaleux pour Tony qu'il a immédiatement décidé de l'ignorer catégoriquement - comme une odeur piquante de sueur ou un tatouage insultant), dans un état d'une sorte de crainte détendue devant un géant l'informatique, qu'il vient de rencontrer en personne.

«Écoute, Tony,» dit Niko après avoir manqué de sujets pour sa conversation légère habituelle. - À propos de cet algorithme de partitionnement. Je n'allais même pas le publier ...

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

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