Schnittmenge von mehreren Mengen ermitteln

[BUG]

Bei Sprüngen würde ich mit Memory Mapped Files arbeiten. Damit überlässt du das Lesen aus der Datei dem Betriebssystem und das ist ein Bereich, in den die Betriebssystemler ewig rumoptimieren. Davon kannst du nur profitieren.
Deshalb könnte das auch einen Geschwindigkeitsschub geben, wenn du einen Ansatz ohne Sprünge wählst.

Ich persönlich würde allgemein einen der Ansätze wählen, die die Dateien gleichzeitig fortlaufend durchgehen.

Aber mit den fortlaufenden Zahlen könntest du den Aufwand vermutlich auf die Größe der kleinsten Datei drücken, mehr Informationen (oder vielleicht ein Beispiel) wären schön.

[Namenloser]

Also wenn ich es richtig verstehe ist das, was du willst, ein „Inner-Join“, um es mit SQL-Vokabular auszudrücken. Man könnte also mal recherchieren, welche Algorithmen ausgereifte Datenbanksysteme dafür benutzen. Auf die Schnelle habe ich folgenden gefunden: Hash Join. Klingt nach kurzem Überfliegen für mich 1:1 wie der Vorschlag von Furtbichler (hab den allerdings auch nur überflogen). Wichtig ist, dass man von der Datei mit den wenigsten Datensätzen ausgeht.

Btw, Herumspringen und mit MMFs arbeiten, ist irgendwie witzlos - denn was macht das MMF? Richtig, es liest die Datei in größeren Blöcken ein und kopiert sie in den RAM – und somit liest du im Endeffekt auch wieder die ganze Datei ein, nur hast du dabei noch zusätzlichen Verwaltungs-Overhead. MMFs sind ja eigentlich eher eine Notlösung dafür, wenn man in großen Daten herumspringen muss. Aber wenn man schon die Möglichkeit hat, die Datei in einem Rutsch einzulesen, spricht aus meiner Sicht nichts für ein MMF. MMFs können noch so schnell sein, schneller als das Einlesen in einem Rutsch können sie zumindest bei herkömmlichen Festplatten nicht sein.

Allgemein würde ich auch nicht zu viel Hirnschmalz auf dieses Problem verwenden. Ich denke, mit Hashmaps bist du hier erst mal ganz gut bedient. Wenn das wider Erwarten nicht der Fall sein sollte, kannst du dir ja immer noch was besseres überlegen.

[BUG]

Ich weiß nicht, was die Hashtable in diesem Fall für Verbesserungen bringen soll. Für die build-Phase muss die kleinste Datei einmal ganz gescannt werden, für die probe-Phase die anderen.

Die Hashtable würde nur dann Sinn machen, wenn die Datensätze nicht sortiert wären.


PS:
Ich würde noch gerne mehr über die fortlaufenden Nummern erfahren.
Meint "fortlaufend" Zahlen in der Form: n, n+1, n+2, n+3, ..., n+m?

[patti]

Zitat von BUG:

Ich weiß nicht, was die Hashtable in diesem Fall für Verbesserungen bringen soll.

Das ist genau das, was ich auch nicht ganz nachvollziehen kann. Warum sollte das schneller als z.B. mein Ansatz sein?

[Furtbichler]

Zitat von BUG:

Ich weiß nicht, was die Hashtable in diesem Fall für Verbesserungen bringen soll.

Suchen geht sehr schnell, der Aufbau ist aber grottenlahm. Deshalb habe ich meinen Vorschlag revidiert und bereits eine Lösung gepostet, die 12 Dateien mit jeweils 5 Mio Zahlen in 500ms einliest und die Schnittmenge bildet.

Kann es jemand schneller? Bei Interesse an einem 'Wettbewerb' poste ich gerne mein Testprogramm.

Ich würde allen vorschlagen, weniger über die Theorie zu sinieren, als einfach ein Proof-Of-Concept zu präsentieren.

Ich weiss nur, das das Einlesen einer Zahl genauso lange dauert, wie 2000 (Systempage = 8k, 4Byte=eine Zahl) Also wieso sollte ich einzelne Zahlen einlesen und wie soll das gehen? Ich will ja nicht eine Zahl finden, sondern die Schnittmenge über alle Zahlen. Also muss ich auch alle einlesen (nun ja, bis MAX(Bisherige-Schnittmenge)).

Ich behaupte mal, das bis -sagen wir- 500MB pro Datei ist das einmalige (schlürf) Einlesen aller Werte bedeutend performanter als Gehirnakrobatik.

Aber bitte sehr: 500ms sind zu schlagen

[Bummi]

@Furtbichler
Ich finde gerade weder Zeit noch Muße etwas derartiges zu testen.
Ich würde aber da die Daten bereits sortiert sind, vermuten dass Dein Ansatz, den ich bis dahin teile durch ersetzen des Blocks bei " while (j < n) and (Intersect[j] < data[i]) do inc(j);" durch eine BinarySearchfunktion nochmals deutlich am Performance zulegen sollte.

[Namenloser]

Zitat von Furtbichler:

Zitat von BUG:

