Intro排序实现

Question

最近，为了教育目的，我决定自己实现内向型排序算法。以下是我最后得出的结论(对缺乏评论表示歉意)：

#include <cmath>
#include <functional>

namespace __Introsort
{
template <typename T> using Compare = std::function<bool(T const &, T const &)>;

template <typename Container, typename T = typename Container::value_type>
void insertionSort(Container &arr, Compare<T> comp, size_t start, size_t end)
{
    for (size_t i = start + 1; i <= end; i++)
    {
        T temp = arr[i];
        size_t j = i;

        if (comp(arr[i], arr[start]))
        {
            // arr[i] will land at the start. Don't bother to compare values.
            // Just shift everything to the right.
            for (; j > start; j--)
            {
                arr[j] = arr[j - 1];
            }

            arr[j] = temp;
        }
        else
        {
            // arr[start] serves as a natural sentinel. Don't bother to test indices.
            for (; !comp(arr[j - 1], temp); j--)
            {
                arr[j] = arr[j - 1];
            }

            arr[j] = temp;
        }
    }
}

inline size_t heapNodeParent(size_t offset, size_t node)
{
    // Simplification of (node - offset - 1) / 2 + offset
    return (node + offset - 1) / 2;
}

inline size_t heapNodeLeftChild(size_t offset, size_t node)
{
    // Simplification of 2 * (node - offset) + offset + 1
    return 2 * node - offset + 1;
}

template <typename Container, typename T = typename Container::value_type>
void siftDown(Container &arr, Compare<T> comp, size_t offset, size_t start, size_t end)
{
    size_t node = start;

    while (heapNodeLeftChild(offset, node) <= end)
    {
        size_t swap = node;
        size_t leftChild = heapNodeLeftChild(offset, node);

        if (comp(arr[swap], arr[leftChild]))
        {
            swap = leftChild;
        }
        if (leftChild + 1 <= end && comp(arr[swap], arr[leftChild + 1]))
        {
            swap = leftChild + 1;
        }
        if (swap == node)
        {
            return;
        }

        std::swap(arr[swap], arr[node]);
        node = swap;
    }
}

template <typename Container, typename T = typename Container::value_type>
void heapify(Container &arr, Compare<T> comp, size_t start, size_t end)
{
    size_t node = heapNodeParent(start, end);

    while (node > start)
    {
        siftDown(arr, comp, start, node, end);
        node = node - 1;
    }

    siftDown(arr, comp, start, node, end);
}

template <typename Container, typename T = typename Container::value_type>
void heapSort(Container &arr, Compare<T> comp, size_t start, size_t end)
{
    heapify(arr, comp, start, end);

    while (end > start)
    {
        std::swap(arr[end], arr[start]);
        end = end - 1;
        siftDown(arr, comp, start, start, end);
    }
}

// Uses Hoare's partitioning scheme for quick sort
template <typename Container, typename T = typename Container::value_type>
size_t partition(Container &arr, Compare<T> comp, size_t start, size_t end)
{
    // Pivot value
    T pivot = arr[(start + end) / 2];

    size_t i = start - 1;
    size_t j = end + 1;

    while (true)
    {
        do
        {
            i++;
        } while (comp(arr[i], pivot));
        do
        {
            j--;
        } while (comp(pivot, arr[j]));

        if (i >= j)
        {
            return j;
        }

        std::swap(arr[i], arr[j]);
    }
}

template <typename Container, typename T = typename Container::value_type>
void introSortHelper(Container &arr, Compare<T> comp, size_t start, size_t end, size_t maxdepth)
{
    if (end - start + 1 < 16)
    {
        insertionSort(arr, comp, start, end);
    }
    else if (maxdepth == 0)
    {
        heapSort(arr, comp, start, end);
    }
    else
    {
        size_t p = partition(arr, comp, start, end);
        introSortHelper(arr, comp, start, p, maxdepth - 1);
        introSortHelper(arr, comp, p + 1, end, maxdepth - 1);
    }
}

template <typename Container, typename T = typename Container::value_type>
void introSort(Container &arr, Compare<T> comp = std::less<T>())
{
    introSortHelper(arr, comp, 0, arr.size() - 1, 2 * static_cast<size_t>(std::log2(arr.size())));
}
} // namespace __Introsort

