Schnittmenge zweier Textdateien

Re(8): Schnittmenge zweier Textdateien

Simon Oberhammer — Fri, 31 Aug 2001 08:23:26 GMT

aber zum glück hat er die angabe erweitert: es gibt günstigerweise keine doppelten einträge. dann ist mein vorschlag ja nur mehr ineffizient

................

"Ideally, hyperthreading, which has been under development for four and a half years, will show meatier benefits. An individual could play games while simultaneously downloading multimedia files from the Internet with a computer containing the technology"

- intel.com

Re(3): Schnittmenge zweier Textdateien

TomCat — Thu, 30 Aug 2001 18:09:08 GMT

Perl ist gerade für solche Aufgaben mit seinen assoc. arrays extrem schnell. Ausserdem kannst du die arrays leicht auf dbm - files mappen, falls dir doch der Hauptspeicher zu eng wird.

Cats make purrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrfect friends.

Re(3): Schnittmenge zweier Textdateien

Fly — Thu, 30 Aug 2001 17:44:21 GMT

Passiert automatisch nach dieser Methode.

Läuft im Wesentlichen so ab:

Zuerst die erste Liste einlesen und bei der Gelegenheit gleich sortiert im Hashtable eintragen (ich hab mir zuerst überlegt es in einem sorttree unterzubringen, aber nachdem wir's ja nicht "wirklich" sortieren sondern nur wiederfinden müssen ist's mit'm Hash wesentlich effizienter. Wie gross soll's denn nur sein?)

Dann jedes Element der zweiten Liste in der ersten suchen. Wird's gefunden, in die Ergebnisliste ausgeben und Eintrag im Table löschen.

Wenn's nochmal vorkommt wird's eh nicht mehr gefunden.

Wenn Mehrfacheinträge sehr häufig sind, ist es ggf. vielleicht sogar effizienter, die Ergebnismenge ebenfalls wieder zu hashen und zuerst in dieser (kleineren) Menge zu suchen.

Shadows can be made real
if you kill in their name.

Re(8): Schnittmenge zweier Textdateien

Robert Craven — Thu, 30 Aug 2001 13:49:17 GMT

Ich hab damals nicht ganz genau aufgepasst. Ist die Schnittmenge zweier Multimengen wieder eine Multimenge?

Re(7): Schnittmenge zweier Textdateien

mjy@geizhals.at — Thu, 30 Aug 2001 13:22:01 GMT

Die Ausgangssituation nennt aber 2 Dateien, da können sehr wohl Duplikate vorkommen.

Marinos J. Yannikos <mjy@geizhals.at>

_{Education is an admirable thing, but nothing that is worth knowing can be taught
-- Oscar Wilde}

Re(2): Schnittmenge zweier Textdateien

cltom — Thu, 30 Aug 2001 13:09:48 GMT
tja, da wollte ich mal hören, womit so etwas am einfachsten zu lösen ist.

Ich dachte kurzfristig an ein perl-skript, da man das mit map in 5 zeilen lösen kann, ausserdem wäre es dann gleich online verfügbar. Habe allerdings keine Ahnung, wie lange das dann dauert.

Re(6): Schnittmenge zweier Textdateien

Robert Craven — Thu, 30 Aug 2001 13:04:45 GMT
Naja net wirklich. In einer Menge gibts mal von vornherein keine Doppelten. Damit stimmt dann schon die Ausganssituation nicht. Der Lösungsweg ist schon korrekt.

Re(2): Schnittmenge zweier Textdateien

cltom — Thu, 30 Aug 2001 13:03:12 GMT
Doppeleinträge sind (günstigerweise) sicher auszuschliessen.

Re(5): Schnittmenge zweier Textdateien

mjy@geizhals.at — Thu, 30 Aug 2001 12:59:59 GMT
Trivial, aber falsch.

Marinos J. Yannikos <mjy@geizhals.at>

_{Education is an admirable thing, but nothing that is worth knowing can be taught
-- Oscar Wilde}

