|
Schnittmenge von mehreren Mengen ermitteln
Moin,
gegeben seien n (=1 bis ca. 12) Dateien, in denen jeweils eine Anzahl a (=2 bis ca. 5.000.000) 64-bit Integer-Schlüssel s abgespeichert sind. s liegen jeweils aufsteigend sortiert vor. Gesucht ist ein möglichst schneller Algorithmus: Erzeuge eine Datei output der Schlüssel s, die in allen n Dateien vorkommen. Intuitiv würde ich wie folgt vorgehen:
Code:
- feststellen der Anzahl der Datensätze in den n Dateien
- Anzahl dieser Datensätze sortieren, ergibt Dateien n1... <... n12, n1 enthält wenigste Datensätze, n12 die meisten - Dateien n1-n12 öffnen, Datei output erstellen - für jeden Datensatz in n1 feststellen, ob der Schlüssel auch in Dateien n2.. n12 enthalten ist - bei ja den Schlüssel in ouput schreiben - alle Dateien schließen Noch ein paar Hintergundinfos zu den Schlüsseln: Ein Schlüssel repräsentiert letztlich den Integer-Wert für das Schlagwort "schwarz-weiß" (im Umkehrschluss daraus, nicht farbig und nicht unbekannt). Nicht enthalten ist die Information, ob es sich um ein Bild handelt. Manchmal sind in den Schlüsseln Datumswerte enthalten. Es ist nicht bekannt, in welchem der Schlüssel und es ist auch nicht sicher, dass es ein Datum ist. Mit steigender Anzahl von Schlüsseln ist es recht wahrscheinlich, dass man einen relativ stark eingrenzenden dabei hat: "Maier-Lüdenscheit". Reicht das so an Infos? Wäre meine angedachte Vorgehensweise so ok oder fällt Euch 'was Besseres ein? |
AW: Schnittmenge von mehreren Mengen ermitteln
Zitat:
Spontan hätte ich es so gemacht:
Code:
Lässt sich evtl. noch etwas optimieren (beispielsweise kann die Suche abgebrochen werden, wenn bei einem Datensatz das Ende erreicht wurde). Hoffe, ich habe keinen Denkfehler mehr drin ;)
Speichere für alle Datensätze einen Index, initialisiert mit 0
für alle Werte aus n0: Setze "alleGleich" auf true // für alle Datensätze nj von 1 bis n erhöhe den Index j solange um 1, bis Ende von Datensatz nj erreicht ist oder bis Wert in nj >= Wert aus n0 ist // Wenn Ende nicht erreicht oder Wert aus nj > Wert aus n0 setze "alleGleich" auf false // wenn "alleGleich" füge Wert aus n0 zum Ergebnis hinzu Wie gut sind deine Java-Kenntnisse? Ich habe das gerade mal in Java programmiert. lg |
AW: Schnittmenge von mehreren Mengen ermitteln
Ich würde eine bzw. zwei Hashmaps nehmen:
1. Lies 1.Datei in Hashmap A 2. Für jede folgende Datei 2.1 Hashmap B = leere Hashmap 2.2 Für jede Zahl in der Datei: Wenn Zahl in A dann füge Zahl in B ein 2.3 A <-- B B enthält nun die Zahlen, die in allen Dateien sind. Hashmap ist einfach viel schneller als eine binäre Suche und wird auch nicht bei großen N langsamer. |
AW: Schnittmenge von mehreren Mengen ermitteln
Oder so :thumb:
;) Edit: Aber schneller als meine Lösung dürfte das auch nicht sein, eher im Gegenteil. Es müssen trotzdem alle Zeilen aller Dateien iteriert werden, zusätzlich entsteht durch das Einfügen/Suchen in der Hashmap ein Overhead (auch wenn der bei Hashmaps eher gering ausfällt). Mein Ansatz funktioniert ja nicht nach binärer Suche und es werden (maximal) alle Zeilen aller Dateien *einmal* betrachtet. |
AW: Schnittmenge von mehreren Mengen ermitteln
:mrgreen:
|
AW: Schnittmenge von mehreren Mengen ermitteln
Zitat:
Zitat:
Edit: Dein Post kam vor meinem Edit, wo war die rote Box? :gruebel: |
AW: Schnittmenge von mehreren Mengen ermitteln
Moin,
vielen Dank für die Vorschläge. Ich rechne mit maximal 25.500 Festplattenlesezugriffen für folgendes Beispiel mit der Schnittmenge aus 500/2.000/30.000/5.000.000 Elementen bzw. Datensätzen s. Neben den Plattenzugriffen scheint mir alles laufzeitmäßig nicht relevant.
Code:
Da die Daten sortiert vorliegen, ist eine binäre Suche möglich. Aufgrund der Definition der Schlüssel ist eine recht genaue Abschätzung, die den größten Teil der worst case Festplattenzugriffe einsparen dürfte.
Datei n n1 n2 n3 n4 Summe
Datensätze s 500 2.000 30.000 5.000.000 Log 2 8,97 10,97 14,87 22,25 Suchzugriffe worst case 9 11 15 23 Suchzugriffe Schnittmenge 500 11 x 500 15 x 500 23 x 500 Summenbildung 500 5.500 7.500 11.500 25.000 @patti: Meine Java-Kenntnisse beruhen auf einem eintägigen Kurs vor ca. 15 Jahren. Das hat eigentlich nur gereicht, mich über fehlende vernünftige Speicherfreigabe und fehlende Assembler inline Makros auzuregen. Verstehe ich Deinen Pseudocode richtig, dass nahe zu alle Schlüssel von der Platte gelesen werden? @Furtbichler: Dafür müssten alle Dateien komplett gelesen werden oder? 2. Für jede folgende Datei 2.1 Hashmap B = leere Hashmap |
AW: Schnittmenge von mehreren Mengen ermitteln
Zitat:
Überschlagsmäßig wird dafür 50 Megabyte RAM benötigt. Sobald jede Datei als Array im Speicher liegt, kannst du die Schnittmenge von zwei Arrays bestimmen. Danach kannst du die beiden Arrays wegwerfen und mit dem Ergebnis und dem nächsten Array wieder die Schnittmenge bilden. Die Schnittmenge von zwei Arrays zu bilden sollte in sehr kurzer Zeit machbar sein. O(max(n, m)) oder sowas. |
AW: Schnittmenge von mehreren Mengen ermitteln
Zitat:
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). Das nur mal so am Rande. |
AW: Schnittmenge von mehreren Mengen ermitteln
Zitat:
Wenn sie in etwa gleich groß sind, dann bekommst du mit dem Ansatz allerdings ein Problem mit der Laufzeit, dann sollte mein Ansatz schneller sein. Beispiel mit 4 Datensätzen mit jeweils 20.000 Einträgen: Mit deinem Ansatz brauchst du im worst-case ca. 20.000*(3*15) = 900.000 Lesezugriffe (log_2(20.000) = ca. 14,288). Mein Ansatz liest jeden Eintrag maximal einmal von der Platte, also hier im worst-case 20.000*4 = 80.000 Zugriffe. Zitat:
|
AW: Schnittmenge von mehreren Mengen ermitteln
Zitat:
lg |
AW: Schnittmenge von mehreren Mengen ermitteln
Hallo,
Zitat:
 http://www.delphipraxis.net/1156016-post2.htmlHier etwas abgewandelt
