По-моему кто-то давно уже говорил о Delphi, что если вам надо быстрый код — оптимизируйте алгоритм, остальное компилятор сделает сам.
Для оптимизации кода, как и вообще для написания серьёзного кода, желательно разбить код на фрагменты, "ортогональные" друг к другу, работающие независимо. Чтобы следовать этому принципу, приходится делать на первый взгляд не очень красивые вещи. Например, если мне надо сделать быструю сортировку, я не вставляю её алгоритм в то место где она нужна, а делаю примерно так:
tmparray:=tarray.create;
tmparray.count:=count;
for i:=0 to count-1 do tmparray.fitems[i]:=arr[i];
tmparray.superqsort;
for i:=0 to count-1 do arr[i]:=tmparray[i];
tmparray.free;
Раньше я не понимал принцип быстрой сортировки, а сейчас это кажется очень просто. Вот код, который я написал сходу; специально не тестировал, но уверен что в целом всё правильно:
procedure tdoublearray.superqsort;
var
q:integer;
sumval, midval, tmpval: double;
tmparray1, tmparray2: tdoublearray;
begin
if count<=1 then exit;
if count=2 then begin
if fitems[1]<fitems[0] then begin tmp:=fitems[1]; fitems[1]:=fitems[0]; fitems[0]:=tmp; end;
exit;
end;
sumval:=0;
for q:=0 to count do sumval:=sumval+fitems[q];
midval:=sumval/count;
tmparay1:=tdoublearray.create;
tmparray1.capacity:=count;
tmparray2:=tdoublearray.create;
tmparray2.capacity:=count;
for q:=0 to count-1 do if fitems[q]>midval then tmparray2.add(fitems[q]) else tmparray1.add(fitems[q]);
tmparray1.superqsort;
tmparray2.superqsort;
for q:=0 to tmparray1.count-1 do fitems[q]:=tmparray1.fitems[q];
for q:=0 to tmparray2.count-1 do fitems[tmparray1.count+q]:=tmparray2.fitems[q];
tmparray1.free;
tmparray2.free;
end;
Когда написал, понял что в этом коде есть маленький потенциальный баг, ну да это мелочи. На аналогичном принципе мне удалось ускорить в тысячу раз код, перебирающий атомы в брутто-формуле.
"Ты должен сделать добро из зла, потому что его больше не из чего сделать". АБ Стругацкие.
Здравствуйте, Khimik, Вы писали:
K>По-моему кто-то давно уже говорил о Delphi, что если вам надо быстрый код — оптимизируйте алгоритм, остальное компилятор сделает сам. K>Для оптимизации кода, как и вообще для написания серьёзного кода, желательно разбить код на фрагменты, "ортогональные" друг к другу, работающие независимо. Чтобы следовать этому принципу, приходится делать на первый взгляд не очень красивые вещи. Например, если мне надо сделать быструю сортировку, я не вставляю её алгоритм в то место где она нужна, а делаю примерно так:
K>Раньше я не понимал принцип быстрой сортировки, а сейчас это кажется очень просто. Вот код, который я написал сходу; специально не тестировал, но уверен что в целом всё правильно:
K>Когда написал, понял что в этом коде есть маленький потенциальный баг, ну да это мелочи. На аналогичном принципе мне удалось ускорить в тысячу раз код, перебирающий атомы в брутто-формуле.
Измерений не делал, но по виду кода такой алгоритм будет на порядок — два медленнее стандартного дельфового,
так как в нем огромное количество лишнего распределения памяти.
Может использовал бы стандартный — ускорил бы в сто тыщ раз, и некрасивый код с копированием данных не понадобился.
Сделай тест, сравни со стандартным.
И нахрена писать все в строчку.
S>Измерений не делал, но по виду кода такой алгоритм будет на порядок — два медленнее стандартного дельфового, S>так как в нем огромное количество лишнего распределения памяти. S>Может использовал бы стандартный — ускорил бы в сто тыщ раз, и некрасивый код с копированием данных не понадобился. S>Сделай тест, сравни со стандартным. S>И нахрена писать все в строчку.
Понятно что тут лишние такты уходят на выделение памяти, обработку классов и присвоения; полагаю, этот код примерно в 2-5 раз медленнее стандартной быстрой сортировки. Но всё равно для больших массивов он в миллион раз быстрее простой сортировки из двух вложенных циклов. Я же говорю что аналогичным алгоритмом ускорил одну процедуру в своей программе где-то в тысячу раз. Ну а если надо ещё ускорить, наверно первичное — заменить класс на рекорд в Delphi, и ещё наверно держать временные массивы не с числами а с указателями (индексами для исходного массива).
"Ты должен сделать добро из зла, потому что его больше не из чего сделать". АБ Стругацкие.
Здравствуйте, Khimik, Вы писали:
K>Здравствуйте, swame, Вы писали:
S>>Измерений не делал, но по виду кода такой алгоритм будет на порядок — два медленнее стандартного дельфового, S>>так как в нем огромное количество лишнего распределения памяти. S>>Может использовал бы стандартный — ускорил бы в сто тыщ раз, и некрасивый код с копированием данных не понадобился. S>>Сделай тест, сравни со стандартным. S>>И нахрена писать все в строчку.
K>Понятно что тут лишние такты уходят на выделение памяти, обработку классов и присвоения; полагаю, этот код примерно в 2-5 раз медленнее стандартной быстрой сортировки. Но всё равно для больших массивов он в миллион раз быстрее простой сортировки из двух вложенных циклов. Я же говорю что аналогичным алгоритмом ускорил одну процедуру в своей программе где-то в тысячу раз. Ну а если надо ещё ускорить, наверно первичное — заменить класс на рекорд в Delphi, и ещё наверно держать временные массивы не с числами а с указателями (индексами для исходного массива).
tdoublearray = class (TList<double>)
Потестировал, взяв tdoublearray = class (TList<double>) и исправив несколько ошибок в коде
твой код сливает стандартной сортировке, которая вызывается в 1 строчку, в 1,5 раза примерно во всем диапазоне. я думал , будет больше.
возможно на твоих классах будет еще медленней, TList<> отлично оптимизирован.
И это еще не считая дополнительного копирования.
Кроме того nвой код рухает, если встречаются одинаковые значения, а на 50 млн уже Out of memory.
Попросил еще ChatGPT сгенерить банальный quicksort он работает в 2,5 — 3 раза быстрей стандарного, и никаких копирований памяти.
В тесте он quick
procedure tdoublearray.QuickSort(low, high: Integer);
var
i, j: Integer;
pivot, temp: double;
begin
i := low;
j := high;
pivot := Items[(low + high) div 2];
repeat
while Items[i] < pivot do
Inc(i);
while Items[j] > pivot do
Dec(j);
if i <= j then
begin
temp := Items[i];
Items[i] := Items[j];
Items[j] := temp;
Inc(i);
Dec(j);
end;
until i > j;
if low < j then
QuickSort(low, j);
if i < high then
QuickSort(i, high);
end;
Здравствуйте, swame, Вы писали:
S>Попросил еще ChatGPT сгенерить банальный quicksort он работает в 2,5 — 3 раза быстрей стандарного, и никаких копирований памяти.
Честно говоря я немного туплю, не до конца понял как работает этот алгоритм. Т.е. понятно что он делает подмассивы прямо в исходном массиве, чтобы сэкономить память, но далее не совсем ясно. Раз уж вы смастерили бенчмарку, оцените насколько быстрый этот код:
procedure TDoubleArray.QSort(Ascending:boolean);
var
arr1,arr2:array of double;
boolarr:array of boolean;
i:integer;
procedure DoQSort(intervalbeg,intervallast:integer);
var
curcount:integer;
sumval:double;
aveval:double;
ii:integer;
curvalscount:integer;
lowvalscount:integer;
tmpval:double;
begin
curcount:=intervallast-intervalbeg+1;
if curcount<=1 then exit;//Всего один элемент, сортировать не надоif curcount=2 then
begin
if (arr1[intervalbeg]<arr1[intervallast])<>ascending then
begin
tmpval:=arr1[intervalbeg];
arr1[intervalbeg]:=arr1[intervallast];
arr1[intervallast]:=tmpval
end;
exit;
end;
//Находим среднее значение в нашем интервале:
sumval:=0;
for ii:=intervalbeg to intervallast do sumval:=sumval+arr1[ii];
aveval:=sumval/curcount;
for ii:=intervalbeg to intervallast do boolarr[ii]:=(arr1[ii]<aveval);
//Помещаем элементы, меньшие aveval, в первую часть arr2:
curvalscount:=0;
for ii:=intervalbeg to intervallast do if boolarr[ii]=ascending then
begin
inc(curvalscount);
arr2[intervalbeg+curvalscount-1]:=arr1[ii];
end;
lowvalscount:=curvalscount;
if (lowvalscount=0) or (lowvalscount=curcount) then
exit;//Все элементы в интервале равны, сортировать нельзя
//Помещаем элементы, большие или равные aveval, в первую часть arr2:for ii:=intervalbeg to intervallast do if boolarr[ii]=not ascending then
begin
inc(curvalscount);
arr2[intervalbeg+curvalscount-1]:=arr1[ii];
end;
//Перемещаем arr2 в arr1:for ii:=intervalbeg to intervallast do arr1[ii]:=arr2[ii];
doqsort(intervalbeg,intervalbeg+lowvalscount-1);
doqsort(intervalbeg+lowvalscount,intervallast);
end;
begin
setlength(arr1,fcount);
setlength(arr2,fcount);
setlength(boolarr,fcount);
for i:=0 to fcount-1 do arr1[i]:=fitems^[i];
doqsort(0,fcount-1);
for i:=0 to fcount-1 do fitems^[i]:=arr1[i];
setlength(arr1,0);
setlength(arr2,0);
setlength(boolarr,0);
end;
Этот код длиннее кода от GPT, но мне кажется понятнее. Не всегда в программировании чем код меньше — тем лучше. Может ещё код от GPT быстрый потому, что ссылается на массив в виде локальной переменной в процедуре, а у меня до этого он ссылался на массив в классе.
"Ты должен сделать добро из зла, потому что его больше не из чего сделать". АБ Стругацкие.
Здравствуйте, Khimik, Вы писали:
K>По-моему кто-то давно уже говорил о Delphi, что если вам надо быстрый код — оптимизируйте алгоритм, остальное компилятор сделает сам.
delphi так себе оптимизировал код. K>Для оптимизации кода, как и вообще для написания серьёзного кода, желательно разбить код на фрагменты, "ортогональные" друг к другу, работающие независимо.
Тут очень широкая тема. И так просто она не решается. Так как процессоры уже давно спекулятивные, память очень медленная, есть куча ухищрений что бы это нивилировать, множество вычислений могут быть выполнены на gpgpu с десятками тысяч ядер. Поэтому обычно не заморачиваются а используют уже оптимизированный код под определённые типовые задачи.
K>Чтобы следовать этому принципу, приходится делать на первый взгляд не очень красивые вещи.
Оптимизированный код обычно страшный и тяжело поддерживаемый. Поэтому это сваливают на компиляторы
K>Например, если мне надо сделать быструю сортировку, я не вставляю её алгоритм в то место где она нужна, а делаю примерно так:
если вам приходится так делать посмотрите другие языки где так не надо делать, например fortran
Re[5]: Оптимизация через разделение/вынос функционала
Здравствуйте, m2user, Вы писали:
S>>Попросил еще ChatGPT сгенерить банальный quicksort он работает в 2,5 — 3 раза быстрей стандарного, и никаких копирований памяти.
M>Но есть рекурсия.
Рекурсия есть во всех 3 вариантах, не вижу проблемы.
M>Вообще странно, что быстрее стандартного.
Стандартный код написал для дженириков с вызовами Comparer, большой оверхед на универсальность,
вариант GPT чисто для double так что вполне объяснимо.
Кто будет писать код под миллиардные массивы, будет оптимизировать под свой случай.
Re[5]: Оптимизация через разделение/вынос функционала
Здравствуйте, Khimik, Вы писали:
K>Здравствуйте, swame, Вы писали:
S>>Попросил еще ChatGPT сгенерить банальный quicksort он работает в 2,5 — 3 раза быстрей стандарного, и никаких копирований памяти.
K>Честно говоря я немного туплю, не до конца понял как работает этот алгоритм. Т.е. понятно что он делает подмассивы прямо в исходном массиве, чтобы сэкономить память, но далее не совсем ясно.
Не только память но и время.
K>Раз уж вы смастерили бенчмарку, оцените насколько быстрый этот код:
Извини время больше не буду тратить на эти эксперименты уровня первокурсника. Пиши тесты сам.
Просмотрел код принципиально то де что в предыдущем варианте те же лишние выделения памяти, с чего ему быть быстрее.
И по понятности он ужасен.
K>Этот код длиннее кода от GPT, но мне кажется понятнее. Не всегда в программировании чем код меньше — тем лучше.
Код GPT по-моему идеальный. Советую с ним разобраться и научиться писать так.
K>Может ещё код от GPT быстрый потому, что ссылается на массив в виде локальной переменной в процедуре, а у меня до этого он ссылался на массив в классе.
не из за этого. я написал что у тебя тормоза из-за выделений памяти.
Re[2]: Оптимизация через разделение/вынос функционала
Здравствуйте, kov_serg, Вы писали:
_>Здравствуйте, Khimik, Вы писали:
K>>По-моему кто-то давно уже говорил о Delphi, что если вам надо быстрый код — оптимизируйте алгоритм, остальное компилятор сделает сам. _>delphi так себе оптимизировал код.
Я как химик лет 10-20 назад тоже писал свои контейнеры, алгоритмы Delphi, но в отличие от химика они действительно были быстрей чем библиотечные функции того времени, часто в 2-5 раз. НО библиотеки Delphi совершенствуются, от версии к версии, и сейчас догнали мои наработки и превзошли. Так что я теперь постепенно выкидываю свои старые классы, заменяя на стандартные, которые отлично оптимизированы. Но их надо знать конечно "под капотом".
K>>Например, если мне надо сделать быструю сортировку, я не вставляю её алгоритм в то место где она нужна, а делаю примерно так: _>если вам приходится так делать посмотрите другие языки где так не надо делать, например fortran
В Delphi это тоже не надо делать, стандартный quicksort вызывается одной строчкой , химик просто не знает и пишет велосипед.
Не очень понятно, что этот пост делает в разделе "Философия программирования", ну да ладно.
Радует, что ты попробовал научиться сделать хоть что-то хорошо, отложив свои гениальные идеи по трансформации мироустройства. Этак, глядишь, лет через двадцать из тебя таки выйдет кодерок, которого можно подпускать к реальным задачам
Re[3]: Оптимизация через разделение/вынос функционала
Ладно, мне захотелось проверить и я написал свою бенчмарку:
Бенчмарка
procedure TMainForm.Button9Click(Sender: TObject);
var
firsttime:longword;
q,w:integer;
curarray:tdoublearray;
begin
firsttime:=GetTickCount;
for q:=0 to 800 do begin
curarray:=tdoublearray.Create;
curarray.Capacity:=10000;
for w:=0 to 9999 do curarray.Add(random);
curarray.QSort1Old;
curarray.Free;
end;//next q
caption:=inttostr(GetTickCount-firsttime);
end;
Мой изначальный код из оп (исправил ошибки)
procedure TDoubleArray.QSort1Old;
var
q:integer;
sumval, midval, tmpval: double;
tmparray1, tmparray2: tdoublearray;
tmp:double;
begin
if count<=1 then exit;
if count=2 then begin
if fitems[1]<fitems[0] then begin tmp:=fitems[1]; fitems[1]:=fitems[0]; fitems[0]:=tmp; end;
exit;
end;
sumval:=0;
for q:=0 to count-1 do sumval:=sumval+fitems[q];
midval:=sumval/count;
tmparray1:=tdoublearray.create;
tmparray1.capacity:=count;
tmparray2:=tdoublearray.create;
tmparray2.capacity:=count;
for q:=0 to count-1 do if fitems[q]>midval then tmparray2.add(fitems[q]) else tmparray1.add(fitems[q]);
tmparray1.QSort1Old;
tmparray2.QSort1Old;
for q:=0 to tmparray1.count-1 do fitems[q]:=tmparray1.fitems[q];
for q:=0 to tmparray2.count-1 do fitems[tmparray1.count+q]:=tmparray2.fitems[q];
tmparray1.free;
tmparray2.free;
end;
2.855 секунды.
Алгоритм GPT
procedure TDoubleArray.QSort2GPT;
var
arr:array of double;
q:integer;
procedure QSort(low,high:integer);
var
i, j: Integer;
pivot, temp: double;
begin
i := low;
j := high;
pivot := arr[(low + high) div 2];
repeat
while arr[i] < pivot do
Inc(i);
while arr[j] > pivot do
Dec(j);
if i <= j then
begin
temp := arr[i];
arr[i] := arr[j];
arr[j] := temp;
Inc(i);
Dec(j);
end;
until i > j;
if low < j then
QSort(low, j);
if i < high then
QSort(i, high);
end;
begin
setlength(arr,count);
for q:=0 to count-1 do arr[q]:=fitems[q];
qsort(0,count-1);
for q:=0 to count-1 do fitems[q]:=arr[q];
setlength(arr,0);
end;
0.983 секунды
Мой чуть улучшенный алгоритм из последнего поста
procedure TDoubleArray.QSort3My;
var
arr1,arr2:array of double;
boolarr:array of boolean;
i:integer;
procedure DoQSort(intervalbeg,intervallast:integer);
var
curcount:integer;
sumval:double;
aveval:double;
ii:integer;
curvalscount:integer;
lowvalscount:integer;
tmpval:double;
begin
curcount:=intervallast-intervalbeg+1;
if curcount<=1 then exit;//Всего один элемент, сортировать не надоif curcount=2 then
begin
if (arr1[intervalbeg]<arr1[intervallast])<>true then
begin
tmpval:=arr1[intervalbeg];
arr1[intervalbeg]:=arr1[intervallast];
arr1[intervallast]:=tmpval
end;
exit;
end;
//Находим среднее значение в нашем интервале:
sumval:=0;
for ii:=intervalbeg to intervallast do sumval:=sumval+arr1[ii];
aveval:=sumval/curcount;
for ii:=intervalbeg to intervallast do boolarr[ii]:=(arr1[ii]<aveval);
//Помещаем элементы, меньшие aveval, в первую часть arr2:
curvalscount:=0;
for ii:=intervalbeg to intervallast do if boolarr[ii]=true then
begin
inc(curvalscount);
arr2[intervalbeg+curvalscount-1]:=arr1[ii];
end;
lowvalscount:=curvalscount;
if (lowvalscount=0) or (lowvalscount=curcount) then
exit;//Все элементы в интервале равны, сортировать нельзя
//Помещаем элементы, большие или равные aveval, в первую часть arr2:for ii:=intervalbeg to intervallast do if boolarr[ii]=not true then
begin
inc(curvalscount);
arr2[intervalbeg+curvalscount-1]:=arr1[ii];
end;
//Перемещаем arr2 в arr1:for ii:=intervalbeg to intervallast do arr1[ii]:=arr2[ii];
doqsort(intervalbeg,intervalbeg+lowvalscount-1);
doqsort(intervalbeg+lowvalscount,intervallast);
end;
begin
setlength(arr1,fcount);
setlength(arr2,fcount);
setlength(boolarr,fcount);
for i:=0 to fcount-1 do arr1[i]:=fitems^[i];
doqsort(0,fcount-1);
for i:=0 to fcount-1 do fitems^[i]:=arr1[i];
setlength(arr1,0);
setlength(arr2,0);
setlength(boolarr,0);
end;
2.371 секунды.
Да, GPT алгоритм хорошо работает: то ли потому что не использует вычисления с плавающей точкой, то ли потому что не выделяет дополнительную память для массива, то ли сам алгоритм в принципе лучше — честно говоря я ещё до конца не понял что это за строки Inc(i); Dec(j);. А вы поняли?
Надо ещё протестировать. S>В Delphi это тоже не надо делать, стандартный quicksort вызывается одной строчкой , химик просто не знает и пишет велосипед.
Ну и как он вызывается?
"Ты должен сделать добро из зла, потому что его больше не из чего сделать". АБ Стругацкие.
Re[4]: Оптимизация через разделение/вынос функционала
Здравствуйте, Khimik, Вы писали:
K>2.371 секунды.
K>Да, GPT алгоритм хорошо работает: то ли потому что не использует вычисления с плавающей точкой, то ли потому что не выделяет дополнительную память для массива, то ли сам алгоритм в принципе лучше — честно говоря я ещё до конца не понял что это за строки Inc(i); Dec(j);. А вы поняли? K>Надо ещё протестировать.
Стандартный алгоритм из Delphi использует примерно такой же код. Но он медленней из-за универcальности.
class procedure TArray.QuickSort<T>(var Values: array of T; const Comparer: IComparer<T>;
L, R: Integer);
var
I, J: Integer;
pivot, temp: T;
begin
if L < R then
begin
repeat
if (R - L) = 1 then
begin
if Comparer.Compare(Values[L], Values[R]) > 0 then
begin
temp := Values[L];
Values[L] := Values[R];
Values[R] := temp;
end;
break;
end;
I := L;
J := R;
pivot := Values[L + (R - L) shr 1];
repeat
while Comparer.Compare(Values[I], pivot) < 0 do
Inc(I);
while Comparer.Compare(Values[J], pivot) > 0 do
Dec(J);
if I <= J then
begin
if I <> J then
begin
temp := Values[I];
Values[I] := Values[J];
Values[J] := temp;
end;
Inc(I);
Dec(J);
end;
until I > J;
if (J - L) > (R - I) then
begin
if I < R then
QuickSort<T>(Values, Comparer, I, R);
R := J;
end
else
begin
if L < J then
QuickSort<T>(Values, Comparer, L, J);
L := I;
end;
until L >= R;
end;
end;
Здравствуйте, swame, Вы писали:
S>Стандартный алгоритм из Delphi использует примерно такой же код. Но он медленней из-за универcальности.
Я понял что мой алгоритм был медленнее gpt-шного из-за операций с плавающей точкой (вычисление среднего). Вот ещё его поправил, заменил на среднее по минимальному и максимальному значению:
procedure TDoubleArray.QSort4MyNoFloatSum;
var
arr1,arr2:array of double;
boolarr:array of boolean;
i:integer;
procedure DoQSort(intervalbeg,intervallast:integer; hasminval,hasmaxval:boolean; minval,maxval:double);
const
MaxFloat=1E50;
var
curcount:integer;
aveval:double;
ii:integer;
curvalscount:integer;
lowvalscount:integer;
tmpval:double;
begin
curcount:=intervallast-intervalbeg+1;
if curcount<=1 then exit;//Всего один элемент, сортировать не надоif curcount=2 then
begin
if (arr1[intervalbeg]<arr1[intervallast])<>true then
begin
tmpval:=arr1[intervalbeg];
arr1[intervalbeg]:=arr1[intervallast];
arr1[intervallast]:=tmpval
end;
exit;
end;
if not hasminval then
begin
minval:=MaxFloat;
for ii:=intervalbeg to intervallast do if arr1[ii]<minval then minval:=arr1[ii];
end;
if not hasminval then
begin
maxval:=-MaxFloat;
for ii:=intervalbeg to intervallast do if arr1[ii]>maxval then maxval:=arr1[ii];
end;
aveval:=(minval+maxval)*0.5;
for ii:=intervalbeg to intervallast do boolarr[ii]:=(arr1[ii]<aveval);
//Помещаем элементы, меньшие aveval, в первую часть arr2:
curvalscount:=0;
for ii:=intervalbeg to intervallast do if boolarr[ii]=true then
begin
inc(curvalscount);
arr2[intervalbeg+curvalscount-1]:=arr1[ii];
end;
lowvalscount:=curvalscount;
if (lowvalscount=0) or (lowvalscount=curcount) then
exit;//Все элементы в интервале равны, сортировать нельзя
//Помещаем элементы, большие или равные aveval, в первую часть arr2:for ii:=intervalbeg to intervallast do if boolarr[ii]=not true then
begin
inc(curvalscount);
arr2[intervalbeg+curvalscount-1]:=arr1[ii];
end;
//Перемещаем arr2 в arr1:for ii:=intervalbeg to intervallast do arr1[ii]:=arr2[ii];
doqsort(intervalbeg,intervalbeg+lowvalscount-1,true,false,minval,0);
doqsort(intervalbeg+lowvalscount,intervallast,false,true,0,maxval);
end;
begin
setlength(arr1,fcount);
setlength(arr2,fcount);
setlength(boolarr,fcount);
for i:=0 to fcount-1 do arr1[i]:=fitems^[i];
doqsort(0,fcount-1,false,false,0,0);
for i:=0 to fcount-1 do fitems^[i]:=arr1[i];
setlength(arr1,0);
setlength(arr2,0);
setlength(boolarr,0);
end;
С этим кодом получилось 0.484 секунды, т.е. в два раза быстрее GPT-шного. С другой стороны мой алгоритм использует больше памяти. Если честно, я туплю и не понял до сих пор что там выполняется в GPT-шном или стандартном алгоритме, можете словами сформулировать? Я конечно могу и сам понять, только лень скрипеть мозгами.
"Ты должен сделать добро из зла, потому что его больше не из чего сделать". АБ Стругацкие.
Re[6]: Оптимизация через разделение/вынос функционала
Здравствуйте, Khimik, Вы писали:
K>Здравствуйте, swame, Вы писали:
S>>Стандартный алгоритм из Delphi использует примерно такой же код. Но он медленней из-за универcальности.
K>С этим кодом получилось 0.484 секунды, т.е. в два раза быстрее GPT-шного. С другой стороны мой алгоритм использует больше памяти. Если честно, я туплю и не понял до сих пор что там выполняется в GPT-шном или стандартном алгоритме, можете словами сформулировать? Я конечно могу и сам понять, только лень скрипеть мозгами.
А ты проверил свой алгоритм?
ОН cортирует правильно? Результат совпадает со стандартным? отрабатывает совпадающие значения?
Когда проверишь посмотрю, хотя что он быстрей верится слабо.
Re[6]: Оптимизация через разделение/вынос функционала
K> Если честно, я туплю и не понял до сих пор что там выполняется в GPT-шном или стандартном алгоритме, можете словами сформулировать? Я конечно могу и сам понять, только лень скрипеть мозгами
В википедии есть статья QuickSort. Там и анимация и объяснение.
Нет такой подлости и мерзости, на которую бы не пошёл gcc ради бессмысленных 5% скорости в никому не нужном синтетическом тесте
Re[7]: Оптимизация через разделение/вынос функционала
Здравствуйте, swame, Вы писали:
S>А ты проверил свой алгоритм? S>ОН cортирует правильно? Результат совпадает со стандартным? отрабатывает совпадающие значения? S>Когда проверишь посмотрю, хотя что он быстрей верится слабо.
Проверил. Ох, да, сорри, в моём коде с процедурой QSort4MyNoFloatSum ошибка (второй if not hasminval then надо заменить на if not hasmaxval then). Сейчас он делает правильно, но длится это 2.558 секунд, т.е. даже чуть медленнее моего кода с подсчётом среднего. Буду разбираться дальше.
Вы можете сейчас сказать, почему стандартная/gpt сортировка выполняется быстрее моей? Понимаете её суть? Как я уже сказал, мне пока чуть лень скрипеть мозгами.
"Ты должен сделать добро из зла, потому что его больше не из чего сделать". АБ Стругацкие.
K>> Если честно, я туплю и не понял до сих пор что там выполняется в GPT-шном или стандартном алгоритме, можете словами сформулировать? Я конечно могу и сам понять, только лень скрипеть мозгами
TB>В википедии есть статья QuickSort. Там и анимация и объяснение.
Начал читать, тоже немного лень вникать. У меня сейчас такой вопрос: вот этот код в GPT-алгоритме — это разбиение Ломуто или схема Хоара или что-то другое?
repeat
while arr[i] < pivot do
Inc(i);
while arr[j] > pivot do
Dec(j);
if i <= j then
begin
temp := arr[i];
arr[i] := arr[j];
arr[j] := temp;
Inc(i);
Dec(j);
end;
until i > j;
"Ты должен сделать добро из зла, потому что его больше не из чего сделать". АБ Стругацкие.
Re[8]: Оптимизация через разделение/вынос функционала
Посмотрел другие варианты размера сортируемого массива: вроде соотношение времени работы алгоритмов не зависит, или почти не зависит, от размера массива. Всегда мой алгоритм с подсчётом среднего (QSort3My) работает примерно в 1.3 раза медленнее GPT-шного. Предлагаю проанализировать, почему так.
"Ты должен сделать добро из зла, потому что его больше не из чего сделать". АБ Стругацкие.
