Hilfe: Schnellste möglichkeit ein 4-Byte Array zu Sortieren

[Bjoerk]

Horst, kannst du hier mal die asm routinen einbauen und testen? Wenn du mehr als 1 bis 2 Sekunden einsparst, wäre das m.E. schon ziemlich genial.

Delphi-Quellcode:

unit uArrayOfByteList;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, StdCtrls;

type
  TArrayOfByte = packed record
    case boolean of
      true: (A: array[0..3] of Byte);
      false: (Card: Cardinal);
  end;

  TArrayOfByteList = class(TList)
  private
    function GetItem(Index: integer): TArrayOfByte;
    procedure SetItem(Index: integer; const Value: TArrayOfByte);
  public
    procedure AddItem(const Value: TArrayOfByte);
    procedure DelItem(Index: integer);
    function Networksort(Index: integer): TArrayOfByte;
    function Selectionsort(Index: integer): TArrayOfByte;
    procedure SelectionsortASM(var A: TArrayOfByte);
    procedure SelectionsortASM2(var A: TArrayOfByte);
    procedure SelectionsortASM2Horst(var A: TArrayOfByte);
    procedure SelectionsortASM3Horst(var A: TArrayOfByte);
    property Item[Index: integer]: TArrayOfByte read GetItem write SetItem; default;
    destructor Destroy; override;
  end;

  TWaitTime = class
  private
    FStartTime: TDateTime;
    FWaitTime: int64;
  public
    procedure Start;
    procedure Stop;
    property WaitTime: int64 read FWaitTime;
  end;

  TForm1 = class(TForm)
    Button1: TButton;
    Button2: TButton;
    Button3: TButton;
    Button4: TButton;
    Button5: TButton;
    Button6: TButton;
    procedure Button1Click(Sender: TObject);
    procedure Button2Click(Sender: TObject);
    procedure FormCreate(Sender: TObject);
    procedure FormDestroy(Sender: TObject);
    procedure Button3Click(Sender: TObject);
    procedure Button4Click(Sender: TObject);
    procedure Button5Click(Sender: TObject);
    procedure Button6Click(Sender: TObject);
  end;

var
  Form1: TForm1;
  ArrayOfByteList: TArrayOfByteList;
  WaitTime: TWaitTime;

implementation

{$R *.dfm}

{ TArrayOfByteList }

function TArrayOfByteList.GetItem(Index: integer): TArrayOfByte;
var
  P: ^TArrayOfByte;
begin
  P:= Items[Index];
  Result:= P^;
end;

procedure TArrayOfByteList.SetItem(Index: integer; const Value: TArrayOfByte);
var
  P: ^TArrayOfByte;
begin
  P:= Items[Index];
  P^:= Value;
end;

procedure TArrayOfByteList.AddItem(const Value: TArrayOfByte);
var
  P: ^TArrayOfByte;
begin
  New(P);
  P^:= Value;
  Add(P);
end;

procedure TArrayOfByteList.DelItem(Index: integer);
var
  P: ^TArrayOfByte;
begin
  P:= Items[Index];
  Dispose(P);
  Delete(Index);
end;

destructor TArrayOfByteList.Destroy;
begin
  while Count > 0 do DelItem(Count-1);
  inherited Destroy;
end;

function TArrayOfByteList.Selectionsort(Index: integer): TArrayOfByte;
  procedure Exchange(const I, J: integer);
  var
    T: byte;
  begin
    T:= Result.A[I];
    Result.A[I]:= Result.A[J];
    Result.A[J]:= T;
  end;
begin
  Result:= Item[Index];
  if Result.A[0] < Result.A[1] then Exchange(0, 1);
  if Result.A[0] < Result.A[2] then Exchange(0, 2);
  if Result.A[0] < Result.A[3] then Exchange(0, 3);
  if Result.A[1] < Result.A[2] then Exchange(1, 2);
  if Result.A[1] < Result.A[3] then Exchange(1, 3);
  if Result.A[2] < Result.A[3] then Exchange(2, 3);
end;

function TArrayOfByteList.Networksort(Index: integer): TArrayOfByte;
  procedure Exchange(const I, J: integer);
  var
    T: byte;
  begin
    T:= Result.A[I];
    Result.A[I]:= Result.A[J];
    Result.A[J]:= T;
  end;
begin
  Result:= Item[Index];
  if Result.A[0] < Result.A[1] then Exchange(0, 1);
  if Result.A[2] < Result.A[3] then Exchange(2, 3);
  if Result.A[0] < Result.A[2] then Exchange(0, 2);
  if Result.A[1] < Result.A[3] then Exchange(1, 3);
  if Result.A[1] < Result.A[2] then Exchange(1, 2);
