Autor Beitrag
DarkHunter
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 477

Win XP
D3 Prof, D2005 PE
BeitragVerfasst: 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
ausblenden Delphi-Quelltext
1:
if s in array then bla					

leider geht das nicht
retnyg
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 2754

SNES, GB, GBA, CPC, A500, 486/66, P4/3.0HT: NintendOS, AmigaOS, DoS
Delphi 5, Delphi 7
BeitragVerfasst: 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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 477

Win XP
D3 Prof, D2005 PE
BeitragVerfasst: So 26.06.05 22:46 
ist aber leider ein unsortiertes 2d-array
retnyg
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 2754

SNES, GB, GBA, CPC, A500, 486/66, P4/3.0HT: NintendOS, AmigaOS, DoS
Delphi 5, Delphi 7
BeitragVerfasst: 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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 477

Win XP
D3 Prof, D2005 PE
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 2754

SNES, GB, GBA, CPC, A500, 486/66, P4/3.0HT: NintendOS, AmigaOS, DoS
Delphi 5, Delphi 7
BeitragVerfasst: 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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 477

Win XP
D3 Prof, D2005 PE
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 2684
Erhaltene Danke: 32



BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 2889
Erhaltene Danke: 13

W2000, XP
D6E, BDS2006A, DevExpress
BeitragVerfasst: 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:
ausblenden 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:
ausblenden 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...:
ausblenden 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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 477

Win XP
D3 Prof, D2005 PE
BeitragVerfasst: Mo 27.06.05 09:40 
user profile icondelfiphan 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 2889
Erhaltene Danke: 13

W2000, XP
D6E, BDS2006A, DevExpress
BeitragVerfasst: 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.