Effiziente Suche < Algorithmen < Schule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 16:31 Mo 15.12.2008 | | Autor: | chil14r |
| Aufgabe | Es gibt eine Tabelle mit Wertepaaren (x,y) im Wertebereich x [mm] \in [/mm] 1...1162 y [mm] \in [/mm] 1162.
Gesucht sind die Einträge einer anderen Tabelle in denen auch exakt diese x-y Werte drin stehen mit zusätzlichen Informationen. Die Aufgabe ist also eine paarweise Wertesuche. |
Meine Frage ist : Wie kann ich diese Suche effizient implementieren. Im Moment suche ich erst x und dann y. Dies dauert geschätzte 5 Stunden was eindeutig zulange ist.
Könnte man vielleicht HashTabellen einsetzen ?
|
|
| |
|
Kommt drauf an, was dann passiert, wenn eine Entsprechung zweier Einträge in den beiden Tabellen gefunden ist.
Eine Hashtabelle ist eine gute Idee, aber aufwändig.
Wahrscheinlich gibt es viel einfachere Möglichkeiten, z.B. mit ganz einfachen Indexarrays.
Also: was soll das Programm tun?
Einmalig Listen abgleichen und Daten übernehmen?
Listen sortieren?
Gegenseitig indizieren?
Oder soll es nach Einzelaufruf prüfen, ob zu einem gegebenen Datensatz eine Entsprechung in der anderen Tabelle gibt?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:10 Mo 15.12.2008 | | Autor: | chil14r |
Es soll einmalig die Werte abgleichen und für den gefundenen Index einen String speichern.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:18 Mo 15.12.2008 | | Autor: | reverend |
Na, das klingt doch eigentlich ganz einfach.
Wie groß sind denn die Datenstrukturen, dass bei Dir ein Durchlauf fünf Stunden braucht? Da hätte ich selbst vor 25 Jahren mit den damaligen langsamen Rechnern schon einen ziemlichen Haufen von Daten verarbeitet.
Die Größe hilft auch einzuschätzen, wie effizient die Suche denn sein muss...
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 07:36 Di 16.12.2008 | | Autor: | bazzzty |
Hallo chil14r,
Vielleicht kannst Du noch dazuschreiben, was Du eigentlich genau machst, was fünf Stunden dauert. Auch die Sprache wäre ganz interessant.
Ansonsten hätte ich mehrere Ideen, die alle schneller sein sollten:
a) Du legst ein Bitarray an mit 1162*1162 Bits. Dann gehst Du einmal durch die erste Tabelle und setzt für jeden Eintrag x,y das Bit an der entsprechenden Stelle auf 1. Dann gehst Du durch die andere Tabelle, und Du gibst einen Eintrag x,y,text aus, wenn das Bit an der Stelle x,y gesetzt ist. Das ist keine "elegante" Lösung, aber in der Größenordnung leicht zu realisieren, und vor allem schnell: Das Bitarray ist ein paar hundert Kilobyte groß und schnell initialisiert, danach gehst Du beide Tabellen genau einmal durch. Was die Laufzeit angeht, dürfte das in der Größenordnung unschlagbar sein.
b) Du sortierst die erste Liste oder setzt eine Hashmap (oder ähnliches) ein. Das macht keinen großen Unterschied, ist in C++ oder Java auch alles schon "an Bord". Einfacher ist sicher die Hashmap, weil da auch die Suche schon vorhanden ist (beim Sortieren mußt Du Dir um den Abgleich Gedanken machen). Du nimmst also eine Hashmap, wirfst alle Elemente der ersten Liste hinein und während Du die zweite Liste durchgehst, schaust Du jeweils nach, ob die x-y-Kombination Element in der Hashmap ist. Die Hashfunktion mußt Du allerdings anpassen, z.B. auf x*1162+y (die muß nicht clever sein, nur eindeutig, den Rest macht die HashMap).
Sieht vielleicht netter aus, ist aber sicher um Längen langsamer (wenn auch sicher keine 5 Stunden.)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 10:36 Di 16.12.2008 | | Autor: | reverend |
Noch 'ne Frage anlässlich bazzztys Antwortteil a):
Taucht jedes (x,y)-Tupel höchstens einmal auf?
Wenn es z.B. drei Einträge zu (417;991) gibt (und in der anderen Liste dann genausoviele? oder unbestimmt?), brauchst Du eine andere Suchmethode, als bei höchstens einmaligen Einträgen ((471;991) steht drin oder nicht), und auch die Frage, ob die Listen genau gleich groß sind und genau die gleichen Einträge, eben verknüpft mit anderen Datenfeldern, wird einen Einfluss darauf haben.
Gib doch also bitte Deine Rahmenbedingungen möglichst genau an, wenn Du hier wieder vorbeikommst.
Danke im voraus,
rev
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:20 Mi 17.12.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
