Schnittmenge von mehreren Mengen ermitteln

[Furtbichler]

Zitat von Laser:

Zitat von Furtbichler:

Meinst Du "komplett"? Ja, wie willst Du sonst die Schnittmenge ermitteln?

Jede Binärsuche ist vom Aufwand O(log n), jede Suche in einer Hashmap O(1).

Ich will möglichst nicht alles lesen. Für die Hasmap mit O(1) brauche ich als Voraussetzung O(n) Lesezugriffe auf die Platte.

Du hast die O(*)-Notation nicht verstanden.

Das befüllen der Hashmap dauert wirklich etwas. Mit Binärsuche auf Dateien ist das auch Quark, da das Einlesen einer Datei mit 5 Mio Werten nur wenige ms dauert.

Nun habe ich einen Ansatz, der 12 Dateien mit jeweils 5 Mio Einträgen pro Datei (mit aufsteigenden Zufallswerten) in insgesammt 500ms erledigt.

Hier mal die Routine, die die Schnittmenge mit einer Datei ausrechnet, die Werte der ersten Datei landen direkt in Intersection, für alle weiteren Dateien wird die u.a. Routine aufgerufen.

Delphi-Quellcode:

procedure IntersectFileWithHashmap(aFilename: string; var Intersect: 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;