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 1 von 2  1 2   
schöni

Registriert seit: 23. Jan 2005
Ort: Dresden
445 Beiträge
 
Delphi 7 Personal
 
#1

Zusätzliches WOrt in Hashtabelle einfügen?

  Alt 17. Mai 2012, 19:44
Hallo,

in diesem Quelltext gibt es eine Hashtabelle mit den in Pascal reservierten Wörtern. Allerdings fehlt das Wort "ASM". An welcher Stelle muss ich das einfügen, damit der hier verwendete Algo das eigefügte Wort auch findet und ohne die bisherige Wortfolge für den verwendeten Algo unbrauchbar zu machen.

Hier ist die Quelle:

Delphi-Quellcode:
unit Reserved {word or directive identificator };
{ Under GNU License            }
{ JOAO PAULO SCHWARZ SCHULER }
{ http://www.schulers.com      }
{ Turbo Pascal Source          }
{ Free Pascal Source for DOS   }
{ Free Pascal Source for Linux }
{ Delphi Source                }


interface

Const HashingNumber = 23;
      MaxOnHashLine = 10;

type STR20 = string[20];

Const RWords : array[0..HashingNumber-1,0..MaxOnHashLine-1] of str20 =
(
{00}  ('CONST','OR','TYPE','','','','','','',''),
{01}  ('SHL','FOR','DESTRUCTOR','INHERITED','PROPERTY','','','','',''),
{02}  ('TO','OBJECT','TRY','CDECL','','','','','',''),
{03}  ('VAR','ASSEMBLER','','','','','','','',''),
{04}  ('AND','FORWARD','THEN','IMPLEMENTATION','LIBRARY','RAISE','','','',''),
{05}  ('IF','UNTIL','PUBLISHED','STORED','','','','','',''),
{06}  ('SET','CLASS','INITIALIZATION','THREADVAR','','','','','',''),
{07}  ('LABEL','PROGRAM','SHR','FINALIZATION','NODEFAULT','','','','',''),
{08}  ('CASE','END','DISPID','INDEX','RESIDENT','','','','',''),
{09}  ('ABSOLUTE','WHILE','DO','AUTOMATED','','','','','',''),
{10}  ('RECORD','PACKED','INLINE','PUBLIC','PRIVATE','AS','FAR','OVERRIDE','',''),
{11}  ('OF','STRING','NOT','DEFAULT','DYNAMIC','MESSAGE','','','',''),
{12}  ('FILE','REPEAT','BEGIN','','','','','','',''),
{13}  ('IN','EXTERNAL','INTERFACE','EXPORTS','NAME','STDCALL','','','',''),
{14}  ('GOTO','PROCEDURE','','','','','','','',''),
{15}  ('DOWNTO','ARRAY','PROTECTED','','','','','','',''),
{16}  ('FUNCTION','','','','','','','','',''),
{17}  ('MOD','WITH','','','','','','','',''),
{18}  ('IS','NEAR','','','','','','','',''),
{19}  ('XOR','CONSTRUCTOR','','','','','','','',''),
{20}  ('DIV','NIL','EXCEPT','','','','','','',''),
{21}  ('ELSE','UNIT','USES','FINALLY','ABSTRACT','','','','',''),
{22}  ('EXPORT','PASCAL','VIRTUAL','','','','','','',''));

function Key(S:string;Divisor:byte):word;
{calculates de hashing code}
{ calcula chave de acesso }

function GetHash(S:String):word;

function IsReserved(S:string):boolean;
{ checks if S is a Reserved word or a directive}


implementation

function Key(S:string;Divisor:byte):word;
{ calcula chave de acesso }
var I:integer;
    SOMA:longint;
begin
SOMA:=0;
for I:=1 to length(S) do
    inc(SOMA,ord(S[I]));
Key:=SOMA mod Divisor;
end;

function GetHash(S:String):word;
begin
GetHash:=Key(S,HashingNumber);
end;

function IsReserved(S:string):boolean;
{ checks if S is a Reserved word or a directive}
var HN,L:word;
    C:word;
    Found:boolean;
begin
L:=Length(S);
for C:=1 to L
    do S[C]:=UpCase(S[C]);

HN:=GetHash(S);
C:=0;
Found:=false;
while (C<MaxOnHashLine) and (RWORDS[HN,C]<>'') and not(Found) do
      begin
      Found:=Found or (S=RWORDS[HN,C]);
      inc(C);
      end;
IsReserved:=Found;
end;


end. {of unit}
Aus dem Quellcode werde ich da nicht schlau. Wo gibt es Literatur zu diesem Thema, aber bitte praxisnah.

Oder ist die Einfügestelle völlig egal. Key berechnet dann einen Hashwert, abhängig von der Einfügestelle und dem Wort.

Allerdings kann ich mir nicht wirklich vostellen, das der Einfügeort echt egal ist. Eher glaube ich das die beherigen Pascal Wörter algo-bedingt an ebendiesen Stellen stehen müssen.

Wer kann hier Licht ins Dunkel bringen?

Ich möchte gerne das fehlende Wort 'ASM' ergänzen und wenn ich später noch andere fehlende Wörter finden sollte, diese auch ergänzen.

Die Konstante RWords enthält die Hash-Tabelle.

.
Damit der Topf nicht explodiert, lässt man es ab und zu mal zischen.

Geändert von schöni (17. Mai 2012 um 19:46 Uhr)
  Mit Zitat antworten Zitat
Namenloser

Registriert seit: 7. Jun 2006
Ort: Karlsruhe
3.724 Beiträge
 
FreePascal / Lazarus
 
#2

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

  Alt 17. Mai 2012, 21:37
Den Index der Zeile, in der ein Wort stehen muss, gibt GetHash(Wort) an.

GetHash('ASM') ergibt 18. Also muss 'ASM' in die Zeile {18} eingefügt werden, und zwar so, dass das erste '' ersetzt wird:
{18}  ('IS','NEAR','ASM','','','','','','',''),
  Mit Zitat antworten Zitat
schöni

Registriert seit: 23. Jan 2005
Ort: Dresden
445 Beiträge
 
Delphi 7 Personal
 
#3

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

  Alt 18. Mai 2012, 12:12
Danke wie verrückt. So füge ich also ein neues Wort ein, indem ich den Hash Wert mit GetHash() ermittle und dann einen Index (hier 18) in die Tabelle erhalte. Dann füge ich das neue Wort da ein, wo das erste '' ist. Verstanden. Von da ais sind es nicht allzu viele Wörter in der Tabellenzeile, dürfte also dann schnell gefunden sein.
Damit der Topf nicht explodiert, lässt man es ab und zu mal zischen.
  Mit Zitat antworten Zitat
shmia

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

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

  Alt 18. Mai 2012, 17:08
Wahrscheinlich wäre eine lineare Suche bei der geringen Anzahl an Schlüsseln nicht langsamer als diese Hashtabelle.
Ausserdem wird enthält das Array RWords jede Menge Luft (23*10*(20+1) = 4830 Bytes); die lineare Suche bräuchte nicht mal ein Viertel davon.
Andreas
  Mit Zitat antworten Zitat
schöni

Registriert seit: 23. Jan 2005
Ort: Dresden
445 Beiträge
 
Delphi 7 Personal
 
#5

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

  Alt 18. Mai 2012, 22:14
Wahrscheinlich wäre eine lineare Suche bei der geringen Anzahl an Schlüsseln nicht langsamer als diese Hashtabelle.
Ausserdem wird enthält das Array RWords jede Menge Luft (23*10*(20+1) = 4830 Bytes); die lineare Suche bräuchte nicht mal ein Viertel davon.
Interessanter Gedanke. Ok, ich werde beides probieren. Schaun mer mal.
Damit der Topf nicht explodiert, lässt man es ab und zu mal zischen.
  Mit Zitat antworten Zitat
Christian Seehase
(Co-Admin)

Registriert seit: 29. Mai 2002
Ort: Hamburg
11.262 Beiträge
 
Delphi 2006 Professional
 
#6

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

  Alt 19. Mai 2012, 01:48
Wahrscheinlich wäre eine lineare Suche bei der geringen Anzahl an Schlüsseln nicht langsamer als diese Hashtabelle.
Ausserdem wird enthält das Array RWords jede Menge Luft (23*10*(20+1) = 4830 Bytes); die lineare Suche bräuchte nicht mal ein Viertel davon.
Von der binären Suche in einer sortierten StringListe mal ganz zu schweigen
Ich hab's mal ausprobiert: Fast dreimal so schnell, wie die Lösung mit Hashtable.
Tschüss Chris
Die drei Feinde des Programmierers: Sonne, Frischluft und dieses unerträgliche Gebrüll der Vögel.
Der Klügere gibt solange nach bis er der Dumme ist
  Mit Zitat antworten Zitat
shmia

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

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

  Alt 19. Mai 2012, 06:30
Ich denke es hängt auch davon ab, ob die Menge an Schlüsseln sich nie verändert oder ob zur Laufzeit Schlüssel hinzugefügt oder entfernt werden sollen.

a.) feste Menge an Schlüsseln
-> binäre Suche, Interpolationssuche oder quadratische Binärsuche liefert das beste Ergebnis

