Schnittmenge von mehreren Mengen ermitteln

[Laser]

Moin,

Zitat von jfheins:

Zitat von Laser:

Moin,

Zitat von jfheins:

Einfach jede Datei erstmal in den RAM laden.

Dann habe ich schon über 5.000.000 Festplattenzugriffe. Danach ist es dann alles egal, wie schnell man im RAM arbeitet.

Hmmmm, das sehe ich anders.

Die Frage ist sicherlich, wie man einen Festplattenzugriff definiert. Für mich ist sowohl "Ein Byte lesen" als auch "100000 Bytes lesen" ein Festplattenzugriff. Denn in jedem Fall fällt die Latenzzeit an (irgendwas so um die 10ms) egal wie viel man liest. (Die Zeit braucht der Lesekopf, um an die Stelle zu fahren wo die Daten sind.)
Sobald der Lesekopf einmal angefangen hat, zu lesen kann er das ziemlich schnell. So auf 100 MB/s sind da schon drin.

Falls du also jede 64-bit Zahl einzeln liest, bekommst du 100 Zahlen pro Sekunde. Liest du sequenziell alles ein bekommst du 13 Mio Zahlen pro Sekunde.

Caching kann da jetzt noch einiges reißen aber ich denke ich habe meinen Grundgedanken klar gemacht. Auf einer SSD sieht das natürlich anders aus, aber man sollte ja nicht davon ausgehen dass jeder ne SSD hat.

Falls es also um Datenmengen geht die problemlos in den RAM passen, kann es durchaus sinnvoll sein erst mal alles zu laden. Wenn du mir nicht glaubst, probiere es bitte mal aus

auch hmmmmm
Erst hatte ich den Verdacht, dass Plattenzugriffe einfach nur "wegdefiniert" werden.
Nach näherer Betrachtung scheint es aber richtig, zumindest die einzelnen Dateien komplett einzulesen.

Erst mal ein paar Annahmen für Lesezugriffe:
HDD: ca. 50 MB/s, 10 ms Zugriffszeit, max. 2 TB für das Programm, das wird nicht eng
SSD: ca. 300 MB/s, < 1 ms, keine Kapazität für dieses Programm
RAM: ca. 10.240 MB/s, Nanosekundenbereich, max. 20 GB für dieses Programm, RAM, Ramdisk oder Festplattenpuffer

Gehen wir mal davon aus, dass es ca. 1 Sekunde dauert, bis 5.000.000 Schlüssel aus einer Datei eingelesen wurden.
In dieser Zeit könnte man sich nur ca. 100 mal "Rumgehüpfe" à 10 ms beim erstmaligen Einlesen leisten. In meinem Beispiel benötigt man 11.500 mal. Das wird vermutlich selbst dann nicht schneller als das Einlesen, wenn man davon ausgeht, dass ein Großteil der Anfragen aus Festplattenpuffern des Betriebssystems bedient werden können.

Ein "Rumgehüpfe" im RAM könnte auch ein Schuss nach hinten sein. Das überlege ich mir noch.
Eine gute Idee finde ich, Dateien im Thread zu lesen. Mehr als 1 zur Zeit schient mir auch nicht sinnvoll.
Memory Mapped Files scheint mir auch eher ungünstig.
Zu http://en.wikipedia.org/wiki/Hash_join muss ich mal schauen, ob ich auch einen für mich verständlichen deutschen Artikel finde.

@Furtbichler
Wie hast Du bei Deinem Test sichergestellt, dass Du die Dateien nicht aus dem Puffer des Betriebssystems liest?

[Furtbichler]

Zitat von Laser:

@Furtbichler: Wie hast Du bei Deinem Test sichergestellt, dass Du die Dateien nicht aus dem Puffer des Betriebssystems liest?

Gar nicht. Aber andere Verfahren lesen ja auch aus dem Cache, sodaß es eigentlich egal ist.

Ich habe zudem eine Abbruchbedingung: Wenn die Schnittmenge leer ist, werden keine weiteren Dateien mehr angefasst, wozu auch. Das verfälscht natürlich das Ergebnis.

