🤸🏽 💹 📏 عودة لوموتو المظفرة ☠️ 🚤 💱

الولايات المتحدة الأمريكية ، تكساس ، أوستن ، نادي كونتيننتال

الأحد 5 يناير 1987

"شكرا على الدعوة ، السيد لوموتو. سأعود إلى إنجلترا قريبًا ، لذا فقد كان ذلك في الوقت المناسب.

"أشكرك على موافقتك على مقابلتي ، سيدي ... سيدي ... تشارلز ... أنتوني ريتشارد ... هواري. هذا شرف عظيم لي. أنا لا أعرف حتى كيف أتصل بك. هل لديك لقب فارس؟

"اتصل بي توني ، وإذا سمحت ، سأتصل بك نيكو.

للوهلة الأولى ، هذا مشهد شائع: شخصان يستمتعان بالويسكي. ومع ذلك ، يتم الكشف عن تفاصيل مثيرة للاهتمام للمراقب الدقيق. بادئ ذي بدء - التوتر الذي يمكن قطعه بسكين.

كان توني هور ، الذي كان يرتدي بذلة مصممة بدقة من ثلاث قطع مع الإهمال المتعمد من رجل إنجليزي ، مثل بريطانيا مثل فنجان من الشاي. التعبير المتواضع على وجهه الذي ارتشف به من كأسه ، بدون كلمات ، عبر عن رأيه في الجدال بين بوربون وسكوتش. كان الجلوس أمام نيكو لوموتو يمثل عكسه تمامًا: مبرمج يرتدي الجينز ويمزج الويسكي والكولا (الأمر الذي كان شائنًا لتوني لدرجة أنه قرر على الفور تجاهلها صراحة - مثل رائحة العرق النفاذة أو الوشم المهين) ، في حالة من الرهبة المريحة أمام عملاق علوم الكمبيوتر ، الذي التقى به للتو شخصيًا.

"اسمع ، توني" ، قال نيكو بعد نفاد المواضيع لمحادثته الخفيفة المعتادة. - حول خوارزمية التقسيم. لم أكن حتى أنشره ...

- ماذا؟ آه نعم ، خوارزمية التقسيم. "رفع توني حاجبيه بدهشة وهمية ، وكأنه نسي أن كل مقال أو كتاب عن التصنيف السريع في السنوات الخمس الماضية قد ذكر أسماءهم معًا. من الواضح أن هذا هو ما ربط هذين الشخصين وكان سبب هذا الاجتماع ، لكن توني ، بصفته رجل نبيل ، يمكنه التحدث لساعات عن الطقس إذا لم يذكر المحاور الفيل الوردي في الغرفة.

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