b.) zur Laufzeit wird eine begrenzte Menge an Schlüsseln hinzugefügt
-> Hashverfahren können genützt werden
Bei zu hohem Füllungsgrad der Hashtabelle wird die Suche aber langsam.

c.) zur Laufzeit dürfen auch Schlüssel gelöscht werden
-> Hashverfahren versagen, weil das Löschen von Schlüsseln nicht erlaubt ist
Andreas
  Mit Zitat antworten Zitat
Furtbichler
(Gast)

n/a Beiträge
 
#8

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

  Alt 19. Mai 2012, 08:48
Ich denke es hängt auch davon ab, ob die Menge an Schlüsseln sich nie verändert oder ob zur Laufzeit Schlüssel hinzugefügt oder entfernt werden sollen.

a.) feste Menge an Schlüsseln
-> binäre Suche, Interpolationssuche oder quadratische Binärsuche liefert das beste Ergebnis

b.) zur Laufzeit wird eine begrenzte Menge an Schlüsseln hinzugefügt
-> Hashverfahren können genützt werden
Bei zu hohem Füllungsgrad der Hashtabelle wird die Suche aber langsam.

c.) zur Laufzeit dürfen auch Schlüssel gelöscht werden
-> Hashverfahren versagen, weil das Löschen von Schlüsseln nicht erlaubt ist
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.