Also: Durchscannen aller 5 Mio Werte einer Datei geht ohne Optimierung im Worstcase in 140ms, wenn nämlich alle Dateien die gleichen 5 Mio Zahlen enthalten.

Zitat von Laser:

Memory Mapped Files scheint mir auch eher ungünstig.

Beim Einlesen habe ich eben mit Mapped Files getestet: Das scheint doppelt so schnell zu sein, wie ein TMemorystream.LoadFromFile, zumindest, wenn die Daten im RAM vorliegen.

Das Mapped File habe ich von hier: http://landman-code.blogspot.com/200...ce-i-last.html

Zitat von Horst_:

im Prinzip bleibt es bei Patti's Vorschlag aus PostNr 2: Aber in 500 ms aus 480 Mbyte die Schnittmenge zu bilden heißt nur, dass alle Dateien im Cache waren.

Korrekt. und nochmal korrekt.

Das, zusammen mit memory mapped files, dürfte die ideale Lösung sein bzw. die, gegen die eine Alternative bestehen müsste.

[Amateurprofi]

Hallo Furtbichler,
mich hat das auch interessiert und ich habe das mit binärer Suche versucht – war aber, die Performance betreffend, ein Flop.
Also hab ich mir mal deine Lösung angeschaut.
Sehr interessanter Ansatz, leider aber fehlerhaft.

for I := 0 to High(data) - 1 do begin Das " – 1 " gehört da m.E. nicht hin. Es verursacht, dass das letzte Element von data nicht in Intersect übernommen wrid.
Ich nehme an da stand ursprünglich Length(data) – 1


while (j < n) and (Intersect[j] < data[i]) do inc(j); Wenn das letzte Element in data größer ist als das letzte Element in Intersect dann wird j=n=Length(Intersect) und bei
if data[i] = Intersect[j] then begin wird auf Intersect[Length(Intersect)] zugegriffen, was einen Laufzeitfehler verursachen müßte.


Du schriebst 140 ms bei 12 Files je 5 Mio Werten, wobei die Files bereits im RAM liegen und alle Files die gleichen Daten enthalten.

Ich hab mal deine Prozedur auf meinem Rechner laufen lassen.
Das "Alle Files identisch und bereits im RAM" habe ich so realisiert, dass das Array "data", das bei dir lokal definiert ist, als Parameter mitgegeben wird.

Bei mir dauert das ganze bei unten stehendem Ablauf 300 ms.
Hab ich da vielleicht irgendwas falsch verstanden? Oder hab ich nur 'nen lahmen Rechner? Auf was für einer Maschine erreichst du 140 ms?

Delphi-Quellcode:

procedure IntersectFileWithHashmap(var Intersect,Data:TSampleArray);
var
   newIntersect{, data}: TSampleArray;
   n, i, j, k: Integer;
begin
   n := Length(Intersect);
   if n = 0 then exit;
   //ReadSamples(aFilename, data);
   j := 0;
   k := 0;
   SetLength(newIntersect, n);
   for I := 0 to High(data) {- 1} do begin
      while (j < n) and (Intersect[j] < data[i]) do inc(j);
      if data[i] = Intersect[j] then begin
         newIntersect[k] := data[i];
         inc(k);
      end;
   end;
   setLength(newIntersect, k);
   Intersect := newIntersect;
end;

procedure TMain.Button1Click(Sender: TObject);
const count=5000000;
var intersect,data:TSampleArray; i:integer; t:cardinal;
begin
   SetLength(data,count);
   for i:=0 to High(data) do data[i]:=i+1;
   intersect:=Copy(data);
   t:=GetTickCount;
   for i:=1 to 11 do IntersectFileWithHashmap(intersect,data);
   t:=GetTickCount-t;
   ShowMessage('Anzahl='+IntToStr(Length(intersect))+#13+
               'Zeit='+IntToStr(t)+' ms');
end;

Du wolltest gern bessere Lösungen sehen.

Ich habe da einfach mal deine Prozedur genommen und an ein paar Stellen etwas entfernt.

