String-Interpolationssuche?

[bröggle]

Hi,
*hust* (ich muss erstmal den staub von meinem account entfernen)

und zwar habe ich das problem, dass ich einen algo für die interpolierte Suche erstellen soll.
Soweit kein problem (im inet gibt es ja genügend Beispiele für die interpolierte Suche für Zahlen), aber ich 'muss'/möchte nach einem String suchen.

d.h. einen String aus einem Stringarray raussuchen.

->Problem dabei die neuen teilbereiche zu berechnen.

so wie hier: http://de.wikipedia.org/wiki/Interpolationssuche geht es eben nicht (ich kann ja nicht mit 'foo' malnehmen)


Meine Fragen also:
Geht eine Interpolierte Suche überhaupt mit Strings (muss eigentlich)
2.Wenn ja wie, bzw hat jemand ein Beispiel?bzw kann mir jemand erklären wie ich die neuen teilbereiche rausbekomme?
Denn sowas wie indexOf werde ich ja wohl nicht nehmen dürfen


Danke schonmal
^-^

 

[stev.glasow]

Und wenn du den hashcode des Strings nimmst?

 

[bröggle]

Und wenn du den hashcode des Strings nimmst?

hmm, habe ich mir auchs chon überlegt,
aber ist der hashcode von abc auch wirklich kleiner als der von zz?

 

[stev.glasow]

Ne größer weil abc mehr Zeichen hat. Auf'n Schlag wüsste ich aber auch nix anderes ???:L

 

[bröggle]

hmm, könnte man dann nicht
den sting mit vielen Z (letztes in sortierung) füllen, sodass zumindest die Stellen zahl gleich wäre?

ZZZZabc <
ZZZZZzz

würde ja wieder stimmen.
aber welche hashfunktion kann das so machen?
bzw welche liefert eine entsprechende Zahl zurück

 

[stev.glasow]

hab doch was zusammen gefriemelt bekommen, hab den Code von Wikipedia etwas angepasst:

public static int interpolierteSuche(String schlüssel, String daten[])
	 {
	   int links = 0;                  // linke Teilfeldbegrenzung 
	   int rechts = daten.length - 1;  // rechte Teilfeldbegrenzung
	   int versch;                     // Anzahl verschiedener Elemente
	   int pos;                        // aktuelle Teilungsposition

	   // solange der Schlüssel im Bereich liegt (andernfalls ist das gesuchte 
	   // Element nicht vorhanden)
	   while( schlüssel.compareTo(daten[links]) >= 0 && schlüssel.compareTo(daten[rechts]) <= 0 ){
	     // Aktualisierung der Anzahl der verschiedenen Elemente
	     versch = daten[rechts].compareTo(daten[links]);
	        
	     // Berechnung der neuen interpolierten Teilungsposition 
	     pos = links + (int)(((double)rechts - links) * (schlüssel.compareTo(daten[links]))
	           / versch);
	     
	     if( schlüssel.compareTo(daten[pos]) > 0)             // rechtes Teilintervall 
	       links = pos + 1;                       // daten[pos] bereits überprüft
	     else if( schlüssel.compareTo(daten[pos])  < 0 )       // linkes Teilintervall
	       rechts = pos - 1;                      // daten[pos] bereits überprüft
	     else                                     // Element gefunden
	       return pos;                            // Position zurückgeben
	   }
	        
	   return -1;                                 // Element nicht gefunden
	 }

 

[stev.glasow]

Scheiße geht doch nicht, nur wenn die Strings nur aus Zahlen bestehen, was dir ja gar nix bringt.
[edit] Und dann auch nicht richtig, den Code kannst du in die Tonne kloppen.

 

[bröggle]

hehe, trotzdem danke für deine mühe;-)

Die Hashcode-Methode ist ansich eine ganz gute Ideejeoch funktioniert das nur bis zu einer bestimmten stringlänge... z.b. bei 10Stellen gibt es - Zahlen und das ganze hat sich erledigt:

CCCCCCCCCD 997603809

DDDDDDDDDE 1653533313

EEEEEEEEEF -1985504479

FFFFFFFFFG -1329574975

GGGGGGGGGH -673645471

 

[stev.glasow]

Du mein Code oben geht doch, hatte im Test einen Fehler, hatte einen Array übergeben der nicht sortiert war.

 

[bröggle]

Du mein Code oben geht doch, hatte im Test einen Fehler, hatte einen Array übergeben der nicht sortiert war.

Aber nur für Zahlenstrings oder?

 

[stev.glasow]

ne für alle

 

[stev.glasow]

ich hab einfach die a - b durch a.compareTo(b) ersetzt und die a >= b durch a.compareTo(b) >= 0 usw.
Klar was das soll?

 

[bröggle]

hmm, müsste ich ja fast mal ausprobieren ;-)

tja ansich einfach ;-)(hoffe ich)

 

[bröggle]

juhuhuhuhu geht!


;-)
eigentlich wars ganz logisch, aber da fehlts mir noch ein wenig an erfahrung ;-)

Naja vielleicht wirds ja dann im Studium besser


Danke


p.s.: wünscht mir glück für den 28.4, 2.5 und 12.5 (ABI)

 

[stev.glasow]

p.s.: wünscht mir glück für den 28.4, 2.5 und 12.5 (ABI)

nö

 

[ohNein]

hab doch was zusammen gefriemelt bekommen, hab den Code von Wikipedia etwas angepasst:

public static int interpolierteSuche(String schlüssel, String daten[])
	 {
	   int links = 0;                  // linke Teilfeldbegrenzung 
	   int rechts = daten.length - 1;  // rechte Teilfeldbegrenzung
	   int versch;                     // Anzahl verschiedener Elemente
	   int pos;                        // aktuelle Teilungsposition

	   // solange der Schlüssel im Bereich liegt (andernfalls ist das gesuchte 
	   // Element nicht vorhanden)
	   while( schlüssel.compareTo(daten[links]) >= 0 && schlüssel.compareTo(daten[rechts]) <= 0 ){
	     // Aktualisierung der Anzahl der verschiedenen Elemente
	     versch = daten[rechts].compareTo(daten[links]);
	        
	     // Berechnung der neuen interpolierten Teilungsposition 
	     pos = links + (int)(((double)rechts - links) * (schlüssel.compareTo(daten[links]))
	           / versch);
	     
	     if( schlüssel.compareTo(daten[pos]) > 0)             // rechtes Teilintervall 
	       links = pos + 1;                       // daten[pos] bereits überprüft
	     else if( schlüssel.compareTo(daten[pos])  < 0 )       // linkes Teilintervall
	       rechts = pos - 1;                      // daten[pos] bereits überprüft
	     else                                     // Element gefunden
	       return pos;                            // Position zurückgeben
	   }
	        
	   return -1;                                 // Element nicht gefunden
	 }

Nur das die ganze Sache nicht das hält was es verspricht.
Es soll ja eine günstige position für das suchen gefunden werden.
CompareTo liefert aber nur -1,0,1 und bringt somit nicht viel bei der Berechnung der Position

 

[GilbertGrape]

Das is doch schon 3 Jahre alt...