Re: Оптимизация через разделение/вынос функционала
От: Khimik  
Дата: 20.06.24 17:39
Оценка: :)
Азарту ради, я написал код с сортировкой с использованием дополнительной памяти (деление интервала значений на секции):

  Скрытый текст
procedure TDoubleArray.QSort10Sections;
const
SectionsCount=100;
var
sectionsize:integer;
Sections:array[0..SectionsCount-1] of tdoublearray;
q,w:integer;
minval,maxval:double;
interval:double;
begin
if fcount<300 then begin
QSort2GPT;
exit;
end;


minval:=MaxSafeFloat;
maxval:=-MaxSafeFloat;
for q:=0 to fcount-1 do begin
if fitems[q]<minval then minval:=fitems[q];
if fitems[q]>maxval then maxval:=fitems[q];
end;//next q

minval:=minval-minsafefloat;
maxval:=maxval+minsafefloat;
interval:=maxval-minval;

sectionsize:=fcount div sectionscount;
for q:=0 to sectionscount-1 do begin
sections[q]:=TDoubleArray.Create;
sections[q].Capacity:=sectionsize*10;
end;

for q:=0 to fcount-1 do begin
sections[floor((sectionscount-1)*(fitems[q]-minval)/interval)].Add(fitems[q]);
end;

count:=0;
for q:=0 to SectionsCount-1 do begin
sections[q].QSort10Sections;
for w:=0 to sections[q].fcount-1 do add(sections[q].fitems[w]);
sections[q].Free;
end;


end;


Прежде чем кликать по спойлеру, ответьте на вопрос — вы бы легко написали этот алгоритм?
Мой алгоритм вышел примерно на 30% быстрее стандартной быстрой сортировки со схемой Хоара. Памяти он расходует не особо много. А вы бы опять искали готовый алгоритм вместо голимого придумывания велосипеда?
"Ты должен сделать добро из зла, потому что его больше не из чего сделать". АБ Стругацкие.
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.