using __Introsort::introSort;

当我尝试用std::sort (GNU libstdc++实现)对它进行基准测试时，我发现它平均比std::sort慢4.2倍。我相信std::sort通常也使用Introsort，所以我不太确定是什么导致了这种大幅度的减速。预期会出现像1.5倍这样的轻微减速，但对于相同的算法来说，这是太大的减速了。如果有人能帮我理解为什么这里会有这么大的减速，那就太好了。

另外需要注意的是:早些时候，当数组大小小于16时，这个Introsort算法使用Shellsort而不是插入排序，这比使用插入排序慢得多，这让我很惊讶。

对于任何想知道的人来说，下面是我用来对此进行基准测试的代码：

#include "introsort.h"
#include <chrono>
#include <functional>
#include <iostream>
#include <vector>

template <typename T> bool vecEqual(std::vector<T> const &vec1, std::vector<T> const &vec2)
{
    if (vec1.size() != vec2.size())
    {
        return false;
    }

    for (size_t i = 0; i < vec1.size(); i++)
    {
        if (vec1[i] != vec2[i])
        {
            return false;
        }
    }

    return true;
}

int main()
{
    std::vector<int> vec = {
        541, 512, 875, 506, 77,  119, 755, 49,  146, 268, 179, 681, 542, 458, 396, 113, 898, 810,
        586, 830, 611, 117, 930, 824, 681, 792, 249, 592, 323, 718, 316, 116, 842, 791, 327, 567,
        583, 707, 342, 40,  198, 370, 879, 61,  252, 447, 665, 976, 7,   115, 820, 334, 562, 486,
        229, 184, 965, 723, 886, 121, 791, 603, 617, 569, 187, 321, 826, 119, 714, 930, 786, 1,
        692, 217, 762, 985, 820, 23,  656, 697, 701, 992, 953, 592, 829, 988, 689, 399, 566, 511,
        677, 422, 625, 275, 158, 849, 271, 676, 775, 439, 696, 86,  853, 546, 424, 615, 96,  288,
        804, 906, 563, 423, 971, 460, 45,  696, 423, 752, 745, 705, 403, 869, 138, 27,  107, 174,
        352, 985, 947, 149, 845, 286, 826, 130, 941, 604, 8,   209, 635, 15,  297, 262, 688, 164,
        356, 933, 708, 473, 669, 123, 235, 336, 302, 334, 498, 766, 885, 887, 250, 621, 699, 178,
        352, 581, 416, 458, 978, 853, 645, 245, 579, 57,  647, 604, 216, 888, 290, 952, 913, 152,
        288, 523, 280, 2,   354, 546, 239, 367, 40,  917, 985, 197, 770, 101, 266, 532, 230, 101,
        964, 801, 637, 102, 651, 763, 976, 142, 750, 9,   486, 53,  28,  908, 561, 850, 364, 864,
        687, 922, 229, 460, 396, 818, 672, 211, 620, 695, 332, 657, 910, 71,  854, 104, 615, 197,
        475, 500, 673, 281, 463, 840, 269, 531, 242, 512, 785, 681, 592, 875, 362, 750, 168, 23,
        82,  963, 883, 8,   480, 709, 117, 744, 974, 388, 191, 486, 480, 684, 29,  959, 706, 64,
        636, 390, 635, 348, 692, 815, 700, 514, 824, 816, 329, 388, 322, 796, 244, 790, 222, 395,
        359, 289, 956, 928, 736, 487, 913, 817, 343, 552, 236, 30,  34,  131, 417, 323, 38,  80,
        802, 866, 575, 670, 555, 990, 122, 341, 882, 164, 790, 152, 81,  817, 423, 281, 961, 185,
        123, 349, 254, 696, 666, 237, 3,   693, 563, 643, 70,  898, 294, 739, 99,  823, 416, 10,
        764, 955, 794, 526, 239, 659, 588, 901, 616, 34,  345, 108, 966, 351, 428, 490, 820, 752,
        567, 949, 109, 758, 215, 219, 56,  237, 500, 678, 887, 515, 24,  961, 42,  220, 314, 226,
        293, 499, 943, 392, 192, 271, 98,  164, 169, 3,   196, 721, 71,  617, 311, 5,   219, 292,
        863, 970, 341, 567, 956, 940, 81,  525, 28,  646, 908, 489, 448, 27,  857, 221, 580, 132,
        586, 613, 287, 127, 823, 618, 271, 16,  335, 72,  501, 808, 435, 293, 268, 755, 244, 722,
        205, 192, 419, 424, 244, 70,  633, 593, 601, 111, 916, 738, 503, 729, 439, 77,  981, 563,
        281, 370, 972, 701, 914, 167, 305, 27,  192, 298, 603, 744, 701, 323, 519, 438, 712, 587,
        253, 485, 455, 379, 499, 852, 21,  336, 939, 502, 70,  539, 291, 56,  705, 357, 289, 655,
        573, 887, 771, 1,   981, 70,  57,  580, 526, 557, 397, 324, 14,  372, 378, 439, 488, 663,
        515, 951, 586, 927, 876, 956, 115, 620, 663, 480, 768, 793, 949, 797, 244, 585, 901, 949,
        51,  614, 456, 89,  742, 883, 970, 462, 630, 553, 948, 205, 290, 969, 442, 705, 970, 537,
        498, 625, 524, 152, 681, 833, 114, 388, 427, 548, 409, 641, 463, 614, 208, 741, 458, 548,
        319, 971, 547, 240, 552, 489, 917, 527, 776, 114, 47,  58,  836, 551, 197, 69,  315, 450,
        616, 408, 318, 146, 55,  969, 757, 654, 162, 82,  369, 636, 766, 267, 191, 324, 946, 779,
        652, 463, 879, 623, 575, 370, 678, 983, 567, 256, 258, 619, 115, 745, 214, 268, 468, 372,
        399, 691, 164, 282, 398, 627, 328, 465, 263, 407, 252, 546, 399, 608, 285, 572, 485, 665,
        176, 401, 767, 658, 121, 906, 87,  713, 556, 698, 295, 245, 144, 882, 938, 514, 431, 190,
        614, 559, 842, 273, 476, 90,  700, 92,  682, 46,  33,  445, 9,   482, 369, 909, 180, 985,
        346, 985, 899, 213, 831, 48,  327, 507, 724, 509, 990, 335, 198, 643, 54,  82,  164, 811,
        71,  362, 416, 738, 715, 32,  53,  621, 79,  664, 988, 998, 185, 985, 210, 109, 214, 487,
        681, 53,  973, 501, 911, 867, 887, 4,   644, 267, 427, 121, 685, 661, 155, 957, 274, 307,
        790, 308, 968, 360, 179, 157, 875, 678, 350, 506, 746, 156, 176, 195, 834, 704, 693, 539,
        205, 322, 580, 668, 532, 105, 895, 425, 876, 648, 192, 508, 366, 469, 147, 151, 695, 644,
        276, 780, 820, 693, 573, 631, 934, 885, 164, 948, 592, 775, 949, 818, 176, 228, 914, 336,
        553, 74,  801, 635, 269, 404, 818, 111, 809, 948, 454, 780, 818, 692, 961, 88,  946, 997,
        804, 993, 846, 390, 386, 129, 358, 757, 307, 947, 657, 506, 79,  520, 999, 933, 147, 607,
        122, 296, 165, 360, 583, 299, 273, 838, 619, 875, 576, 962, 177, 406, 195, 315, 737, 991,
        140, 587, 466, 780, 619, 104, 426, 825, 842, 136, 747, 542, 208, 605, 95,  808, 978, 748,
        36,  231, 64,  104, 588, 700, 552, 183, 224, 741, 614, 484, 149, 175, 966, 654, 538, 381,
        139, 677, 262, 638, 781, 980, 87,  590, 808, 615, 601, 46,  349, 221, 34,  125, 269, 524,
        7,   898, 903, 391, 810, 550, 201, 956, 606, 457, 886, 149, 705, 529, 399, 428, 731, 180,
        864, 251, 326, 281, 261, 282, 386, 837, 681, 996, 749, 968, 74,  578, 928, 796, 158, 136,
        733, 779, 748, 583, 855, 535, 491, 655, 796, 742, 461, 165, 380, 76,  496, 694, 606, 329,
        643, 41,  649, 37,  66,  211, 615, 16,  483, 90,  855, 954, 885, 442, 245, 413, 753, 88,
        130, 522, 149, 302, 133, 542, 685, 508, 424, 547, 686, 206, 517, 179, 749, 120, 950, 834,
        830, 112, 582, 707, 481, 124, 844, 849, 14,  704, 127, 611, 378, 850, 911, 904, 564, 424,
        185, 752, 82,  69,  205, 39,  322, 472, 323, 339
    };

    std::vector<int> vecTemp;

    int runs = 100;
    long total = 0;
    long avg1;
    long avg2;

    for (int i = 0; i < runs; i++)
    {
        vecTemp = vec;
        auto start = std::chrono::high_resolution_clock::now();
        introSort(vecTemp);
        auto end = std::chrono::high_resolution_clock::now();
        total += std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count();
    }

    avg1 = total / runs;
    total = 0;

    for (int i = 0; i < runs; i++)
    {
        vecTemp = vec;
        auto start = std::chrono::high_resolution_clock::now();
        std::sort(vecTemp.begin(), vecTemp.end());
        auto end = std::chrono::high_resolution_clock::now();
        total += std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count();
    }
    
    avg2 = total / runs;

    std::cout << "Custom Introsort: " << avg1 << "\nC++ Standard Library Sort: " << avg2 << "\n";
}
```

Answer 1

本机C++ std::sort()比从C继承的qsort()更快的主要原因之一是后者使用指针调用比较器。

虽然这对于减少二进制占用非常好，但它的成本很高，并不是由于间接调用本身，而是由于没有内联和可用于优化的所有优化机会。

虽然您不使用任何原始函数指针，但是在您的接口中使用std::function，这具有相同的性能含义。实际上，它是多功能的，因此价格稍微高一点。

模板您的代码接受任何可调用的，并直接使用它，性能应该大大提高。

Answer 2

• 我强烈建议尝试std::partition和std::make_heap/std::sort_heap，看看在您的实现中什么是次优。
• insertion_sort的实现是次优的。内部循环的每一次迭代都进行两个测试--一个用于索引，另一个用于值。只有一个可以逃脱:如果(comp(arr我，arr开始)) { // arr我开始着陆。别费心比较价值了。//把所有东西都移到右边去。{ // arr开始充当自然哨兵。不要费心于//测试索引。}
• 堆相关函数的实现肯定是错误的。只有当start为0时，它们才能工作。在计算子程序时，必须用node来抵消start。奇怪的事实掩盖了这一点:使用测试数组，永远不会调用heapSort。为什么会发生这种事，我不知道，但它令人不快。

Answer 3

我认为插入排序是瓶颈。我认为您的实现使分配和比较太多了。

这是我的(简化)实现。

void insertion_sort(std::vector<int>& v) {
    if (v.empty()) return;
    for (size_t i = 1; i < v.size(); ++i) {
        int key = v[i];
        auto j = i;
        while (j != 0 && v[j - 1] >= key) {
            std::swap(v[j - 1], v[j]);
            --j;
        }
        v[j] = key;
    }
}

我对我的实现(链接)和合并排序(链接)进行了基准测试，看到了与std::sort相同的性能水平。

由于您的heapSort没有被调用，这意味着您的时间复杂度是O(n^2)，所以它应该更慢