Ich weiß nicht, was die Hashtable in diesem Fall für Verbesserungen bringen soll.

Suchen geht sehr schnell, der Aufbau ist aber grottenlahm.

Geht. Meine (String-)Hashmap addet eine Million Einträge in ca. einer halben Sekunde. Gut, deine 500ms kann man damit natürlich nicht mehr toppen, aber die Frage ist ja, wie schnell das Programm wirklich sein muss . Kommt es auf ein paar Sekunden überhaupt an?

Wie auch immer, ich habe noch mal kurz etwas drüber nachgedacht und jetzt eine deutlich einfachere Lösung – manchmal sieht man den Wald vor lauter Bäumen nicht. Kann sein, dass Patti in seinem ersten Post das gleiche meinte, allerdings bin ich mir bei seinem Pseudocode nicht ganz sicher

Mein Algorithmus geht so:

Code:

Zunächst haben wir für jede Datei quasi einen "Stream" mit einem Index. 
Der Index ist zu Beginn für alle Streams 0, also am Anfang der Datei. 
Jeder Stream hat eine Methode um das aktuelle Element zurückliefern, und eine Methode um einen Datensatz weiterzurücken.

Solange kein Stream das Dateiende erreicht hat:
  Bestimme PivotElement = höchstes (größter Wert) der aktuellen Elemente der Streams
  Für jeden Stream:
    Wenn das aktuelle Element des Streams < PivotElement:
      Aktuellen Stream eins weiterrücken lassen
  Wenn alle Elemente gleich sind:
    Element ausgeben
    Streams eins weiterrücken lassen (reicht an sich auch, einfach irgendeinen weiterrücken zu lassen, der Rest zieht automatisch nach)

Ich habe es nur an drei präparierten kleinen Testdateien ausprobiert, aber danach scheint es zu funktionieren. Hoffentlich ist kein Denkfehler drin (um diese Uhrzeit und bei 3 Stunden Schlaf kann viel passieren). Furtbichler, veröffentliche doch mal dein Programm zur Generierung der Testdaten. Ich würde mein Programm gerne mal damit testen (auch auf Geschwindigkeit, obwohl ich es jetzt nicht sonderlich optimiert habe).

[edit]
Alternativ kann man natürlich auch immer die Schnittmenge aus zwei Listen bilden, wobei bei den späteren Durchläufen eine der Listen selbst wieder je eine Schnittmenge ist. Das entspricht wohl Furtbichlers Ansatz. Dieses Verfahren ist im Best-Case schneller, da man bei einer leeren Zwischen-Schnittmenge gleich abbrechen kann, hat aber den Nachteil, dass es nicht In-Place arbeitet.

Man könnte den Ansatz auch parallelisieren und immer die Schnittmengen zwischen mehreren Listenpaare gleichzeitig bilden, und dann das gleiche wieder mit den sich daraus ergebenden Listen usw.... allerdings wächst dabei natürlich der Speicherbedarf noch weiter an.

Zusätzlich wäre ein Hybridansatz denkbar, dass man z.B. wenn nur (noch) sehr wenig Elemente in einer Liste (bzw. Zwischen-Schnittmenge) sind, die Strategie wechselt, und eben doch eine binäre Suche durchführt, da es ineffizient wäre, 5 Millionen Datensätze einzulesen, nur um zu prüfen, ob ein oder zwei Datensätze existieren.
[/edit]

[Horst_]

Hallo,

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.

Gruß Horst

[Panthrax]

Zitat von Furtbichler:

Ich würde allen vorschlagen, weniger über die Theorie zu sinieren, als einfach ein Proof-Of-Concept zu präsentieren.

+1

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  #37, Pascal  #35, Assembler
                    1      254          221              68
                    2      276          218              68
                    3      256          220              62
                    4      250          226              65
                    5      266          214              64
                    6      258          201              62
                    7      258          234              64
                    8      248          222              64
                    9      262          225              63
                   10      253          226              66
                   11      250          225              63

           Mittelwert      257,364      221,091          64,455
   Standardabweichung        8,201        8,432           2,115

[Laser]

Moin,

Zitat von BUG:

Aber mit den fortlaufenden Zahlen könntest du den Aufwand vermutlich auf die Größe der kleinsten Datei drücken, mehr Informationen (oder vielleicht ein Beispiel) wären schön.

Zitat von BUG:

Ich würde noch gerne mehr über die fortlaufenden Nummern erfahren.
Meint "fortlaufend" Zahlen in der Form: n, n+1, n+2, n+3, ..., n+m?

der 64-Bit Schlüssel ist eindeutig. Er besteht aus einem 32 Bit-Zeitstempel im oberen Teil und einer 32-Bit laufenden Nr. im unteren Teil.

In den Dateien n1...n12 kommt der Schlüssel jeweils 0 bis 1 mal vor. In den Dateien sind die Schlüssel aufsteigend sortiert.

Fortlaufend wäre also nur der untere 32-Bit Teil. Es kann aber Lücken zwischen 2 Schlüsseln geben. Es sind zwar alle Schlüssel lückenlos vergeben, aber es sind nicht unbedingt alle in den Dateien n1..n12 enthalten.