Re[5]: Оптимизация через разделение/вынос функционала
От: Khimik  
Дата: 21.06.24 15:24
Оценка: :))) :)
Здравствуйте, swame, Вы писали:

S>Мой тест показал, что твой алгоритм сопоставим по +/- по скорости со стандартным TList <double>.Sort

S>(как раз из за того что внутри использует QSort2GPT)
S>и, как и прежде в 2-5 раз медленней quick QSort2GPT.
S>При этом расходует в 100 раз и больше памяти. на 5 млн элементов уже переполняет память.
S>ты просто замедлил отсебятиной QSort2GPT
S>Так что на помойку и хватит бредить.

А вы покажите полностью код для вашего теста. Могу предположить, что ваш вариант медленнее из-за заполнения нулями динамических массивов при инициализации. У меня используется мой класс tdoublearray, представляющий собой кастомный динамический массив:


  Скрытый текст
TDoubleArray=class(tsafeobject)
private

public
fcount:integer;
fcapacity:integer;
procedure SetCount(newcount:integer);
procedure SetCapacity(newcapacity:integer);
//procedure SetCapacityQuick(newcapacity:integer);
//Странно, выходит и setcapacity не заполняет нулями. И setcount значит тоже
function GetItem(index: integer): double;
procedure SetItem(index: integer; Value: double);
public
fitems:pdoublearr;
procedure CopyToSimpleArray(var arr:array of double);
destructor Destroy; override;
property Items[index:integer]:double read GetItem write SetItem; default;
property Count:integer read fcount write setcount;
property Capacity:integer read fcapacity write SetCapacity;
function FirstPointer:pdoublearr;
procedure Grow;
procedure Clear;
function SafeGetItem(ind:integer; errval:double):double;//Если выходит за границы индекса - возвращает errval
function TryGetItem(ind:integer; out res:double):boolean;
procedure SetZeroValues(newcount:integer);
procedure SetBlankValues(newcount:integer; newval:double);
procedure Add(value:double);
procedure AddArray(otherarray:tdoublearray);
procedure SwapPoints(pointnum1,pointnum2:integer);
procedure Assign(otherarray:tdoublearray);
procedure SortByGrowing;
function LinInterValue(kx:double):double;//kx-положение в массиве (в вещественных координатах);0 - первая точка, 1 - вторая, 0.5 - посередине
function LagrInterpValue(kx:double; polnum:integer):double;//Интерполяция по Лагранжу: polnum - стенень полинома (должно быть четное число). 2 - линейная интерполяция
function SumValues:double;
function MaxValue:double;
function HasNonZeroValues:boolean;
procedure QSort(ascending:boolean);
procedure SmoothAdjacentAveraging(numpoints:integer);
procedure GetValuesInterval(minval,maxval:double; out minn,maxn:integer);//определяет интервал точек, попадающих
//в указанные границы (предполагается что точки в массиве расположены по возрастанию)
function GetSortedNums(ascending:boolean):tintarray;
//Возвращает список номеров своих элементов, отсортированных по возрастанию (если ascending=true) или убыванию
function ValuesAreEquiDistant(out beg,step:double):boolean;//Возвращает false если чисел 0 или 1
//Также возвращает false если все значения равны
function ValuesAreSubsequent(out beg,step:double):boolean;//Возвращает true если идёт непрерывная последовательность эквидистантных значений, постоянно увеличивающихся
//Возвращает false если чисел 0; если 1, возвращает true и step 1
procedure AddValues(val:double);
procedure MultValues(val:double);
end;

procedure TDoubleArray.SetCount(newcount: integer);
begin
if newcount>fcapacity then setcapacity(newcount);
fcount := newcount;
end;


procedure TDoubleArray.SetCapacity(newcapacity: integer);
begin
  if NewCapacity < fCount then
    raise exception.Create('NewCapacity='+inttostr(NewCapacity));
  if NewCapacity <> fCapacity then
  begin
    ReallocMem(fitems, NewCapacity * SizeOf(double));
    FCapacity := NewCapacity;
  end;
end;


procedure TDoubleArray.Add(value: double);
begin
fcount:=fcount+1;
if fcount>fcapacity then grow;
fitems^[fcount-1]:=value;
end;


Я получил выигрыш в скорости 30% для массивов из 100 000 чисел с равномерно распределенными random-ами.
И если вы даже не можете сразу понять принцип моего алгоритма (и почему он работает быстро), это очередной пример что "профессиональные программеры" с rsdn могут заимствовать чужие идеи, но не генерировать свои. Я в КСВ об этом создал тему.
"Ты должен сделать добро из зла, потому что его больше не из чего сделать". АБ Стругацкие.
Отредактировано 21.06.2024 15:29 Khimik . Предыдущая версия .
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.