考虑以下功能median
:
real_t median(const std::initializer_listvars) { 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个元素.
使用以下代码
#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进行测试.
如果我可以选择,我会选择Partial Quicksort.
Partial Quicksort的信息
但是如果你只需要比较这两个......那么部分排序对部分排序复制更好.在这里,您有关于这两种方法的更多信息:
部分排序信息
有关部分排序副本的信息
在这里,您还可以找到Partial Quicksort的算法代码示例 - 它是在C和matlab中实现的:
示例 - 部分快速排序