Schnittmenge von mehreren Mengen ermitteln

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