Einzelnen Beitrag anzeigen

Amateurprofi

Registriert seit: 17. Nov 2005
Ort: Hamburg
963 Beiträge
 
Delphi XE2 Professional
 
#59

AW: Schnittmenge von mehreren Mengen ermitteln

  Alt 19. Mär 2012, 20:42
Ich habe meine Asm-Version aus #35 noch einmal überarbeitet.
Die nachstehende Funktion arbeitet mit 32 und 64 Bit Daten und ist (auf meinem Rechner) deutlich schneller, als die aus #35.
Mit den von Laser in #53 genannten Testdaten liefert sie korrekte Ergebnisse.

Die Umstellung von 32 auf 64 Bit habe ich so gelöst :

Delphi-Quellcode:
{$DEFINE INT64DATA}
type
   TElement={$IFDEF INT64DATA} int64 {$ELSE} integer {$ENDIF} ;
   TSampleArray=Array of TElement;
   TFiles=Array of TSampleArray;
var
   files:TFiles;
Wenn files die Daten enthält, dann ist der Ablauf so :

Delphi-Quellcode:
var len:integer;
begin
   len:=Length(files[0]);
   for i:=1 to High(files) do
      len:=GetIntersect_5(files[0], files[i],len);
   SetLength(files[0],len);
end;
Danach ist files[0] der Intersect.

Delphi-Quellcode:
FUNCTION GetIntersect_5(var Intersect,Data:TSampleArray; Len:integer):integer;
const f={$IFDEF INT64DATA} 8 {$ELSE} 4 {$ENDIF};
asm
// IN : EAX=@Intersect, EDX=@Data, ECX=Anzahl der Elemente der bisherigen Schnittmenge
// Out : EAX=Neue Anzahl der Elemente der Schnittmenge
               // Alle Register retten
               pushad // Temp:=ESP; Push EAX,ECX,EDX,EBX,Temp,EBP,ESI,EDI
               // Prüfen ob Data leer
               mov esi,[edx] // @Data[0]
               test esi,esi
               je @ReturnZero // Data ist leer
               mov edi,[eax] // @Intersect[0]
               test edi,edi
               je @ReturnZero // Intersect leer
               // Zeiger in Intersect und Data hinter jeweils letzten Eintrag
               // stellen und Indizes auf jeweils ersten Eintrag ausrichten
               lea edi,[edi+ecx*f] // @Intersect[Len]
               neg ecx // i [edi+ecx*4] = Intersect[0]
               je @ReturnZero // 0 Elemente in Intersect
               mov ebp,ecx // k [edi+ebp*4] = Intersect[0]
               mov ebx,[esi-4] // Length(data)
               lea esi,[esi+ebx*f] // @Data[Length(data)]
               neg ebx // j [esi+edx*4] = Data[0]
               jmp @Entry

@Store: mov [edi+ebp*f],eax // In neuem Intersect speichern
               {$IFDEF INT64DATA}
               mov [edi+ebp*f+4],edx // Hi wenn int64
               {$ENDIF};
               add ebp,1 // Neue Anzahl in Intersect
               add ecx,1 // Nächster Intersect-Index
               je @SetRes // Fertig
               mov eax,[edi+ecx*f] // Zahl aus Intersect laden
               {$IFDEF INT64DATA}
               mov edx,[edi+ecx*f+4] // Hi wenn int64
               {$ENDIF};
@NextData: add ebx,1 // Nächster Data-Index
               je @SetRes // Fertig
@Compare: {$IFDEF INT64DATA}
               cmp edx,[esi+ebx*f+4] // Vergleich Intersect, Data (Hi)
               ja @NextData // Intersect>Data. Nur Data-Index erhöhen
               jb @NextI
               {$ENDIF};
               cmp eax,[esi+ebx*f] // Vergleich Intersect, Data
               je @Store // Gleich. Speichern und beide Indizes erhöhen
               ja @NextData // Intersect>Data. Nur Data-Index erhöhen
@NextI: add ecx,1 // Nächster Intersect-Index
               je @SetRes // Fertig
@Entry: mov eax,[edi+ecx*f] // Zahl aus Intersect laden
               {$IFDEF INT64DATA}
               mov edx,[edi+ecx*f+4] // Hi wenn int64
               {$ENDIF};
               jmp @Compare

@SetRes: add ebp,[esp+24] // Alte Länge addieren (ebp ist <= 0)
               jmp @StoreRes

@ReturnZero: xor ebp,ebp
@StoreRes: mov [esp+28],ebp // von da wird sie in EAX gepopt
               popad
end;
Dass die Performance weitestgehend durch das Einlesen der Daten von der Platte bestimmt wird ist auch mir klar.
Mir geht es hier nur um den Wettbewerb der von Furtbichler ins Leben gerufen wird, mit der Voraussetzung "Daten komplett im RAM".
Gruß, Klaus
Die Titanic wurde von Profis gebaut,
die Arche Noah von einem Amateur.
... Und dieser Beitrag vom Amateurprofi....
  Mit Zitat antworten Zitat