AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Zurück Delphi-PRAXiS Programmierung allgemein Algorithmen, Datenstrukturen und Klassendesign FreePascal Schnittmenge von mehreren Mengen ermitteln

Schnittmenge von mehreren Mengen ermitteln

Offene Frage von "Horst_"
Ein Thema von Laser · begonnen am 11. Mär 2012 · letzter Beitrag vom 21. Mär 2012
Antwort Antwort
Seite 3 von 7     123 45     Letzte » 
Furtbichler
(Gast)

n/a Beiträge
 
#21

AW: Schnittmenge von mehreren Mengen ermitteln

  Alt 12. Mär 2012, 21:40
Bin mal gespannt, wie schnell ihr mit eurem Rumgehüpfe seid.
  Mit Zitat antworten Zitat
Laser

Registriert seit: 2. Jan 2009
Ort: Ubunutu 10.10
18 Beiträge
 
FreePascal / Lazarus
 
#22

AW: Schnittmenge von mehreren Mengen ermitteln

  Alt 12. Mär 2012, 21:42
Moin,
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)
wenn ich das richtig verstehe, wird hier sehr viel von Platte gelesen. Vor allem werden die Dateien n3...nx gelesen, wenn man nach dem Lesen von n1 und n2 teilweise schon feststellen kann, dass eine Identität bzw. Schnittmenge über alle nicht mehr möglich ist.

Einzelne Schlüssel zu lesen, bremst ziemlich aus. Das wurde hier gut beschrieben:
http://www.delphipraxis.net/1156224-post17.html
Liebe Grüße
Laser
  Mit Zitat antworten Zitat
Benutzerbild von jfheins
jfheins

Registriert seit: 10. Jun 2004
Ort: Garching (TUM)
4.579 Beiträge
 
#23

AW: Schnittmenge von mehreren Mengen ermitteln

  Alt 12. Mär 2012, 22:19
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....)
  Mit Zitat antworten Zitat
Benutzerbild von BUG
BUG

Registriert seit: 4. Dez 2003
Ort: Cottbus
2.094 Beiträge
 
#24

AW: Schnittmenge von mehreren Mengen ermitteln

  Alt 12. Mär 2012, 22:22
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.
  Mit Zitat antworten Zitat
Namenloser

Registriert seit: 7. Jun 2006
Ort: Karlsruhe
3.724 Beiträge
 
FreePascal / Lazarus
 
#25

AW: Schnittmenge von mehreren Mengen ermitteln

  Alt 12. Mär 2012, 22:45
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.
  Mit Zitat antworten Zitat
Benutzerbild von BUG
BUG

Registriert seit: 4. Dez 2003
Ort: Cottbus
2.094 Beiträge
 
#26

AW: Schnittmenge von mehreren Mengen ermitteln

  Alt 12. Mär 2012, 23:19
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?
  Mit Zitat antworten Zitat
Benutzerbild von patti
patti

Registriert seit: 20. Okt 2004
Ort: Mittelfranken
665 Beiträge
 
Turbo Delphi für Win32
 
#27

AW: Schnittmenge von mehreren Mengen ermitteln

  Alt 12. Mär 2012, 23:22
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?
Patrick Kreutzer
[Informatik-Student im 4. Semester]
http://www.patti-k.de/
  Mit Zitat antworten Zitat
Furtbichler
(Gast)

n/a Beiträge
 
#28

AW: Schnittmenge von mehreren Mengen ermitteln

  Alt 12. Mär 2012, 23:30
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
  Mit Zitat antworten Zitat
Benutzerbild von Bummi
Bummi

Registriert seit: 15. Jun 2010
Ort: Augsburg Bayern Süddeutschland
3.470 Beiträge
 
Delphi XE3 Enterprise
 
#29

AW: Schnittmenge von mehreren Mengen ermitteln

  Alt 12. Mär 2012, 23:42
@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.
Thomas Wassermann H₂♂
Das Problem steckt meistens zwischen den Ohren
DRY DRY KISS
H₂ (wenn bei meinen Snipplets nichts anderes angegeben ist Lizenz: WTFPL)
  Mit Zitat antworten Zitat
Laser

Registriert seit: 2. Jan 2009
Ort: Ubunutu 10.10
18 Beiträge
 
FreePascal / Lazarus
 
#30

AW: Schnittmenge von mehreren Mengen ermitteln

  Alt 13. Mär 2012, 00:41
Moin,
Moin,
Einfach jede Datei erstmal in den RAM laden.
Dann habe ich schon über 5.000.000 Festplattenzugriffe. Danach ist es dann alles egal, wie schnell man im RAM arbeitet.
Hmmmm, das sehe ich anders.

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
auch hmmmmm
Erst hatte ich den Verdacht, dass Plattenzugriffe einfach nur "wegdefiniert" werden.
Nach näherer Betrachtung scheint es aber richtig, zumindest die einzelnen Dateien komplett einzulesen.

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?
Liebe Grüße
Laser
  Mit Zitat antworten Zitat
Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 08:33 Uhr.
Powered by vBulletin® Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2021 by Daniel R. Wolf