Re(4): Schnittmenge zweier Textdateien

Robert Craven — Thu, 30 Aug 2001 12:56:48 GMT
Mal von doppelten abgesehen. Aber das ist ja eh trivial

Re(3): Schnittmenge zweier Textdateien

Robert Craven — Thu, 30 Aug 2001 12:55:14 GMT
Wieso falsch? (x el (A Schnitt B)), wenn (x el A) und (x el B).

Re: Schnittmenge zweier Textdateien

mjy@geizhals.at — Thu, 30 Aug 2001 12:54:37 GMT
1) kleinere Datei öffnen und alle Wörter in eine Hash-Tabelle (einmal!) eintragen
2) größere Datei öffnen und für jedes Wort in der Hash-Tabelle nachschauen, ob es in der anderen Datei vorgekommen ist. Falls ja, Wort ausgeben und Wort aus der Hash-Tabelle löschen (damit Wörter nicht doppelt ausgegeben werden!)

Marinos J. Yannikos <mjy@geizhals.at>

_{Education is an admirable thing, but nothing that is worth knowing can be taught
-- Oscar Wilde}

Re: Schnittmenge zweier Textdateien

Robert Craven — Thu, 30 Aug 2001 12:52:07 GMT
Texte sortieren (Doppelte streichen!). Kurze Liste gegen die Lange vergleichen. Wenn Hit dann zur Schnittmenge hinzufügen.

Re(2): Schnittmenge zweier Textdateien

mjy@geizhals.at — Thu, 30 Aug 2001 12:49:30 GMT
Ineffizient und vermutlich falsch (falsch gemäß Definition von "Schnittmenge", ob das auch in der Fragestellung so zu berücksichtigen ist, weiß ich natürlich nicht).

Marinos J. Yannikos <mjy@geizhals.at>

_{Education is an admirable thing, but nothing that is worth knowing can be taught
-- Oscar Wilde}

Re: Schnittmenge zweier Textdateien

The Cleaner — Thu, 30 Aug 2001 12:43:51 GMT
Nur ein kleiner Vorschlag der mir ad hoc einfällt:
Ich nehme an ',' ist das Trennzeichen.
Daher alle Strings in dem kleineren File in Mem lesen (Liste o.ä.),
Mit den Strings im größeren Vergleichen (1tes Zeichen, wenn gleich dann 2tes, usw..)
und die Schnittmenge wieder abspeichern.

Aber bei Texten mit 700 und 3000 Zeilen bist du ziemlich sicher auf der schnellen Seite mit heutigem Standard Equipment.

Für konkretere Angaben zur Geschwindigkeitsoptimierung wäre etwas mehr Info hilfreich (Welche Sprache? Wie schnell solls sein?).

HTH
The Cleaner

Re: Schnittmenge zweier Textdateien

Simon Oberhammer — Thu, 30 Aug 2001 12:37:12 GMT
also wenns um die schnittmenge der wörter zweier textdateien geht würd ich mal eine aufmachen,

wort einlesen - andere durschaun ob's das wort gibt. wenn ja: ist in schnittmenge; wenn nein: eben nicht. nächstes wort. goto anfang.

................

"Ideally, hyperthreading, which has been under development for four and a half years, will show meatier benefits. An individual could play games while simultaneously downloading multimedia files from the Internet with a computer containing the technology"
- intel.com

Schnittmenge zweier Textdateien

cltom — Thu, 30 Aug 2001 12:28:02 GMT
Welchen Weg würdet ihr gehen, wenn ihr die Schnittmenge von zwei Textdateien erhalten wollt. Beispiel:

Text1: HHH, KKK, LLL, OOO, PPP, SSS
Text2: BBB, MMM, OOO, SSS

Ergebnis: OOO, SSS

Die beiden Texte sind recht umfangreich (der eine 700 Zeilen, der andere 3000 Zeilen). Vielleicht kann man das bei der Lösung beachten.