Коллеги, приветствую!

Вы попадали когда-то в ситуацию, когда TStringList.Sort сортирует список из 42196 элементов долго (точно больше 20 минут, дальше ждать не стал, срубил)?

Вот я сегодня попал. Сначала был в шоке. Прочел, что у алгоритма быстрой сортировки бывают такие косяки, когда есть неудачный исходный список. Но чтобы так...

Переписал на красно-черное бинарное дерево. Даже быстрее (в моем случае) стало.

Пишу, чтобы поделится мыслью - не верьте безгранично быстрой сортировке. Она коварная)))

Сча придет Ша и киданет ссылочку с разборами сортировок и быстрой в том числе. :)

Если так, то буду ждать с нетерпением. Т.к. Sha мне жутко помог года 3 назад с алгоритмом выставления порядка в списке путем перестановок. Я, правда, свой аналогичный написал. Но взял все же от Sha, ибо доверяю в части алгоритмов Sha безгранично))

> Тимохов Дима ©   (14.12.18 22:34) 

ты точно не опечатался?

у меня вот такой код

procedure TForm1.Button1Click(Sender: TObject);
begin
 var Data := TStringList.Create;
 try
   for var I := 0 to 42196 do
   begin
     Data.Add(TGUID.NewGuid.ToString);
   end;

   var Time1 := GetTickCount;
   Data.Sort;
   Time1 := GetTickCount - Time1;

   ShowMessage(Time1.ToString);
 finally
   Data.Free;
 end;
end;

показывает ровно 141 мс.

> Тимохов Дима ©   (14.12.18 22:34)  

При простом алгоритме сортировки таких времен быть никак не Должно.

> Eraser ©   (15.12.18 02:23) [3]
>
>
> > Тимохов Дима ©   (14.12.18 22:34)
>
> ты точно не опечатался?
>
> у меня вот такой код

Мой бывший директор, у которого я работал программистом окончательно ушел на пенсию. Похоже и мне  пора.

Коварен не алгоритм сортировки, а алгоритм сравнения при сортировке, который и создаёт тормоза.

Каковы размеры строк в списке?
В каком символе они преимущественно отличаются?
Быть может речь про запихивание в list строк по 100Кб, различающихся в десяти последних символах от начала?

Коллеги, ви мне не верите?
Погодите, создам течение дня тестовый пример. Вместе будем в шоке))

>алгоритм сравнения при сортировке, который и создаёт тормоза
asm cmp (он же if) в современных процессорах равен 1 такту.
Тормоза создают запись в переменную.

У меня Sort:
1. Миллион элементов ~5 сек.
2. 42196 элементов ~0.1 сек.

https://yadi.sk/d/uHnjyZP3fyi7Vw

удивимся вместе)))
ждать не стал - срубил после 3 минут.

на всякий случай, у меня Delphi2007.

order by нужен

program Project1;

{$APPTYPE CONSOLE}

uses
 Classes, SysUtils, Windows, Vcl.Dialogs;

var
 SL: TStringList;
 st, et, tt: Double;
 i: Integer;

begin

 SL := TStringList.Create;

 SL.LoadFromFile('data.txt');
 st := GetTickCount;
 SL.Sort;
 et := GetTickCount;
 tt := (et - st) / 1000.0;
 MessageDlg('Время: ' + FloatToStrF(tt, ffNumber, 18, 2) + ' сек.', mtInformation, [mbOk], 0, mbOk);

 SL.Free;
end.
У меня сортировалось 94.88 сек.
i7-6950 Extreme 3.0 ГГц.

> У меня сортировалось 94.88 сек.

все равно не мало, согласись.

у тебя Дельфи какой? Если отличный от моего, то пришли плз (timokhov собак gmail тчк com) текст TStringList.QuickSort.

> Тимохов Дима ©   (15.12.18 13:08) [10]

130 сек. на древнем i7-2600 (2011 год разработки).

когда же ты уже выкинешь этот делфи 2007? вопрос риторический )

> все равно не мало, согласись.

не мало, потому что не очень удобно для сортировки, по сравнению с рандомными значениями. по моему есть алгоритмы, оптимизированные для работы с частично отсортированными массивами.

> когда же ты уже выкинешь этот делфи 2007? вопрос риторический
> )


Мне он дорог как память)  Мне его лично Ник Ходжес прислал. Честно говоря, я так и не понял, за какие заслуги в тесте. Видимо, мелькал много)))

Ты код то пришли)

> Eraser ©   (15.12.18 16:35) [15]


просьба о TStringList.QuickSort снимается.
уверен, что она такая же.

дотерпел до конца. у меня 200 сек (комп старенький). как раз чуть больше трех минут, в прошлый раз не дотерпел.

но в боевом проекте в своем списке все же заменил быструю сортировку на сортировку по дереву. у меня там сравнение "дорогое", десятки минут получаются.

кстати, сортировка по бинарному дереву оказалась процентов на 30 быстрее в моих тестах. хотя, конечно, есть затраты памяти на само дерево, но для меня это несущественно.

всем спасибо за внимание)

>у тебя Дельфи какой?
Delphi XE6.

10000 - 6.3130 сек.
20000 - 23.1400 сек.
30000 - 47.3590 сек.
40000 - 85.8130 сек.
50000 - 133.9690 сек.

Вот код с генерацией строк.
program Project1;

{$APPTYPE CONSOLE}

uses
 Classes, SysUtils, Windows, Vcl.Dialogs, System.StrUtils, System.UITypes;

var
 SL: TStringList;
 st, et: Double;
 i, N: Integer;
 S: String;

const
 K: string = '|201410-';

begin

 SL := TStringList.Create;
 N := 50000;
 SL.Capacity := N;

 for i := 0 to (N div 2 - 1) do
 begin
   S := K + Format('%.5d', [i]) + '|';
   SL.Add(S);
 end;

 for i := (N div 2) downto 0 do
 begin
   S := K + Format('%.5d', [i]) + '|';
   SL.Add(S);
 end;

 Writeln('Генерация ' + IntToStr(N) + ' элементов завершена.');
 Writeln('Идет сортировка ...');

 st := GetTickCount;
 SL.Sort;
 et := GetTickCount;
 SL.Free;

 Writeln('Время: ' + FloatToStrF((et - st) * 0.001, ffNumber, 18, 4) + ' сек.');
 Readln;
end.

Чтобы ускорить переделай на AnsiString. Будет бестрее.

> Чтобы ускорить переделай на AnsiString. Будет бестрее.

Мне уже не актуально, я забраковал быструю сортировку в моем случае.
Хотя столько лет пользовался.

Сейчас просто у меня велик шанс иметь такие частично сортированные массивы.

Ну ее, эту быструю сортировку от греха подальше.

Красно-черные деревья оказались надежнее.
Хотя там при опред. кол-ве данных возможны просадки при ребалансировке.
Время покажет.