AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren

Zusätzliches WOrt in Hashtabelle einfügen?

Ein Thema von schöni · begonnen am 17. Mai 2012 · letzter Beitrag vom 20. Mai 2012
Antwort Antwort
Seite 2 von 2     12
shmia

Registriert seit: 2. Mär 2004
5.508 Beiträge
 
Delphi 5 Professional
 
#11

AW: Zusätzliches WOrt in Hashtabelle einfügen?

  Alt 20. Mai 2012, 05:43
Bei zu hohem Füllungsgrad der Hashtabelle wird die Suche aber langsam.
Da bin ich aber ganz anderer Meinung (oder beziehst Du dich auf diese konkrete Implementierung?):
Hashtabellen (nicht gerade diese) sind in Puncto Performance bei großen Datenmengen nicht zu schlagen. Die Performance für das Einfügen, Suchen und Löschen ist stehts O(1), sofern eine dynamische Variante genutzt wird.
Die Standardimplementierung einer Hash-Tabelle sieht so aus, dass es eine bestimmte Anzahl an Buckets (Einträge in einem Array) gibt.
Die Hashfunktion bildet den Schlüssel auf den Index im Array ab.
Sollte ein Bucket aber schon belegt sein, dann nimmt man den nächsten freien Eintrag. ("Linear Probing")
Bei zu hohem Füllungsgrad; also das Array ist schon zu 80% voll; wird immer seltener ein freies Bucket gefunden.
Es bilden sich ganze Ketten von belegten Buckets, die das Suchen und Eintragen von Schlüsseln verlangsamen.
Bei 100% Belegung müssen für die Suche nach einem nichtvorhandenen Schlüssel ALLE Buckets durchsucht werden.
Natürlich kann man Hashtabellen auch anderst strukturieren, z.B. als Array of TList und damit einige dieser Nachteile vermeiden.


Ansonsten ist nach meinen Messung die lineare Suche bei diesem Beispiel schneller!
Delphi-Quellcode:
for i := 1 to 1000000 do
begin
   IsReserved('test'); // Miss
   IsReserved('string'); // Hit
end;
Die Hashtabelle aus Beitrag #1 benötigt ~ 1,32 Sekunden,
die lineare Suche braucht ~ 1,02 Sekunden.

Wer selbst messen möchte:
Delphi-Quellcode:
function IsReservedLinSearch(S:string):Boolean;
const list : array[0..87] of string =
(
'CONST','OR','TYPE',
'SHL','FOR','DESTRUCTOR','INHERITED','PROPERTY',
'TO','OBJECT','TRY','CDECL',
'VAR','ASSEMBLER',
'AND','FORWARD','THEN','IMPLEMENTATION','LIBRARY','RAISE',
'IF','UNTIL','PUBLISHED','STORED',
'SET','CLASS','INITIALIZATION','THREADVAR',
'LABEL','PROGRAM','SHR','FINALIZATION','NODEFAULT',
'CASE','END','DISPID','INDEX','RESIDENT',
'ABSOLUTE','WHILE','DO','AUTOMATED',
'RECORD','PACKED','INLINE','PUBLIC','PRIVATE','AS','FAR','OVERRIDE', //50
'OF','STRING','NOT','DEFAULT','DYNAMIC','MESSAGE',
'FILE','REPEAT','BEGIN',
'IN','EXTERNAL','INTERFACE','EXPORTS','NAME','STDCALL',
'GOTO','PROCEDURE',
'DOWNTO','ARRAY','PROTECTED',
'FUNCTION',
'MOD','WITH',
'IS','NEAR',
'XOR','CONSTRUCTOR',
'DIV','NIL','EXCEPT',
'ELSE','UNIT','USES','FINALLY','ABSTRACT',
'EXPORT','PASCAL','VIRTUAL'
);
var
  i : Integer;
begin
   S := Uppercase(S);
   for i := low(List) to High(List) do
   begin
      if S = list[i] then
      begin
         Result := True;
         Exit;
      end;
   end;
   Result := False;
end;
Andreas
  Mit Zitat antworten Zitat
Furtbichler
(Gast)

n/a Beiträge
 
#12

AW: Zusätzliches WOrt in Hashtabelle einfügen?

  Alt 20. Mai 2012, 08:32
