delover
Advanced Member | Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
LadyOfWood
Да Вы правы, это слабое улучшение, но оно сказывается так же и на использование стека. 1)Если Ваше приложение серверное или имеет тип служба и предполагает потоковые обработки, то использование стека может быть весьма существенным.
2)Такие среды разработки как Сишарп (интерпретируемые) сильно уступают в скорости сортировки, для них улучшение весьма существенное.
3)В моём случае существует Сишарп служба которая тратит на один из своих шагов 6 часов. Там цикл внутри которого работа с 400 тысячами наименований продуктов поступивших от точек. Создание индекса занимает на Delphi 2 минуты для трёх миллионов. Значит вместо службы я создам локальный индекс за 40 секунд и проделаю работу за 3 минуты. 3 минуты против 6 часов Сишарпа.
Я тут выяснил, что для обратной сортировки - случай 3 2 1, выбирается медианой 1. В хаотичных данных это иногда верно иногда не верно, по этому не особо заметно. Однако в обратно сортированных данных лучше возвращать медиану на место. В этом случае я бы даже предусмотрел счётчик, который либо обнуляется если мы не возвращали медиану либо накапливается. При набранном пороговом значении можно отключать выбор медианы так как огромный шанс, что мы включили обратную сортировку. Это так же актуально в локальных гридинах. Однако меня интересует именно элементарное улучшение алгоритма и глобальный счётчик мне кажется избыточен. Если 5 миллионов это 15 секунд выигрыша, то 65 тысяч это примерно 150 миллисекунд. По отношению к двум минутам меня более интересуют 15 секунд, так как если я ждал 2 минуты - то я не замечу 150 миллисекунд.
Добавлено:
Улучшение 2.
Код: T := (P - I) shr 2;
if T > 16 then
begin
if SCompare(SortList[P - T], SortList[P]) < 0 then
begin
if SCompare(SortList[P], SortList[P + T]) > 0 then
Inc(P, T);
end else
begin
Dec(P, T);
if SCompare(SortList[P], SortList[P + (T shl 1)]) > 0 then
begin
Inc(P, T);
if SCompare(SortList[P], SortList[P + T]) < 0 then //<-- третье сравнение
Inc(P, T);
end;
end;
end; |
Оно принесло уже выигрыш 7 миллионов - 7478839. А так же облегчило обратную сортировку.
Добавлено:
LadyOfWood
Цитата:| Проблема в том что мало кому надо сортировать миллионны строк, а вот на небольших массивах разница может не быть или будет слабо заметна. |
В большинстве случаев в гридинах не более 5000 записей и на этих данных моё улучшение просто безобидно. Но в тех случаях когда Вы начинаете сортировать по 60 тысяч, Вы постоянно выигрываете миллисекунды на хороших компах - как у меня, а на плохих ещё больше выигрыш.
Добавлено:
Изменений в глубине используемого стека я не заметил. Странно но 1320 байт в обоих случаях - мизер какой-то. Да и ещё странно - дома комп новый процессор + 64 система + 8Гб памяти - сортирует 3 с половиной минуты. На работе комп старый + 4гб + 32 система сортирует 2 с половиной минуты. 64 ещё сыровата для сортировки строк. |
