www.matheraum.de
Das Matheforum.
Das Matheforum des MatheRaum.

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenSchul-Informatik AlgorithmenEffiziente Suche
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Deutsch • Englisch • Französisch • Latein • Spanisch • Russisch • Griechisch
Forum "Schul-Informatik Algorithmen" - Effiziente Suche
Effiziente Suche < Algorithmen < Schule < Informatik < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Schul-Informatik Algorithmen"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Effiziente Suche: Frage (überfällig)
Status: (Frage) überfällig Status 
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 ?

        
Bezug
Effiziente Suche: Rückfrage
Status: (Antwort) fertig Status 
Datum: 16:52 Mo 15.12.2008
Autor: reverend

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?

Bezug
                
Bezug
Effiziente Suche: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 17:10 Mo 15.12.2008
Autor: chil14r

Es soll einmalig die Werte abgleichen und für den gefundenen Index einen String speichern.

Bezug
                        
Bezug
Effiziente Suche: Datengröße?
Status: (Mitteilung) Reaktion unnötig Status 
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...

Bezug
        
Bezug
Effiziente Suche: Rückfragen
Status: (Mitteilung) Reaktion unnötig Status 
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.)


Bezug
                
Bezug
Effiziente Suche: x,y-Paare eindeutig?
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
        
Bezug
Effiziente Suche: Fälligkeit abgelaufen
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 17:20 Mi 17.12.2008
Autor: matux

$MATUXTEXT(ueberfaellige_frage)
Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Schul-Informatik Algorithmen"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheforum.net
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]