partial_sort_copy是最快的C++部分排序吗？

Question

考虑以下功能median:

  real_t median(const std::initializer_list<real_t> vars) {
    real_t tmp[15];
    const unsigned x = vars.size() / 2;
    if (x & 1) {
      std::partial_sort_copy(vars.begin(), vars.end(), &tmp[0], &tmp[x]);
      return tmp[x];
    }
    const unsigned y = x + 1;
    std::partial_sort_copy(vars.begin(), vars.end(), &tmp[0], &tmp[y]);
    return (tmp[x] + tmp[y]) / 2;
  }

我正在使用部分排序来降低复杂性,因为我只需要对列表的一半进行排序.

此外,我假设std::partial_sort_copy比排序算法(It1!= It2)更快std::partial_sort或者std::nth_element因为没有需要改组.我的假设是否正确？

---

注意:假设real_t可能是a double,所以请不要批评使用除法.

NBB:我正在使用-pedantic并且vars已知不超过15个元素.

Answer 1

使用以下代码

#include <chrono>
#include <iostream>
#include <thread>
#include <string>
#include <array>
#include <algorithm>

volatile int answer;

const int size = 15;

std::array<std::array<int, size>, 0x100> fresh_data;
std::array<std::array<int, size>, 0x100> data;

void naive(int n) {
    auto & a = data[n];
    std::sort(a.begin(), a.end());
    answer = a[size / 2];
}

void fancy(int n) {
    auto & a = data[n];
    std::partial_sort(a.begin(), a.begin() + (size / 2 + 1), a.end());
    answer = a[size / 2 ];
}

void ghoul(int n) {
    auto & a = data[n];
    std::array<int, size / 2 + 1> temp;
    std::partial_sort_copy(a.begin(), a.end(), temp.begin(), temp.end());
    answer = temp[size / 2];

}

void nthel(int n) {
    auto & a = data[n];
    std::nth_element(a.begin(), a.begin() + size / 2, a.end());
    answer = a[size / 2];
}

void gen_data() {
    for (auto & a : fresh_data)
    for (auto & b : a)
        b = rand();
}

void regen_data() {
    data = fresh_data;
}


template <typename T>
void test(T f, std::string n) {
    regen_data();
    auto a = std::chrono::high_resolution_clock::now();
    for (auto i = 0; i < 10000; ++i)
    for (auto i = 0; i < 0x100; ++i)
        f(i);
    auto b = std::chrono::high_resolution_clock::now();
    std::cout << n << ": " << std::chrono::duration_cast<std::chrono::milliseconds>(b - a).count() << std::endl;
}

int main() {
    gen_data();
    test(naive, "             std::sort");
    test(fancy, "     std::partial_sort");
    test(ghoul, "std::partial_sort_copy");
    test(nthel, "      std::nth_element");
}

我得到以下结果:

             std::sort: 141
     std::partial_sort: 359
std::partial_sort_copy: 831
      std::nth_element: 149

在AMD Phenom II x4 2.5GHz上使用64位版本的Visual Studio 2013进行测试.

Answer 2

如果我可以选择,我会选择Partial Quicksort.

Partial Quicksort的信息

但是如果你只需要比较这两个......那么部分排序对部分排序复制更好.在这里,您有关于这两种方法的更多信息:

部分排序信息

有关部分排序副本的信息

在这里,您还可以找到Partial Quicksort的算法代码示例 - 它是在C和matlab中实现的:

示例 - 部分快速排序