Schnittmenge von mehreren Mengen ermitteln

[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

[Furtbichler]

Hi Panthrax, hättest Du ein Problem damit, deine Testroutine hier zur Verfügung zu stellen?

[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.

[Namenloser]

Zitat von Furtbichler:

Zitat von NamenLozer:

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

Du musst das sportlich sehen.

Klar, für einen „Wettbewerb“ kann man das schon mal machen . Aber im Produktivsystem würde ich die Pascal-Variante trotzdem vorziehen.

[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
* in Millisekunden

             Messung  #19, Pascal  #39, Pascal  #45, Pascal  #35, Assembler
                   1      242          224          160              64
                   2      246          221          161              62
                   3      244          224          159              63
                   4      248          221          161              67
                   5      247          246          174              64
                   6      252          221          172              61
                   7      249          222          168              62
                   8      251          227          161              60
                   9      261          231          160              61
                  10      263          236          160              62
                  11      255          221          157              61

          Mittelwert      250,727      226,727      163,000          62,455
  Standardabweichung        6,665        8,026        5,639           1,968

Anmerkungen:

• Testsystem: Intel i7, Windows 7
• Den Mittelwert und die Standardabweichung füge ich mit Excel hinzu.
• Verglichene Implementierungen:
  #19 (Pascal, Furtbichler) ist der erste Vorschlag;
  #39 (Pascal, Furtbichler) ist eine korrigierte und verbesserte Variante von #19;
  #45 (Pascal, Panthrax) ist eine verbesserte Variante von #37;
  #35 (Assembler, Amateurprofi).

[Horst_]

Hallo,

ich habe mal das Programm geändert und einfach ein Testfeld mit Zahlen gleichen Abstandes gefüllt habe ( sehr großer Abstand) und anschließend in diesem diese Feld zufällige Werte um 1 oder mehr vergrößert habe.
Dies mehrfach hintereinander.
Versuch[i]= verändertere(Versuch[i-1])

Es war mir nicht geheuer, immer nur die gleiche Datei mit sich selbst zu vergleichen, da werden keine Daten bewegt.

Hier mal die Messungen mit 16 Feldern mit 1e7 = 10 Mio Werten.
Temp ist das Ausgangs und Intersectfeld
Einmal Intersect(Temp,versuch[i]) mit i von 0..15
und einmal rückwärts
Intersect(Temp,versuch[i]) mit i von 15..0
type
tData = int64;
Als Ergbenis:

Code:

   Messung
  #19, Pascal
   9999999   9375981   8790215   8240652   7725057   7242124   6788731   6363882
   5967006   5594037   5244659   4916458   4608947   4321049   4050708   3796820

   3796820   3796820   3796820   3796820   3796820   3796820   3796820   3796820
   3796820   3796820   3796820   3796820   3796820   3796820   3796820   3796820

Zeit in ms :     4606
  #39, Pascal
  10000000   9375981   8790215   8240652   7725057   7242124   6788731   6363882
   5967006   5594037   5244659   4916458   4608947   4321049   4050708   3796820

   3796820   3796820   3796820   3796820   3796820   3796820   3796820   3796820
   3796820   3796820   3796820   3796820   3796820   3796820   3796820   3796820

Zeit in ms :         3829
  #45, Pascal
  10000000   9375981   8790215   8240652   7725057   7242124   6788731   6363882
   5967006   5594037   5244658   4916456   4608944   4321045   4050703   3796814

   3796820   3796819   3796818   3796817   3796816   3796815   3796814   3796813
   3796812   3796811   3796810   3796809   3796808   3796807   3796806   3796805

Zeit in ms :         2971
  #35, Assembler
  10000000  10000000  10000000  10000000  10000000  10000000  10000000  10000000
  10000000  10000000  10000000  10000000  10000000  10000000  10000000  10000000

  10000000  10000000  10000000  10000000  10000000  10000000  10000000  10000000
  10000000  10000000  10000000  10000000  10000000  10000000  10000000  10000000

Zeit in ms :             993

Fertig.

Version #19 verzählt an der höchsten Stelle
Version #39 funktioniert
Version #45 verkleinert scheinbar das intersect um 1 zuviel ( aber nicht immer, besonders auffällig bei rueckwaerts.
Mit tdata = longint, war es richtig )
Version #35 funktioniert überhaupt nicht ( kann eigentlich nur bei tData= 32bit funktionieren, oder? Aber vielleicht übergibt freepascal die Register anders)

Version #45 War in der ursprünglichen Verson mit tdata = longint schneller als die Assembler Version 70 / 80 ms

Gruß Horst