[QUOTE=shmia;1167302]
Die Standardimplementierung einer Hash-Tabelle sieht so aus, .."Linear Probing"...
Ich sprach aber von einer brauchbaren Hashmap, also z.B. "chaining" und dynamisch.
Hashtabellen (nicht gerade diese) sind in puncto Performance bei großen Datenmengen nicht zu schlagen. ... sofern eine dynamische Variante genutzt wird.
Zitat:
Ansonsten ist nach meinen Messung die lineare Suche bei diesem Beispiel schneller!
Für mich ist der Test nicht aussagekräftig, da er zu wenig Fälle betrachtet. Versuch diesen:
Delphi-Quellcode:
for i := 1 to 1000000 do
  for j := 0 to allReservedWordsCount-1 do
    IsReserved(reservedWords[j]);
Er sucht nach allen reservierten Wörtern. Wir können noch ein paar Wörter hinzupacken, die nicht gefunden werden sollen, wenn Du magst. Oder Du schlägst einen anderen Test vor.
Dein Test zeigt aber sehr deutlich, das lineare Suche bei kleinen Listen nicht zu topppen ist. Eine Liste mit 88 Elemente ist hier aber nicht mehr "klein".

Der Test mit folgender Klasse führt bei mir zu erheblichen Geschwindigkeitszuwächsen und hält sich bezüglich Speicherauslastung in Grenzen:
Delphi-Quellcode:
Unit pascalKeywordList;
Interface
Type
  TKeywordBucket = Record
    data: Array[0..10] Of String;
    dataCount: Integer;
  End;
  // A generic chaining hash map using the first character as hash function.
  TKeywordListHash = Array[Char] Of TKeywordBucket;

  TPascalKeywordList = Class
  private
    keywords: TKeywordListHash;
    Procedure FillList;
  public
    Constructor Create;
    Function IsReserved(Const aWord: String): Boolean;
  End;

Implementation
Const
  keywordCount = 88;
  keywordList: Array[0..keyWordCount - 1] Of String = (
    'CONST', 'OR', 'TYPE', 'SHL', 'FOR', 'DESTRUCTOR', 'INHERITED', 'PROPERTY',
    'TO', 'OBJECT', 'TRY', 'CDECL', 'VAR', 'ASSEMBLER', 'AND', 'FORWARD', 'THEN',
    'IMPLEMENTATION', 'LIBRARY', 'RAISE', 'IF', 'UNTIL', 'PUBLISHED', 'STORED',
    'SET', 'CLASS', 'INITIALIZATION', 'THREADVAR', 'LABEL', 'PROGRAM', 'SHR',
    'FINALIZATION', 'NODEFAULT', 'CASE', 'END', 'DISPID', 'INDEX', 'RESIDENT',
    'ABSOLUTE', 'WHILE', 'DO', 'AUTOMATED', 'RECORD', 'PACKED', 'INLINE', 'PUBLIC',
    'PRIVATE', 'AS', 'FAR', 'OVERRIDE', 'OF', 'STRING', 'NOT', 'DEFAULT', 'DYNAMIC',
    'MESSAGE', 'FILE', 'REPEAT', 'BEGIN', 'IN', 'EXTERNAL', 'INTERFACE', 'EXPORTS',
    'NAME', 'STDCALL', 'GOTO', 'PROCEDURE', 'DOWNTO', 'ARRAY', 'PROTECTED', 'FUNCTION',
    'MOD', 'WITH', 'IS', 'NEAR', 'XOR', 'CONSTRUCTOR', 'DIV', 'NIL', 'EXCEPT',
    'ELSE', 'UNIT', 'USES', 'FINALLY', 'ABSTRACT', 'EXPORT', 'PASCAL', 'VIRTUAL');

{ TPascalKeywordList }

Constructor TPascalKeywordList.Create;
Begin
  FillList;
End;

Procedure TPascalKeywordList.FillList;
Var
  i: Integer;

  Procedure _FillIntoList(Const keyWord: String);
  Begin
    Assert(Length(keyWord) > 1, 'the keyword to be filled in may not be empty');
    With keywords[keyword[1]] Do Begin
      data[dataCount] := keyWord;
      inc(dataCount);
    End
  End;

Begin
  For I := 0 To keywordCount - 1 Do _FillIntoList(keyWordList[i]);
End;

Function TPascalKeywordList.IsReserved(Const aWord: String): Boolean;
Var
  i: Integer;

Begin
   Assert(Length(aWord) > 1, 'the word to be searched may not be empty');
   With keywords[aWord[1]] Do
    For I := 0 To dataCount - 1 Do
      If data[i] = aWord Then Begin
        result := true;
        exit;
      End;
  result := false;
End;

End.
  Mit Zitat antworten Zitat
Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 10:12 Uhr.
Powered by vBulletin® Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2021 by Daniel R. Wolf