Autor Beitrag
Kunstbanause
Hält's aus hier
Beiträge: 1



BeitragVerfasst: Fr 18.02.05 11:59 
wulfskin hat folgendes geschrieben:
UC-Chewie hat folgendes geschrieben:
Zur Info: Das ganze nennt man binäre Suche und die Anzahl der Zugriffe beträgt max. floor(ld(n)), wobei floor() aufrundet und ld() der Logarithmus zur Basis 2 ist.
Bei 2.000 Einträgen brauchst du also maximal 11 Zugriffe.
Danke schön,

das geht jetzt wirklich richtig schnell! 8) Für alle die es interessiert, hier mein Quelltext:
ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
function TW3gItemList.GetItemById(const AId: TItemId): TW3gItem;
  function FindInList(const AStart, AEnd: Integer; const AId: TItemId): TW3gItem;
  var
    I: Integer;
  begin
    Result := nil;
    if CompareText(Items[AStart].Id, AId) = 0 then
      Result := Items[AStart]
    else
    if CompareText(Items[AEnd].Id, AId) = 0 then
      Result := Items[AEnd]
    else begin
      if  (AStart <> AEnd)
      and ((AEnd - AStart) > 1then begin
        I := (AStart + AEnd) div 2;
        if AId > Items[I].Id then
          Result := FindInList(I, AEnd, AId)
        else
          Result := FindInList(AStart, I, AId);
      end
      else
        {Abbrechen};
    end;
  end;
  
begin
  Result := nil;
  if Count > 0 then
    Result := FindInList(0, Count - 1, AId);
end;
Jetzt muss ich nur noch schauen, wie ich ein Item schnell einfügen kann ohne die Liste jedesmal neu sortieren zu müssen.

Gruß Hape!

Es geht auch ohne Rekursion:
ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
function GetIndex(Wert: String[4]; Liste: array of String): Integer;
var
   i, mi, le, ri  : Integer;
begin
   le := Start;
   ri := Ende;
   repeat
      mi    := (le+ri) div 2;
      if Wert<Liste[mi] then
         ri := mi - 1
      else
         le := mi + 1;           
   until (Wert=Liste[mi])or(le>ri);
   if Wert=Liste[mi] then
      Result   := mi
   else
      Result   := -1;
end;
Spaceguide
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 552


(D3/D7/D8) Prof.
BeitragVerfasst: Fr 18.02.05 14:14 
Also bei 2000 Elementen lohnt sich ein(e) HashTable schon. Bei guter Hashfunktion und geeigneter Hashgröße kommt man auf unter 1.2 Kollisionen/(gefüllte Zelle). Mit Halbierungsverfahren bräuchte man immer noch Log2(2000) ~ 11 Schritte.
UC-Chewie
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 531

WinXP
D5 Ent
BeitragVerfasst: Fr 18.02.05 17:10 
Spaceguide hat folgendes geschrieben:
Also bei 2000 Elementen lohnt sich ein(e) HashTable schon. Bei guter Hashfunktion...(gefüllte Zelle).


Und das ist oft das Problem: Eine gute Hashfunktion zu finden. Eine Hashfunktion muss auf dein Problem zugeschnitten sein, um Kollisionen zu minimieren. Das ist nicht gerade triviale Mathamtik.

_________________
Egal wie dumm man selbst ist, es gibt immer andere, die noch dümmer sind
wulfskin Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 1349
Erhaltene Danke: 1

Win XP
D5 Pers (SSL), D2005 Pro, C, C#
BeitragVerfasst: Fr 18.02.05 17:22 
Vor allem, so denke ich zumindest, geht durch die Erstellung des Hashes gewisse Zeit verloren, die bei so einer geringen Menge ins Gewicht fällt.

Danke für Eure Hilfe. Im Endeffekt war die StringListe etwas schneller, warscheinlich weil die explizite Form schneller ist als meine Rekursive.

GRuß Hape!

_________________
Manche antworten um ihren Beitragszähler zu erhöhen, andere um zu Helfen.
Spaceguide
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 552


(D3/D7/D8) Prof.
BeitragVerfasst: So 20.02.05 18:30 
Apropos Hashfunktion: Ist es eigentlich garantiert, dass ein (Ansi)String ein #0 am Ende hat?
UC-Chewie
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 531

WinXP
D5 Ent
BeitragVerfasst: So 20.02.05 18:31 
Wenn er nicht mittels Zeigerarithmetik manipuliert wurde: Ja.

_________________
Egal wie dumm man selbst ist, es gibt immer andere, die noch dümmer sind