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 1 von 7  1 23     Letzte » 
Laser

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

Schnittmenge von mehreren Mengen ermitteln

  Alt 11. Mär 2012, 14:01
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?
Liebe Grüße
Laser
  Mit Zitat antworten Zitat
Benutzerbild von patti
patti

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

AW: Schnittmenge von mehreren Mengen ermitteln

  Alt 11. Mär 2012, 15:28
s liegen jeweils aufsteigend sortiert vor.
Das lässt sich ausnutzen!

Spontan hätte ich es so gemacht:

Code:
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
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

Wie gut sind deine Java-Kenntnisse? Ich habe das gerade mal in Java programmiert.

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

n/a Beiträge
 
#3

AW: Schnittmenge von mehreren Mengen ermitteln

  Alt 11. Mär 2012, 15:34
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.

Geändert von Furtbichler (11. Mär 2012 um 15:37 Uhr)
  Mit Zitat antworten Zitat
Benutzerbild von patti
patti

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

AW: Schnittmenge von mehreren Mengen ermitteln

  Alt 11. Mär 2012, 15:35
Oder so



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.
Patrick Kreutzer
[Informatik-Student im 4. Semester]
http://www.patti-k.de/

Geändert von patti (11. Mär 2012 um 15:39 Uhr)
  Mit Zitat antworten Zitat
Furtbichler
(Gast)

n/a Beiträge
 
#5

AW: Schnittmenge von mehreren Mengen ermitteln

  Alt 11. Mär 2012, 15:38
  Mit Zitat antworten Zitat
Benutzerbild von patti
patti

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

AW: Schnittmenge von mehreren Mengen ermitteln

  Alt 11. Mär 2012, 15:41
Bezieht sich das jetzt auf mein oder auf mein Edit?

Edit: Dein Post kam vor meinem Edit, wo war die rote Box?
Patrick Kreutzer
[Informatik-Student im 4. Semester]
http://www.patti-k.de/
  Mit Zitat antworten Zitat
Laser

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

AW: Schnittmenge von mehreren Mengen ermitteln

  Alt 11. Mär 2012, 20:15
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:
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
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.


@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
Liebe Grüße
Laser
  Mit Zitat antworten Zitat
Benutzerbild von jfheins
jfheins

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

AW: Schnittmenge von mehreren Mengen ermitteln

  Alt 11. Mär 2012, 20:51
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.
Wenn das so ist, dann gibt es eine einfache Lösung die Performance zu erhöhen: 4 Festplattenlesezugriffe. Einfach jede Datei erstmal in den RAM laden. Alles im RAM machen und das Ergebnis wieder auf die HDD schreiben
Ü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.
  Mit Zitat antworten Zitat
Furtbichler
(Gast)

n/a Beiträge
 
#9

AW: Schnittmenge von mehreren Mengen ermitteln

  Alt 12. Mär 2012, 07:09
@Furtbichler:
Dafür müssten alle Dateien komplett gelesen werden oder?
Meinst Du "komplett in den RAM"? Nein.
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.

Geändert von Furtbichler (12. Mär 2012 um 07: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
 
#10

AW: Schnittmenge von mehreren Mengen ermitteln

  Alt 12. Mär 2012, 11:06
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.
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.

Verstehe ich Deinen Pseudocode richtig, dass nahe zu alle Schlüssel von der Platte gelesen werden?
Im schlimmsten Fall, ja.
Patrick Kreutzer
[Informatik-Student im 4. Semester]
http://www.patti-k.de/
  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 17:45 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