Schnittmenge von mehreren Mengen ermitteln

[Horst_]

Hallo,

@Amateruprofi,

kann es sein, dass die Assemblerversion in http://www.delphipraxis.net/1156992-post45.html bei gleichen Feldern ein Feld zu wenig zählt.

@panthrax
Ich habe habe Deine Version #45 zu #51 mit while-Schleifen umgebaut, die zählt scheinbar richtig.
Anbei ein Testprogramm.
Bei -1 wird Testfeld gegen Testfeld getestet und die Schnittmenge sollte die gleiche Länge besitzen, was Pascal #19 und Assembler nicht tuen.
Bei 0 werden 12 Felder die jeweile eine Modifikation vom Testfeld sind miteinander "geschnitten"
Bei 1 werden 12 Felder die jeweile eine Modifikation vom VorgängerFeld sind miteinander "geschnitten"
Die Ausgabe in µsec bei meinem Rechner, aber es geht ja nur um relative Beziehung als Assembler ist ~doppelt so schnell wie Pascal #19.

Code:

Pascal #19:Pascal #39:Pascal #39p:Pascal #45:Pascal #51:Assem  #35:
-1      -1:    470313:     388363:    475693:    371294:        -1:
 0  593633:    492619:     441995:    456582:    420622:    267954:
 1  638382:    521710:     459289:    462909:    451294:    296262:
 0  594878:    493216:     445630:    456969:    425607:    240649:
 1  638515:    520117:     461448:    457467:    447657:    302612:
 0  594142:    494672:     442169:    460931:    424432:    241258:
 1  641827:    519991:     459252:        -1:    449344:    298184:
 0  594625:    492036:     441968:        -1:    421176:    241215:
 1  640879:    519695:     459175:    462514:    452662:    296423:
 0  596518:    492056:     445751:    456175:    426792:    238062:
 1  636715:    519495:     458919:        -1:    452807:    301079:
 0  597456:    494035:     442330:    456586:    420898:    236698:
 1  643358:    520896:     462224:    458345:    449333:    294667:
Fertig.

Gruß Horst

[Amateurprofi]

Zitat von Horst_:

Hallo,

@Amateruprofi,

kann es sein, dass die Assemblerversion in http://www.delphipraxis.net/1156992-post45.html bei gleichen Feldern ein Feld zu wenig zählt.

Gruß Horst

Eigentlich kann das gar nicht angehen….
Aber vom Brand von Hamburg hatten auch alle gedacht, er könne nicht angehen.
Und dann ist er doch angegangen – und wie!
Das war am 5. Mai 1842, und die haben damals ziemlich dumm geguckt.

So wie ich eben!

Die Funktion ist für Arrays ausgelegt, die keine Zahlen mehrfach enthalten und aufsteigend sortiert sind. Eine weitere Einschränkung ist, dass die als Intersect bezeichnete Menge nicht mehr Elemente enthält, als die als Data bezeichnete.

Wenn wir 2 Arrays haben mit den Zahlen
1 4 4 4 4 7 und
4 4 4
Wie sollte dann die Schnittmenge aussehen?
4 4 4 (weil das die ursprüngliche Anzahl der 4en in der kleineren Menge ist)
oder
4 4 4 4 (weil ja auch die vierte 4 der größeren Menge in der kleineren gefunden wird)
oder
4 4 4 4 4 4 4 4 4 4 4 4 (weil jede 4 der kleineren Menge 4 Mal in der größeren Menge gefunden wird)
oder
4 (weil in Mengen keine Elemente doppelt vorkommen sollten)

Wenn ich in Delphi mit Mengen arbeite, dann kenne ich das so, dass Elemente in Mengen vorkommen oder auch nicht. Es kann aber nicht ein Element mehrfach vorkommen.
Also tendiere ich zur letztgenannten Lösung.

Vielleicht sollte mal jemand ein paar Testdaten (mit nicht mehr als 10 Zahlen in einem Array) zusammenstellen und es sollte auch festgesetzt werden, ob Elemente mehrfach vorkommen dürfen, und wie dann zu verfahren ist.
Und wenn dann mehrere Routinen korrekte Ergebnisse liefern kann man mit großen Mengen die Performance testen.
So wie es jetzt ist, macht das einfach keinen Sinn.

