![]() |
AW: Schnittmenge von mehreren Mengen ermitteln
Zitat:
lg |
AW: Schnittmenge von mehreren Mengen ermitteln
Hallo,
Zitat:
![]() Hier 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. |
Alle Zeitangaben in WEZ +1. Es ist jetzt 01:48 Uhr. |
Powered by vBulletin® Copyright ©2000 - 2025, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz