Насколько большой разрыв производительности между станд.:: вид и станд.:: stable_sort на практике?
Я не хочу пропагандировать поведение «простых вопросов», но это был достаточно простой вопрос:
const strBinSum = (str) => str
.split('') // split the string into individual characters
.map(s =>
s.charCodeAt(0).toString(2) // map them to their binary representation
)
.join('') // join the resulting array
.split('') // split it again
.filter(x => x === '1') // return only 1s
.length; // therefore summing it by returning the amount of 1s.
strBinSum('aB1@aaaaaa'); // 27
4 ответа
Достаточно большой, чтобы гарантировать отдельную функцию, которая выполняет стабильную сортировку и не имеет std :: sort () , сделать это прозрачно.
std :: stable_sort выполняет сравнение NlogN при наличии достаточного объема памяти. Когда недостаточно памяти, она ухудшается до N ((logN) ^ 2) сравнений. Следовательно, он примерно такой же эффективности, что и std :: sort (который выполняет сравнение O (NlogN) как в среднем, так и в худшем случае), когда память доступна.
Для заинтересованных лиц использование sort () introsort (быстрая сортировка, которая переключается на heapsort, когда рекурсия достигает определенной глубины), и stable_sort () использует сортировку слиянием .
Sometimes std::stable_sort() is needed because it maintains order of elements that are equal.
And the conventional advice is that, if maintaining order is not important, you should use std::sort() instead.
However, its context dependant. There is plenty of data that is best sorted with stable sort even if you don't need to maintain order:
Quicksort quickly becomes worst-case performance if the data has consistently poor pivot points.
The Burrows-Wheeler Transform is an algorithm used as part of data compression, e.g. bzip2. It requires sorting all the rotations of the text. For the majority of text data, merge sort (as often used by std::stable_sort()) is substantially faster than quicksort (as usually used by std::sort()).
bbb is a BWT implementation that notes the advantages of std::stable_sort() over sort() for this application.
How big is the performance gap in practice? Do you have some experience about that?
Yes, but it didn't go the way you would expect.
I took a C implementation of the Burrows-Wheeler Transform and C++-ified it. Turned out a lot slower than the C code (though the code was cleaner). So I put timing instrumentation in there and it appeared that the qsort was performing faster than the std::sort. This was running in VC6. It was then recompiled with stable_sort and the tests ran faster than the C version. Other optimisations managed to push the C++ version ~25% quicker than the C version. I think it was possible to eke more speed but the clarity of the code was disappearing.