Du erstellst ein Array newIntersect, schreibst die gefundenen Werte hinein und stellst am Schluss newIntersect in Intersect.
Das ist überflüssig.
Anstatt kann man die gefundenen Werte direkt in das Array Intersect stellen.

Mit diesen Änderungen braucht das Ganze (auf meinem Rechner) nur noch 250 ms, also eine Verbesserung um ca 15 %.
Auf deinem Rechner müsste das dann 140*250/300 = 117 ms brauchen.

Delphi-Quellcode:

procedure xIntersectFileWithHashmap(var Intersect,Data: TSampleArray);
var n, i, j, k: Integer;
begin
   n := Length(Intersect);
   if n = 0 then exit;
   j := 0;
   k := 0;
   for I := 0 to High(data) do begin
     while (j < n) and (Intersect[j] < data[i]) do inc(j);
     if (j < n ) and (data[i] = Intersect[j]) then begin
       Intersect[k] := data[i];
       inc(k);
     end;
   end;
   setLength(Intersect, k);
end;

procedure TMain.Button2Click(Sender: TObject);
const count=5000000;
var intersect,data:TSampleArray; i:integer; t:cardinal;
begin
   SetLength(data,count);
   for i:=0 to High(data) do data[i]:=i+1;
   intersect:=Copy(data);
   t:=GetTickCount;
   for i:=1 to 11 do xIntersectFileWithHashmap(intersect,data);
   t:=GetTickCount-t;
   ShowMessage('Anzahl='+IntToStr(Length(intersect))+#13+
               'Zeit='+IntToStr(t)+' ms');
end;

Aber damit war ich auch nicht zufrieden, denn ich wollte ja auch auf meiner lahmen Krücke deine 140 ms toppen.

Die unten stehende Version braucht bei identischen Daten (auf meinem Rechner) nur noch 110 ms, was, auf deinen Rechner umgerechnet 140*110/300 = 51 ms heißen sollte.
Verglichen mit den 300 ms, die deine Prozedur auf meinem Rechner brauchte, ist das eine Verbesserung um ca. 65 %.

Jedoch möchte ich mich nicht mit fremden (deinen) Federn schmücken.
Auch meine Asm-Version baut im Prinzip auf deiner Lösung auf - und die ist einfach nur gut, auch wenn da ein paar Flüchtigkeitsfehler drin waren.
Jetzt hoffe ich nur, daß ich bei meiner Asm-Version nichts übersehen habe......

Delphi-Quellcode:

FUNCTION IntersectData(var Intersect,Data:TSampleArray; length:integer):integer;
asm
// IN  : EAX=@Intersect, EDX=@Data, ECX=Anzahl der Elemente der bisherigen Schnittmenge
// Out : Neue Anzahl der Elemente der Schnittmenge
               pushad  // Temp:=ESP; Push EAX,ECX,EDX,EBX,Temp,EBP,ESI,EDI
               mov   ebp,ecx          // n := Length(intersect)
               test  ebp,ebp
               je    @ReturnZero      // Schnittmenge ist leer
               mov   esi,[edx]        // @data[0]
               test  esi,esi
               je    @ReturnZero      // Data ist leer
               mov   edi,[eax]        // @Intersect[0]
               test  edi,edi          // nur zur Sicherheit
               je    @ReturnZero      // Intersect leer
               xor   ecx,ecx           // j := 0
               xor   edx,edx           // k := 0;
               xor   ebx,ebx           // for i := 0
               jmp   @CheckFor

@WhileLoop:    add   ecx,1             // inc(j)
               cmp   ecx,ebp           // While (j < n)
               jae   @SetRes
@ForLoop:      cmp   [edi+ecx*4],eax   // and Intersect[j] < data[i]
               jb    @WhileLoop        // do
               jne   @NextFor
               mov   [edi+edx*4],eax   // Intersect[k] := data[i];
@NoStore:      add   edx,1             // inc(k);
@NextFor:      add   ebx,1             // next i
@CheckFor:     cmp   ebx,[esi-4]       // i > High(data)
               jae   @SetRes           // ja, fertig
               mov   eax,[esi+ebx*4]   // data[i]
               jmp   @ForLoop          // Prüfung j<n nicht erforderlich

