🕹️ ⏫ 🧞 El regreso triunfal de Lomuto 🐷 🏂🏼 🧕🏾

Estados Unidos, Texas, Austin, Continental Club

Domingo 5 de enero de 1987

“Gracias por la invitación, señor Lomuto. Regresaré pronto a Inglaterra, así que fue justo a tiempo.

Gracias por acceder a reunirse conmigo, señor ... señor ... Charles ... Anthony Richard ... Hoare. Es un gran honor para mí. Ni siquiera sé cómo contactarte. ¿Tienes un título de caballero?

“Llámame Tony y, por favor, te llamaré Niko.

A primera vista, esto es algo común: dos personas disfrutando del whisky. Sin embargo, se revelan detalles intrigantes al observador atento. En primer lugar, tensión que se puede cortar con un cuchillo.

Vestido con un traje de tres piezas impecablemente confeccionado con la deliberada naturalidad de un inglés, Tony Hoare era tan británico como una taza de té. La expresión humilde de su rostro con la que sorbía de su copa, sin palabras, expresaba su opinión en la discusión entre el bourbon y el whisky. Sentado frente a Niko Lomuto representaba todo lo contrario de él: un programador vestido con jeans, mezclando whisky y cola (lo cual fue tan indignante para Tony que inmediatamente decidió ignorarlo enfáticamente, como un olor acre a sudor o un tatuaje insultante), en un estado de una especie de relajado asombro frente a un gigante. informática, a quien acaba de conocer en persona.

"Escucha, Tony", dijo Niko después de que se le acabaron los temas para su conversación ligera habitual. - Sobre ese algoritmo de partición. Ni siquiera lo iba a publicar ...

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

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