Здравствуйте, 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 быстрый потому, что ссылается на массив в виде локальной переменной в процедуре, а у меня до этого он ссылался на массив в классе.

Здравствуйте, 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 быстрый потому, что ссылается на массив в виде локальной переменной в процедуре, а у меня до этого он ссылался на массив в классе.