@ReturnZero:   xor   edx,edx           // k := 0
@SetRes:       mov   [esp+28],edx      // popad stellt [esp-28] in EAX
               popad
end;

procedure TMain.Button3Click(Sender: TObject);
const count=5000000;
var intersect,data:TSampleArray; i,len:integer; t:cardinal;
begin
   SetLength(data,count);
   for i:=0 to High(data) do data[i]:=i+1;
   intersect:=Copy(data);
   len:=Length(intersect);
   t:=GetTickCount;
   for i:=1 to 11 do len:=IntersectData(intersect,data,len);
   SetLength(intersect,len);
   t:=GetTickCount-t;
   ShowMessage('Anzahl='+IntToStr(Length(intersect))+#13+
               'Zeit='+IntToStr(t)+' ms');
end;

[Namenloser]

Also das in ASM umzusetzen halte ich nicht für sinnvoll. Da geht nur die Wartbarkeit flöten, und die Performance wird sich dadurch kein bisschen okay, kaum verbessern, da die Festplatte der Flaschenhals ist, nicht die CPU.

[Amateurprofi]

Zitat von NamenLozer:

Also das in ASM umzusetzen halte ich nicht für sinnvoll. Da geht nur die Wartbarkeit flöten, und die Performance wird sich dadurch kein bisschen okay, kaum verbessern, da die Festplatte der Flaschenhals ist, nicht die CPU.

Hallo NamenLozer,
ich sehe das ganz anders.
Auch wenn mein Flug nach Neuseeland 36 Stunden dauert, laufe ich nicht zu Fuß zum Flughafen sondern versuche eine schnellere Lösung zu finden. Zudem ging es hier um den speziellen Fall, daß sich die Daten bereits im RAM befinden. Den Flaschenhals Festplatte gab es hier also nicht.
Auch Wartbarkeit ist hier kein Problem, denn es handelt sich um einen kurzen und überschaubaren Code. Der Teil, der die Arbeit macht, umfaßt gerade mal 13 Asm-Anweisungen.

[Furtbichler]

Hi Leute,

Endlich geht es mal los. Ich lese gerade 'Clean Coder' von Robert C. Martin, und da geht es darum, wie sich ein 'professioneller Programmierer' verhalten soll. U.a. empfiehlt er 'Programmierwettbewerbe' im Team zu veranstalten, z.B. wer schreibt den schnellsten (oder elegantesten, kompaktesten etc.) Code. Einerseits geht es um Verfahren, andererseits auch um Implementierung. Und wenn man gerade kein Team bei der Hand hat, soll man immer mal wieder aus Spaß in seiner Freizeit seinen Stil vervollkommnen. Dazu ist so ein Forum echt gut.

Zum, Thema;
Bezüglich der Performance: Nun ja. Ich teste mit 5 Mio Werten, Du mit 10 Mio.

@Amateurprofi: Danke für das Review. Die Fehler, die ich da gemacht habe, sind mir teilweise hinterher auch aufgefallen. (aber die -1 nicht, weil ich -na ja- zu blöd bin ). Genau das ist der Sinn von Codereview. Die Optimierungen sind natürlich sehr gut bemerkt.

In einer Produktivumgebung würde ich den Code vermutlich sauber ausprogrammieren. Wenn es um jede 10tel Sekunde geht, dagegen Assembler nehmen, aber den Code im Klartext (d.h.) Delphi oder Pseudocode darüber schreiben.

Wir sollten jedoch nicht nur den worst case betrachten, sondern in etwa mit den Zahlen hantieren, die in der Produktivumgebung zu erwarten sind. Dann wird die zu untersuchende Schnittmenge sehr schnell klein werden und es wäre noch eine Optimierung drin: In dem Augenblick, wo data[i] größer als das letzte Element von Intersect ist, kann die For-Schleife beendet werden.

Desweiteren ist der Name der Routine unglücklich: "xIntersectFileWithHashmap". Da ist erstens keine Hashmap und zweitens keine Datei. Entweder wird das eine Methode des TSampleArray oder man gibt dem Kind einen anständigen Namen, z.B. so:

Delphi-Quellcode:

procedure IntersectSampleArray (var Intersect,Data: TSampleArray);
var n, i, j, k: Integer;
begin
  n := Length(Intersect);
  if n = 0 then exit;
  j := 0;
  k := 0;
  for I := 0 to High(data) do begin
    while (j < n) and (Intersect[j] < data[i]) do inc(j);
    if j = n then  // Intersect-Array ist durch, alle weiteren Daten in data können ignoriert werden
      break
    else if data[i] = Intersect[j] then begin
      Intersect[k] := data[i];
      inc(k);
    end
  end;
  setLength(Intersect, k);
end;

Weiteres Optimierungspotential wäre:
1. 'SetLength' am Ende entfernen und stattdessen die Arraygröße im TSampleArray selbst mitzuspeichern.
2. In der inneren While-Schleife kann man auf das (j<n) verzichten, wenn das letzte Element von Intersect immer MaxInt64 ist und dieses Element selbst nicht in dem Wertebereich vorkommt.
3. Zumindest bei Strings ist die Verwendung von inkrementierenden Zeigern (PChar) schneller als der Array-Zugriff. Hier könnte man noch etwas herausholen. Dann ist das in etwa so schnell wie Assembler. Aber auch so unübersichtlich.

So, muss zur Arbeit

[Panthrax]

Code:

11 Messungen:
function Intersect(var Left: TSampleArray; const Right: TSampleArray);
* mit Length(Left) = Length(Right) = N = 10000000 // 10 Mio.
* mit denselben Daten für jede Routine
* mit zufällig generierten Daten für jede Messung

           Messung  #19, Pascal  #39, Pascal  #37, Pascal #35, Assembler
                 1      260          231          221             65
                 2      259          238          209             65
                 3      264          238          205             68
                 4      267          233          204             67
                 5      264          232          225             72
                 6      266          239          221             64
                 7      262          253          217             66
                 8      263          243          210             66
                 9      280          232          210             66
                10      265          230          212             65
                11      264          231          209             65

        Mittelwert      264,909      236,364      213,000         66,273
Standardabweichung        5,540        6,932        6,957          2,195

[Namenloser]

Zitat von Amateurprofi:

Zitat von NamenLozer:

Also das in ASM umzusetzen halte ich nicht für sinnvoll. Da geht nur die Wartbarkeit flöten, und die Performance wird sich dadurch kein bisschen okay, kaum verbessern, da die Festplatte der Flaschenhals ist, nicht die CPU.

Hallo NamenLozer,
ich sehe das ganz anders.
Auch wenn mein Flug nach Neuseeland 36 Stunden dauert, laufe ich nicht zu Fuß zum Flughafen sondern versuche eine schnellere Lösung zu finden. Zudem ging es hier um den speziellen Fall, daß sich die Daten bereits im RAM befinden. Den Flaschenhals Festplatte gab es hier also nicht.

Ja, im Test gab es den nicht, da man sonst die Algorithmen unmöglich vergleichen könnte. In der Praxis wird es den Flaschenhals Festplatte aber dennoch geben. Ich will deinen Code auf keinen Fall schlechtreden, der eigentliche Vergleiche-Teil ist schon erheblich schneller . Die Frage ist nur, ob es sich lohnt, hier 200ms zu sparen, wenn das Laden an sich schon mehrere Sekunden dauert.

[Furtbichler]

Zitat von NamenLozer:

Die Frage ist nur, ob es sich lohnt...

Du musst das sportlich sehen.

[Laser]

Moin,

die Dateien liegen auf der Platte. Sie sind vor dem letzten Reboot entstanden. Die Wahrscheinlichkeit, dass sie schon im RAM sind, liegt in der Größenordnung 1:100.000.

Man kann sich das so vorstellen, dass für jedes Wort in einem Buch mit mehreren Millionen Seiten eine Indexdatei vorliegt. Es werden mehrere Schlagwörter benannt und die Schnittmenge enthält die Seiten, auf denen alle Wörter vorkommen.

KISS steht an dieser Stelle nicht im Vordergrund. Es geht um einen zentralen Teil, der die Performance bestimmt.