Мастера DELPHI, Delphi programming community Рейтинг@Mail.ru Титульная страница Поиск, карта сайта Написать письмо 
| Новости |
Новости сайта
Поиск |
Поиск по лучшим сайтам о Delphi
FAQ |
Огромная база часто задаваемых вопросов и, конечно же, ответы к ним ;)
Статьи |
Подборка статей на самые разные темы. Все о DELPHI
Книги |
Новинки книжного рынка
Новости VCL
Обзор свежих компонент со всего мира, по-русски!
|
| Форумы
Здесь вы можете задать свой вопрос и наверняка получите ответ
| ЧАТ |
Место для общения :)
Орешник
Коллекция курьезных вопросов из форумов
Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / rsdn.org

 
Чтобы не потерять эту дискуссию, сделайте закладку « предыдущая ветвь | форум | следующая ветвь »
Страницы: 1 2 3

Быстрая сортировка


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

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

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

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

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

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


ухты ©   (14.12.18 22:54[1]

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


Тимохов Дима ©   (14.12.18 23:29[2]

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


Eraser ©   (15.12.18 02:23[3]


> Тимохов Дима ©   (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 мс.


Германн ©   (15.12.18 03:04[4]


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

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

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

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


Dimka Maslov ©   (15.12.18 11:29[5]

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


KSergey ©   (15.12.18 12:00[6]

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


Тимохов Дима ©   (15.12.18 12:09[7]

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


dmk ©   (15.12.18 12:38[8]

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


dmk ©   (15.12.18 13:08[9]

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


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

https://yadi.sk/d/uHnjyZP3fyi7Vw

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

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


ухты ©   (15.12.18 14:53[11]

order by нужен


dmk ©   (15.12.18 15:11[12]

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 ГГц.


Тимохов Дима ©   (15.12.18 15:14[13]


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

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

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


Eraser ©   (15.12.18 16:32[14]


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

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

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


Eraser ©   (15.12.18 16:35[15]


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

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


Тимохов Дима ©   (15.12.18 16:36[16]


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


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

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


Тимохов Дима ©   (15.12.18 16:59[17]


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


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

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

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

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

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


dmk ©   (15.12.18 17:19[18]

>у тебя Дельфи какой?
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. Будет бестрее.


Тимохов Дима ©   (15.12.18 17:30[19]


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

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

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

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

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


Страницы: 1 2 3 версия для печати

Написать ответ

Ваше имя (регистрация  E-mail 







Разрешается использование тегов форматирования текста:
<b>жирный</b> <i>наклонный</i> <u>подчеркнутый</u>,
а для выделения текста программ, используйте <code> ... </code>
и не забывайте закрывать теги! </b></i></u></code> :)


Наверх

  Рейтинг@Mail.ru     Титульная страница Поиск, карта сайта Написать письмо