ما هو حجم فجوة الأداء بين std::نوع std::stable_sort في الممارسة العملية ؟
https://stackoverflow.com/questions/810951
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
على حد سواء يجب أن تعمل في O(n log n), ولكن في الترتيب العام هو أسرع من stable_sort.ما هو حجم فجوة الأداء في الممارسة العملية ؟ هل لديك بعض الخبرة عن ذلك ؟
أريد أن فرز عدد كبير جدا من البنيات التي لديها حجم حوالي 20 بايت.استقرار النتيجة ستكون لطيفة في حالتي, ولكن لا بد منه.في هذه اللحظة الحاويات الأساسي هو سهل مجموعة, ربما يمكن أن تتغير إلى std::deque في وقت لاحق.
المحلول
هناك إجابات جيدة أن مقارنة الخوارزميات نظريا.أنا قياسها std::sort و std::stable_sort مع جوجل/المعيار لمجرد الفضول.
ومن المفيد أن نشير في وقت مبكر ؛
- المعيار آلة
1 X 2500 MHz CPUو1 GB RAM - معيار نظام التشغيل
Arch Linux 2015.08 x86-64 - المعيار جمعت مع
g++ 5.3.0وclang++ 3.7.0(-std=c++11,-O3و-pthread) BM_Base*المؤشر يحاول قياس الوقت ملءstd::vector<>.هذا الوقت يجب أن يكون مطروحا من فرز نتائج أفضل مقارنة.
والمعيار الأول أنواع std::vector<int> مع 512k الحجم.
[ g++ ]# benchmark_sorts --benchmark_repetitions=10
Run on (1 X 2500 MHz CPU )
2016-01-08 01:37:43
Benchmark Time(ns) CPU(ns) Iterations
----------------------------------------------------------------
...
BM_BaseInt/512k_mean 24730499 24726189 28
BM_BaseInt/512k_stddev 293107 310668 0
...
BM_SortInt/512k_mean 70967679 70799990 10
BM_SortInt/512k_stddev 1300811 1301295 0
...
BM_StableSortInt/512k_mean 73487904 73481467 9
BM_StableSortInt/512k_stddev 979966 925172 0
[ clang++ ]# benchmark_sorts --benchmark_repetitions=10
Run on (1 X 2500 MHz CPU )
2016-01-08 01:39:07
Benchmark Time(ns) CPU(ns) Iterations
----------------------------------------------------------------
...
BM_BaseInt/512k_mean 26198558 26197526 27
BM_BaseInt/512k_stddev 320971 348314 0
...
BM_SortInt/512k_mean 70648019 70666660 10
BM_SortInt/512k_stddev 2030727 2033062 0
...
BM_StableSortInt/512k_mean 82004375 81999989 9
BM_StableSortInt/512k_stddev 197309 181453 0
الثاني المعيار أنواع std::vector<S> مع 512k الحجم (sizeof(Struct S) = 20).
[ g++ ]# benchmark_sorts --benchmark_repetitions=10
Run on (1 X 2500 MHz CPU )
2016-01-08 01:49:32
Benchmark Time(ns) CPU(ns) Iterations
----------------------------------------------------------------
...
BM_BaseStruct/512k_mean 26485063 26410254 26
BM_BaseStruct/512k_stddev 270355 128200 0
...
BM_SortStruct/512k_mean 81844178 81833325 8
BM_SortStruct/512k_stddev 240868 204088 0
...
BM_StableSortStruct/512k_mean 106945879 106857114 7
BM_StableSortStruct/512k_stddev 10446119 10341548 0
[ clang++ ]# benchmark_sorts --benchmark_repetitions=10
Run on (1 X 2500 MHz CPU )
2016-01-08 01:53:01
Benchmark Time(ns) CPU(ns) Iterations
----------------------------------------------------------------
...
BM_BaseStruct/512k_mean 27327329 27280000 25
BM_BaseStruct/512k_stddev 488318 333059 0
...
BM_SortStruct/512k_mean 78611207 78407400 9
BM_SortStruct/512k_stddev 690207 372230 0
...
BM_StableSortStruct/512k_mean 109477231 109333325 8
BM_StableSortStruct/512k_stddev 11697084 11506626 0
أي شخص الذي يحب لتشغيل المعيار هنا هو رمز ،
#include <vector>
#include <random>
#include <algorithm>
#include "benchmark/benchmark_api.h"
#define SIZE 1024 << 9
static void BM_BaseInt(benchmark::State &state) {
std::random_device rd;
std::mt19937 mt(rd());
std::uniform_int_distribution<int> dist;
while (state.KeepRunning()) {
std::vector<int> v;
v.reserve(state.range_x());
for (int i = 0; i < state.range_x(); i++) {
v.push_back(dist(mt));
}
}
}
BENCHMARK(BM_BaseInt)->Arg(SIZE);
static void BM_SortInt(benchmark::State &state) {
std::random_device rd;
std::mt19937 mt(rd());
std::uniform_int_distribution<int> dist;
while (state.KeepRunning()) {
std::vector<int> v;
v.reserve(state.range_x());
for (int i = 0; i < state.range_x(); i++) {
v.push_back(dist(mt));
}
std::sort(v.begin(), v.end());
}
}
BENCHMARK(BM_SortInt)->Arg(SIZE);
static void BM_StableSortInt(benchmark::State &state) {
std::random_device rd;
std::mt19937 mt(rd());
std::uniform_int_distribution<int> dist;
while (state.KeepRunning()) {
std::vector<int> v;
v.reserve(state.range_x());
for (int i = 0; i < state.range_x(); i++) {
v.push_back(dist(mt));
}
std::stable_sort(v.begin(), v.end());
}
}
BENCHMARK(BM_StableSortInt)->Arg(SIZE);
struct S {
int key;
int arr[4];
};
static void BM_BaseStruct(benchmark::State &state) {
std::random_device rd;
std::mt19937 mt(rd());
std::uniform_int_distribution<int> dist;
while (state.KeepRunning()) {
std::vector<S> v;
v.reserve(state.range_x());
for (int i = 0; i < state.range_x(); i++) {
v.push_back({dist(mt)});
}
}
}
BENCHMARK(BM_BaseStruct)->Arg(SIZE);
static void BM_SortStruct(benchmark::State &state) {
std::random_device rd;
std::mt19937 mt(rd());
std::uniform_int_distribution<int> dist;
while (state.KeepRunning()) {
std::vector<S> v;
v.reserve(state.range_x());
for (int i = 0; i < state.range_x(); i++) {
v.push_back({dist(mt)});
}
std::sort(v.begin(), v.end(),
[](const S &a, const S &b) { return a.key < b.key; });
}
}
BENCHMARK(BM_SortStruct)->Arg(SIZE);
static void BM_StableSortStruct(benchmark::State &state) {
std::random_device rd;
std::mt19937 mt(rd());
std::uniform_int_distribution<int> dist;
while (state.KeepRunning()) {
std::vector<S> v;
v.reserve(state.range_x());
for (int i = 0; i < state.range_x(); i++) {
v.push_back({dist(mt)});
}
std::stable_sort(v.begin(), v.end(),
[](const S &a, const S &b) { return a.key < b.key; });
}
}
BENCHMARK(BM_StableSortStruct)->Arg(SIZE);
BENCHMARK_MAIN();
نصائح أخرى
std::stable_sort يؤدي مقارنات NlogN عندما ذاكرة كافية متوفرة. عندما تكون ذاكرة كافية متوفرة، فإنه يتحلل إلى N ((logN) ^ 2) المقارنات. ولذلك فمن تقريبا من نفس الكفاءة، std::sort (والذي يؤدي O (NlogN) مقارنات في كل من المتوسط، وأسوأ الأحوال) عندما الذاكرة المتوفرة.
لالمهتمين، نوع () يستخدم introsort مثل (quicksort الذي يتحول إلى heapsort عندما العودية تصل إلى عمق معين) وstable_sort () يستخدم دمج النوع .
وكبيرة بما يكفي لتبرير وظيفة منفصلة أن يفعل نوع مستقر وليس لديها std::sort() تفعل ذلك بشفافية.
وأحيانا الأمراض المنقولة جنسيا :: stable_sort () وهناك حاجة لأنها تحافظ على النظام من العناصر التي هي على قدم المساواة.
والنصيحة التقليدية هو أنه إذا حفظ النظام ليست مهمة، يجب عليك استخدام الأمراض المنقولة جنسيا :: نوع () بدلا من ذلك.
ولكن، سياقه التابعة. هناك الكثير من البيانات التي يتم فرزها مع أفضل نوع مستقر حتى لو كنت لا تحتاج للحفاظ على النظام:
وفرز سريع سرعان ما يصبح أداء أسوأ الحالات إذا كانت البيانات لديها نقاط الارتكاز رديئة باستمرار.
الجحور-ويلر تحويل هو الخوارزمية المستخدمة كجزء من ضغط البيانات، على سبيل المثال BZIP2 . فهو يتطلب فرز جميع تناوب النص. وبالنسبة لغالبية البيانات النص، ودمج النوع (كما غالبا ما يستخدمها الأمراض المنقولة جنسيا :: stable_sort ()) حد كبير أسرع من فرز سريع (كما يستخدمه عادة الأمراض المنقولة جنسيا :: نوع ()).
BBB هو تطبيق BWT أن تلاحظ مزايا الأمراض المنقولة جنسيا :: stable_sort () أكثر من نوع () لهذا التطبيق.
ما هو حجم فجوة الأداء في ممارسة؟ هل لديك بعض الخبرة حول ذلك؟
نعم، ولكنه لم يذهب بالطريقة التي تتوقعها.
وأخذت تنفيذ C من الجحور-ويلر تحويل وC ++ - ified ذلك. تحولت الكثير أبطأ من رمز C (على الرغم من رمز ونظافة). لذلك أضع توقيت الأجهزة في هناك، ويبدو أن qsort كان أداء أسرع من الأمراض المنقولة جنسيا :: نوع. كان هذا يعمل في VC6. ثم معاد مع stable_sort والاختبارات ركض أسرع من النسخة C. تمكنت تحقيق أمثلية أخرى لدفع C ++ نسخة ~ 25٪ أسرع من النسخة C. أعتقد أنه كان من الممكن أن يحتال المزيد من السرعة ولكن وضوح رمز وتختفي.
إذا كنت فرز عدد كبير من البنيات، وسرعة IO من الذاكرة / القرص يبدأ لتصبح أكثر أهمية من إدارة الوقت مقارب. وعلاوة على ذلك، ينبغي أن تؤخذ أيضا استخدام الذاكرة في الاعتبار.
وحاولت الأمراض المنقولة جنسيا :: stable_sort على 2GB من البيانات (البنيات 64B)، لا يعرفون أن الأمراض المنقولة جنسيا :: stable_sort يخلق نسخة الداخلية للبيانات. والتحطيم المبادلة التي تلت مقفل تقريبا حتى جهاز الكمبيوتر الخاص بي.
وعن طريق الأمراض المنقولة جنسيا غير مستقر :: نوع يقلل استخدام الذاكرة بمعامل 2، وهو أمر مفيد عندما يكون الترتيب صفائف كبيرة. I إنهاء الأمراض المنقولة جنسيا :: stable_sort، لذلك لا يمكن تحديد كيفية أبطأ بكثير ما كان عليه. ومع ذلك، إذا لا يشترط نوع مستقر، ثم أعتقد أنه من الأفضل استخدام الأمراض المنقولة جنسيا غير مستقر :: نوع.
كان يبحث عن شيء مماثل لكن فوجئت لا أحد تحدث عن مساعدة الفضاء.
كما أعتقد - تنفيذ كل stable_sort و هو نوع من المفترض أن تضمن O(NlogN) لجميع (أفضل متوسط & أسوأ) من الحالات.
ولكن الفرق موجود في مساعدة المساحة المستخدمة.stable_sort يحتاج المساعدة الفضاء O(N).
قد يكون الفرق في الأداء يكمن في الحصول على هذا الفضاء.:)
وإلا من الناحية النظرية - التي من المفترض أن تكون نفس ث.r.t الأداء.
نوع يجب أن تفعل ما عليك إلا إذا كنت بحاجة إلى هذا -> stable_sort يحافظ على النظام النسبي من عناصر ما يعادل القيم.
