143
правки
Изменения
→Некорректность timsort в Java
Также нужно сказать про [[Сортировка вставками | сортировку вставками]], которая используется для сортировки подмассивов <tex>run_i</tex>: в нашем случае, алгоритм работает за <tex>O(minrun + inv)</tex>, где <tex>\mathtt{inv}</tex> {{---}} число обменов элементов входного массива, равное числу инверсий. C учетом значения <tex>\mathtt{k}</tex> получим, что сортировка всех блоков может занять <tex>O(minrun + inv) \cdot k = O(minrun + inv) \cdot </tex><tex dpi=150>\left\lceil \frac{n}{minrun} \right\rceil </tex>. Что в худшем случае <tex dpi=150 >(inv = \frac{minrun(minrun - 1)}{2} )</tex> может занимать <tex>O(n \cdot minrun) </tex> времени. Откуда видно, что константа <tex>\mathtt{minrun}</tex> играет немалое значение: при большом <tex>\mathtt{minrun}</tex> слияний будет меньше, а сортировки вставками будут выполняться долго. Причём эти функции растут с разной скоростью, поэтому и ещё после эксперементов на различных значениях и был выбран оптимальный диапазон {{---}} от <tex>32</tex> до <tex>64</tex>.
== Некорректность timsort в Java ==
Метод mergeCollapce (Java) :
'''private void''' mergeCollapse() { //метод, содержащий ошибку
'''while''' (stackSize > 1) {
'''int''' n = stackSize - 2;
'''if''' (n > 0 && runLen[n-1] <= runLen[n] + runLen[n+1]) {
'''if''' (runLen[n - 1] < runLen[n + 1])
n--;
mergeAt(n);
} '''else if''' (runLen[n] <= runLen[n + 1]) {
mergeAt(n);
} '''else''' {
'''break'''; // инвариант установлен
}
}
}
В результате выполнения метода mergeCollapce, утверждается что для последних трех серий(runLen) выполняются следующие условия(инвариант):
*runLen[n - 2] > runLen[n - 1] + runLen[n]
*runLen[n - 1] > runLen[n]
Утверждается, что этого достаточно, но самом деле нет. Рассмотрим пример.
Пусть runLen содержит следующий набор длин:
<tex> 23, 16, 5, 4, 6 </tex>
На первом шаге в цикле будут объединены серии : 5 и 4 (5 < 4 + 6, 5 < 6). Получим:
<tex> 23, 16, 9, 6 </tex>
На втором шаге,в последней тройке устанавливается инвариант и mergeCollapse завершает свою работу, но инвариант для всего массива не восстановлен: он нарушается в первой тройке, так как 23 < 16 + 9.
В результате нарушения инварианта, длины серий растут медленнее, чем ожидалось, в результате чего их кол-во превышает runLen.length, что привод к ArrayOutOfBoundsException.
Основная идея исправления ошибки {{---}} проверять, что инвариант соблюдается для четырёх последних серий в runLen вместо трёх.
Таким образом, получаем следующее исправление:
'''private void''' newMergeCollapse() { //исправление
'''while''' (stackSize > 1) {
int n = stackSize - 2;
'''if''' ( (n >= 1 && runLen[n-1] <= runLen[n] + runLen[n+1])
|| (n >= 2 && runLen[n-2] <= runLen[n] + runLen[n-1])) {
'''if''' (runLen[n - 1] < runLen[n + 1])
n--;
} '''else if''' (runLen[n] > runLen[n + 1]) {
break; // Инвариант установлен
}
mergeAt(n);
}
}
== Источники информации==
