Integer Array sortieren

[DieDolly]

Ich glaube ich sehe den Wald vor lauter Bäumen nicht.
Wie sortiert man ein Integer Array?

Delphi-Quellcode:

//Mein Array
IndexListe: TArray<Integer>;

// Sortiert man nicht etwa so?
TArray.Sort<Integer>(IndexListe);

Ich bekomme den Fehler, dass es für diesen Aufruf keine überladene Version von Sort gibt.

[bernau]

Nicht getestet. Aber so in etwa.

Delphi-Quellcode:

var
  lComparer: IComparer<Integer>;
begin
  lComparer := TDelegatedComparer < Integer >.create(
    function(const Left, Right: Integer): Integer
    begin
        Result := Left-Right;
    end);

  IndexListe.Sort(lComparer);
end;

Edit: Vergiss es. Das war TList.

[DieDolly]

So ganz komme ich nicht dahinter.

In System.Generics.Collections.pas steht
class procedure Sort<T>(var Values: array of T);
Aber weder deine Variante noch meine werden erkannt

TArray.Sort<Integer>(IndexListe, lComparer);


Edit
ich glaube ich habe den Fehler.
IndexListe war als const im Parameterkopf deklariert. Das Const muss weg.

[bernau]

Vielleicht damit. (Nicht getestet)

Delphi-Quellcode:

  
TArray.Sort<Integer>(aArray, TComparer<Integer>.Construct(
  function (const A, B: integer): Integer
  begin
    Result := a-b;
  end));

[DieDolly]

Const ist weg und dein Comparer drin. Funktioniert jetzt bestens.

[Michael II]

TArray.Sort<Integer>(arr); {1}
funktioniert und ist über 10 Mal schneller als mit "eigenem Comparer" ({2} {3}).

Der oben vorgeschlagene Comparer Result := a-b; {2} funktioniert nicht für alle möglichen Array-Werte; zum Beispiel nicht für den Array mit den zwei Elementen maxint, -maxint.

Der Comparer {3} sortiert korrekt, ist aber wie {2} über 10 Mal langsamer als {1}.

Delphi-Quellcode:

uses
  System.Generics.Collections, { TArray }
  System.Generics.Defaults; { TComparer<T> }

...


var arr, brr : TArray<integer>;

...

{1}
  TArray.Sort<Integer>(arr);

{2} // sortiert nicht korrekt
  TArray.Sort<Integer>(brr, TComparer<Integer>.Construct(
  function (const A, B: integer): Integer
  begin
    Result := a-b;
  end));

{3}
    TArray.Sort<Integer>(brr, TComparer<Integer>.Construct(
  function (const A, B: integer): Integer
  begin
    if a < b then Result := -1
    else
    if a = b then Result := 0
    else Result := 1;
  end));

[DieDolly]

Ich habe dein Beispiel gerade mal nachgestellt.
2.000.000 Durchgänge mit einem 100er Integer-Array.

{1}: 3650 Millisekunden
{2}: 34955 Millisekunden
{2}: 34602 Millisekunden

Sehre unschöner Code aber das ist bei so einem kleinen Test mehr als egal.

Delphi-Quellcode:

var
 SW: TStopwatch;
 i: Integer;
 IntArray: TArray<Integer>;
 A, B, C: Integer;
begin
 SW := TStopwatch.StartNew;
 for i := 0 to 1999999 do
  begin
   IntArray := TArray<Integer>.Create(72, 59, 80, 78, 90, 34, 27, 23, 51, 25, 66, 69, 45, 35, 30, 16, 92, 73, 61, 18, 68, 39, 1, 84, 53, 93, 65, 42, 6, 54, 99, 46, 100, 24, 11, 87, 76,
    79, 56, 5, 22, 64, 8, 94, 95, 7, 21, 77, 71, 29, 12, 55, 20, 37, 49, 19, 52, 96, 9, 91, 57, 44, 67, 74, 88, 32, 75, 31, 28, 36, 89, 47, 82, 14, 3, 85, 58, 97, 60, 62, 2, 15, 17, 86,
    41, 98, 48, 81, 83, 40, 4, 63, 10, 50, 33, 70, 43, 38, 13, 26);

   TArray.Sort<Integer>(IntArray);
  end;
 SW.Stop;
 A := SW.ElapsedMilliseconds;

 //

 SW := TStopwatch.StartNew;
 for i := 0 to 1999999 do
  begin
   IntArray := TArray<Integer>.Create(72, 59, 80, 78, 90, 34, 27, 23, 51, 25, 66, 69, 45, 35, 30, 16, 92, 73, 61, 18, 68, 39, 1, 84, 53, 93, 65, 42, 6, 54, 99, 46, 100, 24, 11, 87, 76,
    79, 56, 5, 22, 64, 8, 94, 95, 7, 21, 77, 71, 29, 12, 55, 20, 37, 49, 19, 52, 96, 9, 91, 57, 44, 67, 74, 88, 32, 75, 31, 28, 36, 89, 47, 82, 14, 3, 85, 58, 97, 60, 62, 2, 15, 17, 86,
    41, 98, 48, 81, 83, 40, 4, 63, 10, 50, 33, 70, 43, 38, 13, 26);

   TArray.Sort<Integer>(IntArray, TComparer<Integer>.Construct(
    function(const A, B: Integer): Integer
    begin
     Result := A - B;
    end));
  end;
 SW.Stop;
 B := SW.ElapsedMilliseconds;

 //

 SW := TStopwatch.StartNew;
 for i := 0 to 1999999 do
  begin
   IntArray := TArray<Integer>.Create(72, 59, 80, 78, 90, 34, 27, 23, 51, 25, 66, 69, 45, 35, 30, 16, 92, 73, 61, 18, 68, 39, 1, 84, 53, 93, 65, 42, 6, 54, 99, 46, 100, 24, 11, 87, 76,
    79, 56, 5, 22, 64, 8, 94, 95, 7, 21, 77, 71, 29, 12, 55, 20, 37, 49, 19, 52, 96, 9, 91, 57, 44, 67, 74, 88, 32, 75, 31, 28, 36, 89, 47, 82, 14, 3, 85, 58, 97, 60, 62, 2, 15, 17, 86,
    41, 98, 48, 81, 83, 40, 4, 63, 10, 50, 33, 70, 43, 38, 13, 26);

   TArray.Sort<Integer>(IntArray, TComparer<Integer>.Construct(
    function(const A, B: Integer): Integer
    begin
     if A < B then
      Result := -1
     else if A = B then
      Result := 0
     else
      Result := 1;
    end));
  end;
 SW.Stop;
 C := SW.ElapsedMilliseconds;

 Caption := '{1}: ' + A.ToString + ', {2}: ' + B.ToString + ', {3}: ' + C.ToString;
end;

[Michael II]

Hallo DieDolly

damit bestätigst du die Zeitunterschiede.

Viel wichtiger ist aber, dass Comparer {2}

Zitat:

Const ist weg und dein Comparer drin. Funktioniert jetzt bestens.

nicht korrekt sortiert, wenn die arr[i] in [-maxint-1..maxint] liegen.

Nebenbei:
Du könntest Test Arrays mit vielen Elementen auch so (und natürlich auch anders ) erzeugen:

Delphi-Quellcode:

  setlength( arr, 10000000 );
  for i := 0 to length(arr)-1 do
  arr[i] := random(maxint) - random(maxint);