end;

procedure TArrayOfByteList.SelectionsortASM(var A: TArrayOfByte); assembler;
asm
  //
end;

procedure TArrayOfByteList.SelectionsortASM2(var A: TArrayOfByte); assembler;
asm
  //
end;

procedure TArrayOfByteList.SelectionsortASM2Horst(var A: TArrayOfByte); assembler;
asm
  //
end;

procedure TArrayOfByteList.SelectionsortASM3Horst(var A: TArrayOfByte); assembler;
asm
  //
end;

{ TWaitTime }

procedure TWaitTime.Start;
begin
  FStartTime:= Now;
end;

procedure TWaitTime.Stop;
var
  Hour, Min, Sec, MSec: Word;
begin
  DecodeTime(Now - FStartTime, Hour, Min, Sec, MSec);
  FWaitTime:= MSec + Sec * 1000 + Min * 60000 + Hour * 3600000;
end;

{ TForm1 }

procedure TForm1.Button1Click(Sender: TObject);
var
  I: integer;
  A: TArrayOfByte;
begin
  WaitTime.Start;
  for I:= 0 to ArrayOfByteList.Count-1 do
    A:= ArrayOfByteList.Selectionsort(I);
  WaitTime.Stop;
  ShowMessage('Selectionsort: '+IntToStr(WaitTime.WaitTime)+' ms');
end;

procedure TForm1.Button2Click(Sender: TObject);
var
  I: integer;
  A: TArrayOfByte;
begin
  WaitTime.Start;
  for I:= 0 to ArrayOfByteList.Count-1 do
    A:= ArrayOfByteList.Networksort(I);
  WaitTime.Stop;
  ShowMessage('Networksort: '+IntToStr(WaitTime.WaitTime)+' ms');
end;

procedure TForm1.Button3Click(Sender: TObject);
var
  I: integer;
  A: TArrayOfByte;
begin
  WaitTime.Start;
  for I:= 0 to ArrayOfByteList.Count-1 do
  begin
    A:= ArrayOfByteList[I];
    ArrayOfByteList.SelectionsortASM(A);
  end;
  WaitTime.Stop;
  ShowMessage('SelectionsortASM: '+IntToStr(WaitTime.WaitTime)+' ms');
end;

procedure TForm1.Button4Click(Sender: TObject);
var
  I: integer;
  A: TArrayOfByte;
begin
  WaitTime.Start;
  for I:= 0 to ArrayOfByteList.Count-1 do
  begin
    A:= ArrayOfByteList[I];
    ArrayOfByteList.SelectionsortASM2(A);
  end;
  WaitTime.Stop;
  ShowMessage('SelectionsortASM2: '+IntToStr(WaitTime.WaitTime)+' ms');
end;

procedure TForm1.Button5Click(Sender: TObject);
var
  I: integer;
  A: TArrayOfByte;
begin
  WaitTime.Start;
  for I:= 0 to ArrayOfByteList.Count-1 do
  begin
    A:= ArrayOfByteList[I];
    ArrayOfByteList.SelectionsortASM2Horst(A);
  end;
  WaitTime.Stop;
  ShowMessage('SelectionsortASM2Horst: '+IntToStr(WaitTime.WaitTime)+' ms');
end;

procedure TForm1.Button6Click(Sender: TObject);
var
  I: integer;
  A: TArrayOfByte;
begin
  WaitTime.Start;
  for I:= 0 to ArrayOfByteList.Count-1 do
  begin
    A:= ArrayOfByteList[I];
    ArrayOfByteList.SelectionsortASM3Horst(A);
  end;
  WaitTime.Stop;
  ShowMessage('SelectionsortASM3Horst: '+IntToStr(WaitTime.WaitTime)+' ms');
end;

procedure TForm1.FormCreate(Sender: TObject);
var
  I, J: integer;
  A: TArrayOfByte;
begin
  Randomize;
  WaitTime:= TWaitTime.Create;
  ArrayOfByteList:= TArrayOfByteList.Create;
  for I:= 1 to MaxInt div 32 do
  begin
    for J:= 0 to 3 do
      A.A[J]:= Random(256);
    ArrayOfByteList.AddItem(A);
  end;
end;

procedure TForm1.FormDestroy(Sender: TObject);
begin
  ArrayOfByteList.Free;
  WaitTime.Free;
end;

end.