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 2 von 7     12 34     Letzte » 
Benutzerbild von patti
patti

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

AW: Schnittmenge von mehreren Mengen ermitteln

  Alt 12. Mär 2012, 12:14
Jede Binärsuche ist vom Aufwand O(log n), jede Suche in einer Hashmap O(1).

Das nur mal so am Rande.
Das Problem wird hier nicht die Suche an sich sein, sondern das Laden von der Platte (langsames I/O...). Bei deinem Ansatz müssen zuerst alle Daten von der Platte gelesen werden (und zwar sicher *alle*), zusätzliche müssen sie dann noch in eine Hashtable geschmissen werden, und erst dann beginnt die Suche (das mag in O(1) klappen, aber vorher ging schon sehr viel Zeit für das Laden drauf...). Die Idee mit der Binär-Suche ist ja gerade, nicht alle Elemente lesen zu müssen. Mein Ansatz liest zwar auch (im schlimmsten Fall) alle Elemente ein, allerdings hab ich den Overhead von 'ner Hashtable nicht (O(1) ist nicht gleich O(1)...).

lg
Patrick Kreutzer
[Informatik-Student im 4. Semester]
http://www.patti-k.de/
  Mit Zitat antworten Zitat
Horst_

Registriert seit: 22. Jul 2004
Ort: Münster Osnabrück
116 Beiträge
 
#12

AW: Schnittmenge von mehreren Mengen ermitteln

  Alt 12. Mär 2012, 14:28
Hallo,

Das Problem wird hier nicht die Suche an sich sein, sondern das Laden von der Platte (langsames I/O...). Bei deinem Ansatz müssen zuerst alle Daten von der Platte gelesen werden (und zwar sicher *alle*)
Darum wird fast kaum herum kommen, alle einzulesen, selbst bei Deinem Verfahren http://www.delphipraxis.net/1156016-post2.html
Hier etwas abgewandelt
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
 - 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
->EDIT: @Laser<-
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

Geändert von Horst_ (12. Mär 2012 um 16:12 Uhr)
  Mit Zitat antworten Zitat
Benutzerbild von patti
patti

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

AW: Schnittmenge von mehreren Mengen ermitteln

  Alt 12. Mär 2012, 14:36
Darum wird fast kaum herum kommen, alle einzulesen, selbst bei Deinem Verfahren http://www.delphipraxis.net/1156016-post2.html
Schon klar, siehe mein Post oben:

Verstehe ich Deinen Pseudocode richtig, dass nahe zu alle Schlüssel von der Platte gelesen werden?
Im schlimmsten Fall, ja.


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
Was aber ja bei meinem Ansatz nicht der Fall ist
Patrick Kreutzer
[Informatik-Student im 4. Semester]
http://www.patti-k.de/
  Mit Zitat antworten Zitat
generic

Registriert seit: 24. Mär 2004
Ort: bei Hannover
2.405 Beiträge
 
Delphi XE5 Professional
 
#14

AW: Schnittmenge von mehreren Mengen ermitteln

  Alt 12. Mär 2012, 15:10
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)
Coding BOTT - Video Tutorials rund um das Programmieren - https://www.youtube.com/channel/UCUG...aXLclwO9qA-lzA
  Mit Zitat antworten Zitat
Laser

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

AW: Schnittmenge von mehreren Mengen ermitteln

  Alt 12. Mär 2012, 20:13
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.
Liebe Grüße
Laser
  Mit Zitat antworten Zitat
Laser

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

AW: Schnittmenge von mehreren Mengen ermitteln

  Alt 12. Mär 2012, 20:22
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).
Ich will möglichst nicht alles lesen. Für die Hasmap mit O(1) brauche ich als Voraussetzung O(n) Lesezugriffe auf die Platte. Für die Binärsuche brauche ich keine weitere Voraussetzung zu schaffen.
Liebe Grüße
Laser
  Mit Zitat antworten Zitat
Benutzerbild von jfheins
jfheins

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

AW: Schnittmenge von mehreren Mengen ermitteln

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

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

AW: Schnittmenge von mehreren Mengen ermitteln

  Alt 12. Mär 2012, 21:11
Moin,
mit der Schnittmenge aus 500/2.000/30.000/5.000.000 Elementen bzw. Datensätzen s
Ist es immer so, dass die einzelnen Dateien so unterschiedlich groß sind? Und dass vor allem immer eine Datei dabei ist, die in Relation so klein ist? Wenn ja, dann ist der Ansatz mit der binären Suche sicherlich nicht verkehrt.
Größenunterschiede sind wahrscheinlich. Im unwahrscheinlichen Fall ist die Anzahl der Elemente mindestens einer Menge nahezu sicher < 1.000.
Liebe Grüße
Laser
  Mit Zitat antworten Zitat
Furtbichler
(Gast)

n/a Beiträge
 
#19

AW: Schnittmenge von mehreren Mengen ermitteln

  Alt 12. Mär 2012, 21:12
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).
Ich will möglichst nicht alles lesen. Für die Hasmap mit O(1) brauche ich als Voraussetzung O(n) Lesezugriffe auf die Platte.
Du hast die O(*)-Notation nicht verstanden.

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;

Geändert von Furtbichler (12. Mär 2012 um 21:23 Uhr)
  Mit Zitat antworten Zitat
Laser

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

AW: Schnittmenge von mehreren Mengen ermitteln

  Alt 12. Mär 2012, 21:31
Moin,
Hallo,
->EDIT: @Laser<-
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.
Ich habe das noch nicht vertieft. Es wird keine übliche binäre Suche sein, bei der das Intervall in der Mitte geteilt wird. Statt dessen wird ein Sprungziel aus dem 64-Bit Schlüssel berechnet.

Die unteren 32 Bit des Schlüssels enthalten eine fortlaufende Zahl. Damit kann ein gutes Sprungziel berechnet werden, was die Plattenzugriffe noch einmal reduziert.
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:53 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