Wie Nachschlagetabelle implementieren

[Guest]

Guten Abend zusammen,

ich stehe gerade vor folgender Problemstellung. Ich muss verschiedene Tabellen im Speicher abbilden. Okay soweit, so gut. Ich versuche ma es an einem Beispiel zu erklären:

Gegegeben ist eine Tabelle mit 4 Spalten und 100 Zeilen. Diese Tabelle muss leider fest codiert werden. Die Kombination aus den 3 der 4 Spalten lässt eine eindeutige Indentifikation des 4. nachzuschlagenden Wertes zu.

Beispieltabelle

A|B|D|E
1|1|1|0
1|0|1|0
0|0|1|5

Wenn ich jetzt den Wert "5" suche (letzte Spalte), sind mir zuvor die Spaltendaten (A-C) hier 0,0,1 gegegeben.

Nun meine Frage, wie kann ich

a) die Tabelle effiktiv abbilden
b) letztendlich nach einem Wert suchen

Vielleicht hat ja jemand ein paar Sichtwörter für mich, die mich weiterbringen.

Vorab schonmal vielen Dank!

Gruß

Sebastian

 

[Gast]

Da seh ich den Wald vor lauter Bäumen nicht!

Wie wäre es mit einem Binären Baum, wenn in den Spalten A-C nur 0 und 1 stehen. bzw. einem anderen Baum. wenn die Werte anders sind.

Also vorausgesetzt du willst folgendes du gibst eine dreistellige Zahl ein z.B 0,0,1 und willst als Ergebnis die 5 bekommen.

 

[Guest]

Danke für die schnelle Antwort.

Ich glaube ein Baum würde nicht funktionieren, da

1.) die Tabelle hier nur beispielhaft (ich weiß, war wohl nen schlechtes Beispiel) angebildet ist, und auch Strings speichern können muss
2.) Ich vor der Erzeugung der Klasse noch nicht weiß, ob die ich über die Spalten A-C den Wert D identifizieren muss, oder über die Spalten B-D den Wert A usw. usw.

Gruß

Sebastian

 

[Hilefoks]

Klingt irgendwie so als wenn man das wie eine Shannon-Fano Kodierung betrachten könnte... aber ich verstehe dein Problem nicht wirklich - wer also gut wenn du dein Problem (speziell deine Tabelle) etwas genauer beschreiben könntest.

MfG,
Hilefoks

 

[SlaterB]

ein ganz allgemeines aber auch langsames Vorgehen:
die drei Index-String zu einem zusammenfügen (evtl. mit Unique-Trennzeichen) und in einer Map auf das 4. Element mappen

wenn Strings als Keys im Spiel sind, wird man auch nicht entscheind mehr machen können,
falls die Menge der Keys auf einen bestimmten Bereich begrenzt ist, kann man evtl. Teilkeys anderen Werten zuordnen, die besser zu verarbeiten sind,

es ist auch eine Frage, woher die Suchanfragen kommen, ob ein User die ganz frisch eintippt oder die im Laufe eines Algorithmusses auftauchen,
wo auch wieder vielleicht die Möglichkeit besteht, andere Keys zu verwenden

 

[Guest]

@Hilefoks

Die Tabelle bildet eine Art Entscheidungsmatrix ab. Vereinfacht könnte man die Problematik vielleicht so beschreiben.
Du hast vier Werte (je Zeile), brauchst aber nur drei um die gesuchte Zeile zu identifizieren. Oder anders ausgedrückt:

Du bekommst vier Werte (deren Einordnung zur Spalte bekannt ist). Dann durchsuchst du alle Zeilen und prüfst, ob in der aktuell durchsuchten Spalte der gesuchte Wert vorhanden ist. Alle Zeilen, die den gesuchten Wert nicht enthalten können aus der zu durchsuchenden Listen gelöscht werden. Das selbe machst du dann mit der 2. Spalte und so veringert sich die zu durchsuchende Menge immer weiter, bis nur noch genau ein Wert in der Menge vorhanden ist. Das ist dann der Treffer / bzw. gesuchte Wert.

Wäre es nicht schön einfach wenn die Tabelle in einer DB abgebildet wäre? Geht aber leider leider nicht. :?

@SlaterB

Die "Suchanfragen setzen sich zur Laufzeit aus User-Angaben zusammen. Ich weiss also vor der User-Eingabe nicht welche Spalte den zu suchenden Wert enthält, bzw. aus welchen 3 Spalten sich der 4 Wert indentifzieren lässt.
Wie soll ich drei Strings zu einem Indexstring zusammenfügen, wenn ich noch nicht weiss aus welchen drei String sich der Index ergibt?

Hat jemand eine weitere Idee :?:

 

[SlaterB]

nun mal halblang, bleiben wir bei deinen Beispiel
A|B|D|E
1|1|1|0
1|0|1|0
0|0|1|5

wenn nun A =1, D = 1 und E = 0 gegeben sind, welche B ist dann gesucht, 0 oder 1?
oder ist das nur eine schlechte Beispieltabelle?
sind 3 Werte immer eindeutig?

und vor allem: weißt du die Spalten zu jedem Wert oder hast
du in beliebiger Reihenfolg drei lose Index-Werte gegeben?

sind denn die Wertebereiche jeder Spalte unterschiedlich oder gibts da Überlappungen?


na egal wie es ist, du brauchst dann jedenfalls eine Map, die von allen möglichen Key-Kombinationen auf den fehlenden Wert mappt,
bei Reihenfolge der Keys ist das recht einfach

key1#key2#key3# -> Wert 4
oder auch
key1##key3#key4 -> Wert 2

wenn die Spalten zu den Werten nicht gegeben sind, dann müssen sie ja eigentlich alle eindeutig sind,
dann sortierst du die Keys alphabetisch und hast so aus 3 Werten immer genau einen Key für die Map

--------

für n Zeilen und 4 Spalten hast du eine Map der Größe 4n,
das geht ja noch

 

[Guest]

@SlaterB

ja die Tabelle ist schlecht!
3 Werte sind immer eindeutig!

ja, ich kenne die Spalten zu jedem Wert.

Die Werte-Bereiche der verschiedenen Spalten sind überlappend.

Ich glaub ich werd um eine komplexe Map nicht herumkommen.

Danke für die Antworten! Tolles Forum!

Ich wünsche noch einen schönen Abend!

Ps. kann die Diskussion leider nicht schließen da ich nicht registriert bin, vielleicht kanns ja jemand für mich machen.

 

[SlaterB]

denkbar wäre noch, wie die DB mehrere einzelne Indexe zu führen und deren Ergebnisse zu vergleichen,
macht die Keys kürzer, dürfte also Platz sparen und man muss auch nicht ständig Keys zusammenbauen,

was schneller ist steht noch aus,
bei Benutzereingaben ist aber Performance wohl egal, solange man nicht die Liste Element für Element durchlaufen muss