Nur bei kleinen Datenmengen macht sich der overhead der Hashfunktion bemerkbar, hier sind vor allem einfache Verfahren im Vorteil.

Bei einem Scanner/Lexer/Tokenizer würde ich auf jeden Fall eine Hashmap nehmen, wobei ich nicht nur die Wörter speichern würde, sondern gleich auch noch die Kategorie, also 'reserved word','Zahl','Symbol','Identifier' etc. Der ist zwar anfangs langsamer, aber da ich den beim Scanner befülle, sollte ich unterm Strich besser fahren.

Ich habe es nun einmal verglichen und bei mir ist diese angeblich so blöde Variante die Schnellste.
Verglichen habe ich das Suchen in:
Dieser Implementierung, einer Dictionary, einer sortierte Stringlist und einem unsortieres Array.

Die Idee bei diesem hier gezeigten Verfahren ist es ja, die Wortliste durch eine Unterteilungsfunktion in kleinere Listen zu zerteilen:

Wenn man als Funktion einfach das erste Zeichen nimmt (und die Liste umsortiert), wird die Geschichte um 35% schneller. Und wenn man den ShortString gegen einen normalen String tauscht, wird das 4x so schnell.

Geändert von Furtbichler (19. Mai 2012 um 09:59 Uhr)
  Mit Zitat antworten Zitat
Bjoerk

Registriert seit: 28. Feb 2011
Ort: Mannheim
1.384 Beiträge
 
Delphi 10.4 Sydney
 
#9

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

  Alt 19. Mai 2012, 13:02
[..] Und wenn man den ShortString gegen einen normalen String tauscht, wird das 4x so schnell.
Aus eigener Erfahrung kann ich sagen, wenn man Strings konsequent mit const als Parameter übergibt ist der Geschwindigkeitsvorteil gegenüber Shortstrings kaum noch spürbar. Was aber immer mega bremst sind Trim und UpperCase.
  Mit Zitat antworten Zitat
Furtbichler
(Gast)

n/a Beiträge
 
#10

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

  Alt 19. Mai 2012, 14:35
Hi
Mit Const und AnsiString und UpperCase statt der Schleife ist es nicht mehr 4x so schnell, sondern nur noch 2,5x so schnell
  Mit Zitat antworten Zitat
Antwort Antwort
Seite 1 von 2  1 2   

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 09:53 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