[Laser]

Moin,

Zitat von Amateurprofi:

Wenn wir 2 Arrays haben mit den Zahlen
1 4 4 4 4 7 und
4 4 4
Wie sollte dann die Schnittmenge aussehen?
4 4 4 (weil das die ursprüngliche Anzahl der 4en in der kleineren Menge ist)
oder
4 4 4 4 (weil ja auch die vierte 4 der größeren Menge in der kleineren gefunden wird)
oder
4 4 4 4 4 4 4 4 4 4 4 4 (weil jede 4 der kleineren Menge 4 Mal in der größeren Menge gefunden wird)
oder
4 (weil in Mengen keine Elemente doppelt vorkommen sollten)

Wenn ich in Delphi mit Mengen arbeite, dann kenne ich das so, dass Elemente in Mengen vorkommen oder auch nicht. Es kann aber nicht ein Element mehrfach vorkommen.
Also tendiere ich zur letztgenannten Lösung.

Vielleicht sollte mal jemand ein paar Testdaten (mit nicht mehr als 10 Zahlen in einem Array) zusammenstellen und es sollte auch festgesetzt werden, ob Elemente mehrfach vorkommen dürfen, und wie dann zu verfahren ist.
Und wenn dann mehrere Routinen korrekte Ergebnisse liefern kann man mit großen Mengen die Performance testen.
So wie es jetzt ist, macht das einfach keinen Sinn.

innerhalb der jeweiligen Menge kommen einzelne Elemente 0 bis 1 mal vor aber nicht mehrfach.

Für das Verständnis sollten diese Testdaten reichen:

Code:

Testdaten:
N1: 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20
N2: 02 06 08 12 14 16 18 20 22 24 26 28 30 32
N3: 03 06 09 15 18 24

Schnittmenge:
N0: 06 18

Der Festplattenzugriff ist für die Performance entscheidend. Daher habe ich mich noch nicht ganz vom "Rumgehüpfe" verabschiedet. Der Ansatz ist jetzt:

Code:

UntereSchwelle = größtes erstes Element aus Datei N1.. N3 = 03
ObereSchwelle = kleinstes letztes Element aus Datei N1..N3 = 20
vorzeitig beenden, falls  sich leere Schnittmenge ergibt
jeweils Anzahl Elemente in N1..N3 feststellen
Mit kleinster Datei starten für alle Dateien
  kleine Dateien komplett lesen (Grenze z.B. 4 KB)
  große Dateien nach UntererSchwelle und ObereSchwelle binär durchsuchen
  große Datei von UntererSchwelle bis ObereSchwelle komplett lesen
  Schnittmenge von 2 Dateien erzeugen
  vorzeitig beenden, falls  sich leere Schnittmenge ergibt

Angesichts der goßen Datenmengen, die von der Platte (nicht aus dem Puffer) gelesen werden müssen, wird dieser mit wenig Aufwand eingegrenzt und dann nur noch ein Teil der Daten von HDD gelesen.

Unter Linux kann man den Festplattenpuffer so löschen:

Code:

echo 3 | sudo tee /proc/sys/vm/drop_caches

Quelle: http://www.linuxatemyram.com/play.html

Weiß jemand, wie das unter Windows XP und 7 geht? Notfalls muss man rebooten.

[BUG]

Warum willst du den Puffer nochmal löschen? Dadurch kann es nur langsamer werden

[Furtbichler]

Nein, er will reproduzierbare Tests.

Na, teste mal dein Rumgehüpfe. Ich denke, der Zeitgewinn, wenn überhaupt, wird marginal sein.

Ich weiss nicht, wo die Dateien herkommen, aber wenn sie vor kurzem auf dem System gelandet sind, sind Teile davon bestimmt noch im RAM.

Dessenungeachtet würde ich wirklich mal mit TMappedFile experimentieren, das wird dir das Rumhüpfen verleiden. Das geht wirklich saumäßig schnell.

Eins zum Schluss: Denk mal an KISS