Code:
->EDIT: @Laser<-
- feststellen der Anzahl der Datensätze in den n Dateien
- Anzahl dieser Datensätze sortieren, ergibt Dateien n1... <... n12, n1 enthält wenigste Datensätze, n12 die meisten - n1 -> tmp - wiederhole für Datei = n2 bis n12 --tmpIndex = 0, DateiIndex = 0 --wiederhole solange (TmpIndex noch nicht maximal) ODER (DateiIndex noch nicht maximal ) ---Falls tmp(tmpIndex)=Datei(DateiIndex)=> ----Schreibe Schluessel nach Out ----tmpIndex= tmpIndex+1 ----DateiIndex= DateiIndex+1 ---sonst ----Solange (tmp(tmpIndex)<Datei(DateiIndex)) UND (TmpIndex noch nicht maximal) -----tmpIndex= tmpIndex+1 ----Solange (tmp(tmpIndex)>Datei(DateiIndex)) UND (DateiIndex noch nicht maximal ) -----DateiIndex= DateiIndex+1 -- -- tmp löschen -- out in tmp umbennen - - tmp in out umbennen Das hin- und herspringen in einer 50 MB Datei zum Beispiel zu Beginn von Mitte dann 0.25 dann 0.125 .. zum Ende von Mitte dann 0.75 dann 0.875.. ist ja auch nicht das schnellste, ausser man hat wirklich nur noch wenige Elemente in der Restliste. Aber vielleicht lässt sich das ja nutzen, indem man sich die Position/Schlüssel also den Weg merkt. Selbst 2^32 Schluessel haben bei binärer Suche nur 32 Wegpunkte. Gruß Horst |
AW: Schnittmenge von mehreren Mengen ermitteln
Zitat:
Zitat:
Zitat:
|
AW: Schnittmenge von mehreren Mengen ermitteln
Da die Daten sortiert vorliegen, würde mir folgendes Vorgehen einfallen:
Alle Dateien öffnen und den Datensatzzeiger auf Anfang stellen von jeder Datei. 1) alle Datensätze wo der Zeiger steht vergleichen -wenn gleich dann ist es eine Schnittmenge in allen Dateien -> merken/ausgeben -> Alle Zeiger einen weiterschieben. Jeweils den Datensatzzeiger weiterschieben, wo der aktuelle Datensatz der kleinste von den gerade gelesen ist. Wenn mehrere gleich sind alle weiterschieben. Springe zu 1) |
AW: Schnittmenge von mehreren Mengen ermitteln
Moin,
Zitat:
|
AW: Schnittmenge von mehreren Mengen ermitteln
Zitat:
|
AW: Schnittmenge von mehreren Mengen ermitteln
Zitat:
Die Frage ist sicherlich, wie man einen Festplattenzugriff definiert. Für mich ist sowohl "Ein Byte lesen" als auch "100000 Bytes lesen" ein Festplattenzugriff. Denn in jedem Fall fällt die Latenzzeit an (irgendwas so um die 10ms) egal wie viel man liest. (Die Zeit braucht der Lesekopf, um an die Stelle zu fahren wo die Daten sind.) Sobald der Lesekopf einmal angefangen hat, zu lesen kann er das ziemlich schnell. So auf 100 MB/s sind da schon drin. Falls du also jede 64-bit Zahl einzeln liest, bekommst du 100 Zahlen pro Sekunde. Liest du sequenziell alles ein bekommst du 13 Mio Zahlen pro Sekunde. Caching kann da jetzt noch einiges reißen aber ich denke ich habe meinen Grundgedanken klar gemacht. Auf einer SSD sieht das natürlich anders aus, aber man sollte ja nicht davon ausgehen dass jeder ne SSD hat. Falls es also um Datenmengen geht die problemlos in den RAM passen, kann es durchaus sinnvoll sein erst mal alles zu laden. Wenn du mir nicht glaubst, probiere es bitte mal aus ;-) |
AW: Schnittmenge von mehreren Mengen ermitteln
Moin,
Zitat:
|
AW: Schnittmenge von mehreren Mengen ermitteln
Zitat:
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; |
AW: Schnittmenge von mehreren Mengen ermitteln
Moin,
Zitat:
Die unteren 32 Bit des Schlüssels enthalten eine fortlaufende Zahl. Damit kann ein gutes Sprungziel berechnet werden, was die Plattenzugriffe noch einmal reduziert. |
AW: Schnittmenge von mehreren Mengen ermitteln
Bin mal gespannt, wie schnell ihr mit eurem Rumgehüpfe seid. ;-)
|
AW: Schnittmenge von mehreren Mengen ermitteln
Moin,
Zitat:
Einzelne Schlüssel zu lesen, bremst ziemlich aus. Das wurde hier gut beschrieben: http://www.delphipraxis.net/1156224-post17.html |
AW: Schnittmenge von mehreren Mengen ermitteln
Wie wäre es mit einer Kombination?
Erstmal die zwei kleinsten Dateien in den Speicher laden, und die Schnittmenge bilden. (Mit zwei Indizes, wie von generic erklärt) Danach immer die nächste Datei in den Speicher laden und die bisherigen Einträge per binärer Suche in der Datei suchen. Das laden der Datei könnte man noch in einen Thread auslagern. Ist aber fraglich ob sich das lohnt - die Datenmenge klingt nach einer Rechenzeit von 300ms. Die Synchronisation von Threads könnte das schon wieder verlangsamen. Damit sollte die Schnittmenge schnell kleiner werden (damit die binäre Suche flott ist) aber am Anfang dürfte das Verfahren mit den zwei Indizes besser sein. Und solange es geht immer im RAM arbeiten, und keine einzelnen Werte von der Platte lesen! Damit kann man jeden Algorithmus zum Schneckentempo zwingen. (ggf. ein Bandlaufwerk in Erwägung ziehen....) |
AW: Schnittmenge von mehreren Mengen ermitteln
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. |
AW: Schnittmenge von mehreren Mengen ermitteln
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. |
AW: Schnittmenge von mehreren Mengen ermitteln
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? |
AW: Schnittmenge von mehreren Mengen ermitteln
Zitat:
|
AW: Schnittmenge von mehreren Mengen ermitteln
Zitat:
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 :stupid: |
AW: Schnittmenge von mehreren Mengen ermitteln
@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. |
AW: Schnittmenge von mehreren Mengen ermitteln
Moin,
Zitat:
Erst hatte ich den Verdacht, dass Plattenzugriffe einfach nur "wegdefiniert" werden. :x Nach näherer Betrachtung scheint es aber richtig, zumindest die einzelnen Dateien komplett einzulesen. :shock: Erst mal ein paar Annahmen für Lesezugriffe: HDD: ca. 50 MB/s, 10 ms Zugriffszeit, max. 2 TB für das Programm, das wird nicht eng SSD: ca. 300 MB/s, < 1 ms, keine Kapazität für dieses Programm RAM: ca. 10.240 MB/s, Nanosekundenbereich, max. 20 GB für dieses Programm, RAM, Ramdisk oder Festplattenpuffer Gehen wir mal davon aus, dass es ca. 1 Sekunde dauert, bis 5.000.000 Schlüssel aus einer Datei eingelesen wurden. In dieser Zeit könnte man sich nur ca. 100 mal "Rumgehüpfe" à 10 ms beim erstmaligen Einlesen leisten. In meinem Beispiel benötigt man 11.500 mal. Das wird vermutlich selbst dann nicht schneller als das Einlesen, wenn man davon ausgeht, dass ein Großteil der Anfragen aus Festplattenpuffern des Betriebssystems bedient werden können. Ein "Rumgehüpfe" im RAM könnte auch ein Schuss nach hinten sein. Das überlege ich mir noch. Eine gute Idee finde ich, Dateien im Thread zu lesen. Mehr als 1 zur Zeit schient mir auch nicht sinnvoll. Memory Mapped Files scheint mir auch eher ungünstig. Zu http://en.wikipedia.org/wiki/Hash_join muss ich mal schauen, ob ich auch einen für mich verständlichen deutschen Artikel finde.@Furtbichler Wie hast Du bei Deinem Test sichergestellt, dass Du die Dateien nicht aus dem Puffer des Betriebssystems liest? |
AW: Schnittmenge von mehreren Mengen ermitteln
Moin,
Zitat:
Zitat:
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. |
AW: Schnittmenge von mehreren Mengen ermitteln
Zitat:
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:
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).
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) [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] |
AW: Schnittmenge von mehreren Mengen ermitteln
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 |
AW: Schnittmenge von mehreren Mengen ermitteln
Zitat:
Ich habe zudem eine Abbruchbedingung: Wenn die Schnittmenge leer ist, werden keine weiteren Dateien mehr angefasst, wozu auch. Das verfälscht natürlich das Ergebnis. Also: Durchscannen aller 5 Mio Werte einer Datei geht ohne Optimierung im Worstcase in 140ms, wenn nämlich alle Dateien die gleichen 5 Mio Zahlen enthalten. Zitat:
Das Mapped File habe ich von hier: http://landman-code.blogspot.com/200...ce-i-last.htmlZitat:
Das, zusammen mit memory mapped files, dürfte die ideale Lösung sein bzw. die, gegen die eine Alternative bestehen müsste. |
AW: Schnittmenge von mehreren Mengen ermitteln
Hallo Furtbichler,
mich hat das auch interessiert und ich habe das mit binärer Suche versucht – war aber, die Performance betreffend, ein Flop. Also hab ich mir mal deine Lösung angeschaut. Sehr interessanter Ansatz, leider aber fehlerhaft.
Delphi-Quellcode:
Das " – 1 " gehört da m.E. nicht hin. Es verursacht, dass das letzte Element von data nicht in Intersect übernommen wrid.
for I := 0 to High(data) - 1 do begin
Ich nehme an da stand ursprünglich Length(data) – 1
Delphi-Quellcode:
Wenn das letzte Element in data größer ist als das letzte Element in Intersect dann wird j=n=Length(Intersect) und bei
while (j < n) and (Intersect[j] < data[i]) do inc(j);
Delphi-Quellcode:
wird auf Intersect[Length(Intersect)] zugegriffen, was einen Laufzeitfehler verursachen müßte.
if data[i] = Intersect[j] then begin
Du schriebst 140 ms bei 12 Files je 5 Mio Werten, wobei die Files bereits im RAM liegen und alle Files die gleichen Daten enthalten. Ich hab mal deine Prozedur auf meinem Rechner laufen lassen. Das "Alle Files identisch und bereits im RAM" habe ich so realisiert, dass das Array "data", das bei dir lokal definiert ist, als Parameter mitgegeben wird. Bei mir dauert das ganze bei unten stehendem Ablauf 300 ms. Hab ich da vielleicht irgendwas falsch verstanden? Oder hab ich nur 'nen lahmen Rechner? Auf was für einer Maschine erreichst du 140 ms?
Delphi-Quellcode:
Du wolltest gern bessere Lösungen sehen.
procedure IntersectFileWithHashmap(var Intersect,Data: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; procedure TMain.Button1Click(Sender: TObject); const count=5000000; var intersect,data:TSampleArray; i:integer; t:cardinal; begin SetLength(data,count); for i:=0 to High(data) do data[i]:=i+1; intersect:=Copy(data); t:=GetTickCount; for i:=1 to 11 do IntersectFileWithHashmap(intersect,data); t:=GetTickCount-t; ShowMessage('Anzahl='+IntToStr(Length(intersect))+#13+ 'Zeit='+IntToStr(t)+' ms'); end; Ich habe da einfach mal deine Prozedur genommen und an ein paar Stellen etwas entfernt. Du erstellst ein Array newIntersect, schreibst die gefundenen Werte hinein und stellst am Schluss newIntersect in Intersect. Das ist überflüssig. Anstatt kann man die gefundenen Werte direkt in das Array Intersect stellen. Mit diesen Änderungen braucht das Ganze (auf meinem Rechner) nur noch 250 ms, also eine Verbesserung um ca 15 %. Auf deinem Rechner müsste das dann 140*250/300 = 117 ms brauchen.
Delphi-Quellcode:
procedure xIntersectFileWithHashmap(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 ) and (data[i] = Intersect[j]) then begin Intersect[k] := data[i]; inc(k); end; end; setLength(Intersect, k); end; procedure TMain.Button2Click(Sender: TObject); const count=5000000; var intersect,data:TSampleArray; i:integer; t:cardinal; begin SetLength(data,count); for i:=0 to High(data) do data[i]:=i+1; intersect:=Copy(data); t:=GetTickCount; for i:=1 to 11 do xIntersectFileWithHashmap(intersect,data); t:=GetTickCount-t; ShowMessage('Anzahl='+IntToStr(Length(intersect))+#13+ 'Zeit='+IntToStr(t)+' ms'); end; Aber damit war ich auch nicht zufrieden, denn ich wollte ja auch auf meiner lahmen Krücke deine 140 ms toppen. Die unten stehende Version braucht bei identischen Daten (auf meinem Rechner) nur noch 110 ms, was, auf deinen Rechner umgerechnet 140*110/300 = 51 ms heißen sollte. Verglichen mit den 300 ms, die deine Prozedur auf meinem Rechner brauchte, ist das eine Verbesserung um ca. 65 %. Jedoch möchte ich mich nicht mit fremden (deinen) Federn schmücken. Auch meine Asm-Version baut im Prinzip auf deiner Lösung auf - und die ist einfach nur gut, auch wenn da ein paar Flüchtigkeitsfehler drin waren. Jetzt hoffe ich nur, daß ich bei meiner Asm-Version nichts übersehen habe......
Delphi-Quellcode:
FUNCTION IntersectData(var Intersect,Data:TSampleArray; length:integer):integer;
asm // IN : EAX=@Intersect, EDX=@Data, ECX=Anzahl der Elemente der bisherigen Schnittmenge // Out : Neue Anzahl der Elemente der Schnittmenge pushad // Temp:=ESP; Push EAX,ECX,EDX,EBX,Temp,EBP,ESI,EDI mov ebp,ecx // n := Length(intersect) test ebp,ebp je @ReturnZero // Schnittmenge ist leer mov esi,[edx] // @data[0] test esi,esi je @ReturnZero // Data ist leer mov edi,[eax] // @Intersect[0] test edi,edi // nur zur Sicherheit je @ReturnZero // Intersect leer xor ecx,ecx // j := 0 xor edx,edx // k := 0; xor ebx,ebx // for i := 0 jmp @CheckFor @WhileLoop: add ecx,1 // inc(j) cmp ecx,ebp // While (j < n) jae @SetRes @ForLoop: cmp [edi+ecx*4],eax // and Intersect[j] < data[i] jb @WhileLoop // do jne @NextFor mov [edi+edx*4],eax // Intersect[k] := data[i]; @NoStore: add edx,1 // inc(k); @NextFor: add ebx,1 // next i @CheckFor: cmp ebx,[esi-4] // i > High(data) jae @SetRes // ja, fertig mov eax,[esi+ebx*4] // data[i] jmp @ForLoop // Prüfung j<n nicht erforderlich @ReturnZero: xor edx,edx // k := 0 @SetRes: mov [esp+28],edx // popad stellt [esp-28] in EAX popad end; procedure TMain.Button3Click(Sender: TObject); const count=5000000; var intersect,data:TSampleArray; i,len:integer; t:cardinal; begin SetLength(data,count); for i:=0 to High(data) do data[i]:=i+1; intersect:=Copy(data); len:=Length(intersect); t:=GetTickCount; for i:=1 to 11 do len:=IntersectData(intersect,data,len); SetLength(intersect,len); t:=GetTickCount-t; ShowMessage('Anzahl='+IntToStr(Length(intersect))+#13+ 'Zeit='+IntToStr(t)+' ms'); end; |
AW: Schnittmenge von mehreren Mengen ermitteln
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.
|
AW: Schnittmenge von mehreren Mengen ermitteln
Zitat:
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 |
AW: Schnittmenge von mehreren Mengen ermitteln
Zitat:
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. |
AW: Schnittmenge von mehreren Mengen ermitteln
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. :mrgreen: @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 :stupid:). 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:
Weiteres Optimierungspotential wäre:
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; 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 |
AW: Schnittmenge von mehreren Mengen ermitteln
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 |
| Alle Zeitangaben in WEZ +1. Es ist jetzt 14:02 Uhr. |
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz