| Autor |
Beitrag |
DarkHunter
      
Beiträge: 477
Win XP
D3 Prof, D2005 PE
|
Verfasst: So 26.06.05 22:24
hallo
gibt es ein möglichkeit zu überprüfen ob ein string in einem 2 dimensioalen array vorhanden ist?
als einen weg der nciht über 2 schleifen führt?
ich dachte zuerst an
Delphi-Quelltext 1:
| if s in array then bla |
leider geht das nicht
|
|
retnyg
      
Beiträge: 2754
SNES, GB, GBA, CPC, A500, 486/66, P4/3.0HT: NintendOS, AmigaOS, DoS
Delphi 5, Delphi 7
|
Verfasst: So 26.06.05 22:45
bei einer stringlist geht das mit indexOf schnell und komfortabel.
bei einem sortierten array kannst du auch schneller zum ziel, indem du immer den zu durchsuchenden bereich halbierst und den ersten buchstaben überprüft.
_________________ es gibt leute, die sind genetisch nicht zum programmieren geschaffen.
in der regel haben diese leute die regel...
|
|
DarkHunter 
      
Beiträge: 477
Win XP
D3 Prof, D2005 PE
|
Verfasst: So 26.06.05 22:46
ist aber leider ein unsortiertes 2d-array
|
|
retnyg
      
Beiträge: 2754
SNES, GB, GBA, CPC, A500, 486/66, P4/3.0HT: NintendOS, AmigaOS, DoS
Delphi 5, Delphi 7
|
Verfasst: So 26.06.05 22:49
musst du also sortieren, bzw eine 2. tabelle mit den sortierten wert und einem index der postition in der ersten "tabelle"
_________________ es gibt leute, die sind genetisch nicht zum programmieren geschaffen.
in der regel haben diese leute die regel...
|
|
DarkHunter 
      
Beiträge: 477
Win XP
D3 Prof, D2005 PE
|
Verfasst: So 26.06.05 22:56
sortieren ist so ein problem
weil ich das array in seiner art nicht verändern will
(dient mir als matrix für eine oberläche)
|
|
retnyg
      
Beiträge: 2754
SNES, GB, GBA, CPC, A500, 486/66, P4/3.0HT: NintendOS, AmigaOS, DoS
Delphi 5, Delphi 7
|
Verfasst: So 26.06.05 22:59
dann brauchst du wie gesagt ne kopie des arrays, zum sortieren.
oder du durchsuchst direkt den ganzen, für das array reservierten speicher. dazu musst du dich aber gut mit pointern auskennen...und schneller ists auch nicht
_________________ es gibt leute, die sind genetisch nicht zum programmieren geschaffen.
in der regel haben diese leute die regel...
|
|
DarkHunter 
      
Beiträge: 477
Win XP
D3 Prof, D2005 PE
|
Verfasst: So 26.06.05 23:04
mit pointer kenn ich mich so gut wie gar nicht aus
ich glaube das läuft doch auf die zu fuss methode aus
|
|
delfiphan
      
Beiträge: 2684
Erhaltene Danke: 32
|
Verfasst: Mo 27.06.05 00:12
Musst du es nach mehreren Wörtern durchsuchen? Oder nur ein mal nach einem Wort?
Statt das Array zu sortieren könntest du eine Hashing-Tabelle aufstellen und anschliessend die Hashing-Tabelle durchsuchen. Nimm z.B. CRC32 (kA ob der für sowas geeignet ist) als Hashing-Funktion.
Vorteil von Hashing-Tabellen: Du kannst mit (beschränkten) Zahlen statt Strings arbeiten. Wenn du CRC16 nimmst, fällt sogar die Suche in der Hashing-Tabelle weg (da nur 16 Bits) und du findest den String in O(1) (= "Gratisoperation"). Das Hinzufügen eines Eintrages in die Hashing-Tabelle erfolgt auch mit O(1).
Nachteil: Möglicherweise gibt's Kollisionen. Es ist also nur eine "grobe" Suche.
|
|
alzaimar
      
Beiträge: 2889
Erhaltene Danke: 13
W2000, XP
D6E, BDS2006A, DevExpress
|
Verfasst: Mo 27.06.05 08:14
Titel: Qui
Sei M dein Stringarray, n die anzahl der Zeilen, m die Anzahl der Zeilen, und M[i,j] der String in Spalte j und Zeile i (i=0..n-1, j=0..m-1), dann erzeugst Du ein Array A [0..m*n-1] of TPoint und füllst es mit den Koordinaten:
Delphi-Quelltext 1: 2: 3:
| For i=0 to n-1 do For j:=0 to m - 1 do A[i*n+j] := Point (i,j) |
Nun sortierst Du das Feld A per Quicksort, wobei die Vergleichsfunktion CompareStrings (i,j) so definiert ist:
Delphi-Quelltext 1: 2: 3: 4:
| Function MyCompareStrings (i,j : Integer) : Integer; Begin Result := CompareStr (M [A[i].x, A[i].y], M[A[j].x, A[j].y]); End; |
Anschliessend kannst Du mit der Binärsuchmethode sehr schnell deine Strings suchen: Wir suchen den String s:
Sei l der linke Rand und r der rechte Rand der Liste (Anfangs: l=0, r=m*n-1). Wir nehmen uns das mittlere Element an der Position m=(l+r)/2.
Sei ms dieses mittlere Element: Wenn s < ms, dann müssen wir in der Teilliste (l,m-1) weitersuchen. Ist s>ms dann müssen wir in der rechten Teilliste weitersuchen...:
Delphi-Quelltext 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21:
| Function BinSearch (Const aString : String) : Boolean; Var m,l,r : Integer;
Begin l := Low (A); r := High (A); While l<r do begin m := (l + r) div 2; Case Sign (CompareStr (M[A[m].x, A[m].y], aString)) of -1 : l := m + 1; 0 : Begin Result := True; Exit; End; +1 : r := m - 1; End; End;
Result := False; End; |
@delphifan: CRC32 ist eine gute Hashfunktion, es gibt aber noch Bessere, z.T. spezielle, den Strings (C? Pascal? Token) Angepasste. Die Hashsuche ist sicherlich die Schnellste, aber nicht so einfach zu implementieren.
|
|
DarkHunter 
      
Beiträge: 477
Win XP
D3 Prof, D2005 PE
|
Verfasst: Mo 27.06.05 09:40
delfiphan hat folgendes geschrieben: | | Musst du es nach mehreren Wörtern durchsuchen? Oder nur ein mal nach einem Wort? |
ich muss das array insgesamt 3 mal nach je einem string durchsuchen
@alzaimar?
geht es da nicht mit 2 verschachtelten For-Schleifen einfacher?
vielleicht ist es ganz interessant das das array ein fest größe 20*10 hat
|
|
alzaimar
      
Beiträge: 2889
Erhaltene Danke: 13
W2000, XP
D6E, BDS2006A, DevExpress
|
Verfasst: Mo 27.06.05 12:53
Das lineare Suchen ist vom Aufwand O(n) wobei n die Listegröße ist. Binäres Suchen ist vom Aufwand O(log(n)), das ist wesentlich effektiver. Wenn Du nur ein paar mal nach Strings suchst und dann nie wieder, ist logischerweise eine lineare Suche einfacher, aber bei sehr grossen Listen oder vielen Wiederholungen ist die Binärsuche besser.
Ich würde mal in der www.delphi-praxis.net (oder wie das heisst) nach meinen Hashlisten suchen. Die sind dann optimal schnell, jedenfalls vom Aufwand O.
|
|
|