TDictionary og TEqualityComparer

Forleden dag havde jeg brug for at vide, hvor mange rækker, der var i hver tabel i en database, og det havde jeg så brug for at spørge om mange gange. Til det brugte jeg en TDictionary. TDictionary er en af de strukturer vi fik sammen med Generics og dermed Delphi 2009. TDictionary bruges til at samle en nøgle med en værdi i en liste. Før Generics ville jeg have brugt en TStringList og læst alle tabelnavnene ind som strings, og de respektive tabellers rækkeantal ville jeg have skrevet som integer på TObject-pladsen i listen. Den slags hacks er vi heldigvis ovre idag - netop fordi vi har Generics.

Til brug i dette indlæg har jeg konstrueret et andet eksempel. Jeg har hentet teksten fra "The Adventures of Sherlock Holmes" fra Project Gutenberg og gemt den som tekstfil, så jeg kan lave en liste over alle de forskellige ord og deres antal. Til det vil jeg bruge en TDictonary struktur. Jeg vil også i dette blogindlæg vise, at det er muligt at skrive sin egen metode til at sammenligne to elementer i listen. Jeg har her valgt at sammenligne dels med hensyn til store og små bogstaver og dels uden - eller helt kort: er AAAA det samme som aaaa eller ej.

Det første jeg skal have gjort er, at få delt teksten ind i ord. Jeg bruger en TStringlist til at læse min tekst ind i og derfra parse den videre ud i de enkelte ord. Der findes helt sikkert hurtigere måder at gøre på end den jeg viser her, men nu er det læsbarheden og forståeligheden jeg går efter - ikke en opvisning i performancetæt kode :o)

Jeg vil ikke kommentere en hel masse på algoritmen. Dels ligger den udenfor scope af dette blog indlæg, og dels mener jeg den er rimelig selvforklarende. Skulle der være nogen blandt læserne der alligevel ønsker noget uddybet, så skriv endelig så skal jeg nok svare.

Split bogen ud i enkelte ord


function TMainForm.ParseFile: TStringList;

var
  P, Start: PChar;
  s: String;
  Buffer: TStringList;
const
  Delimiter = [#$00 .. #$30, #$3A, #$40, #$5B .. #$61, ';', '?'];
begin
  Result := TStringList.Create;

  Buffer := TStringList.Create;
  try
    Buffer.LoadFromFile('pg1661.txt');
    P := PChar(Buffer.Text);

    while P^ <> #0 do
    begin
      Start := P;
      while not CharInSet(P^, Delimiter) do
        Inc(P);

      SetString(s, Start, P - Start);
      Result.Add(s);

      while CharInSet(P^, Delimiter) do
        if P^ = #0 then
          break
        else
          Inc(P);
    end;

  finally
    FreeAndNil(Buffer);
  end;
end;

Nu hvor jeg har min liste af ord skal de stoppes ind i en TDictionary, således at vi har en nøgle der er ordet, og en værdi der angiver hvor mange gange ordet optræder i bogen. Som jeg nævnte vil jeg bruge to forskellige principper til at tælle forskellige ord med: "Case sensitive" (godt dansk ord ;-)) og "ikke case sensitive". Derfor har den procedure, der har til formål at vise resultatet på skærmen, også en IEqualityComparer<String> med ind som parameter.

IEqualityComparer er defineret i Generics.Defaults (System.Generics.Defaults hvis du bruger XE2), og ser således ud:

IEqualityComparer<T> = interface
    function Equals(const Left, Right: T): Boolean;
    function GetHashCode(const Value: T): Integer;
  end;

IEqualityComparer er således den skabelon som man skal bruge, hvis man vil lave en sammenligningsklasse til brug i fx TDirectory. Heldigvis har hver datatype allerede sin egen prædefinerede samlingningsklasse som man kan få fat på ved at skrive TEqualityComparer<T>.Default, hvor T kan være en hvilken som helst datatype. Således skriver man for en string:  TEqualityComparer<String>.Default.

Jeg vil her vise den procedure, jeg bruger til at synliggøre mit TDictonary:

procedure TMainForm.NumberInstances(const AComparer: IEqualityComparer<string>; TheListView: TListView);
var
  Dictionary: TDictionary<string, Cardinal>;
  AWord: string;
  Buffer: TStringList;
  Words: TStringList;
begin
  // Opret en ny instans af TDictionary, der bruger AComparer som "sammenligner"
  Dictionary := TDictionary<string, Cardinal>.Create(AComparer);

  // Hent ord fra filen
  Words := ParseFile;

  Buffer := TStringList.Create;

  // Deaktiver skærmopdatering af hensyn til performance
  TheListView.Items.BeginUpdate;
  try
    TheListView.Clear;

    {
      Løb listen med ord igennem.
      Hvis den findes i Dictionary allerede så opdater tælleren med 1
      ellers opret et nyt element i Dictionary og sæt tælleren til 1
    }
    for AWord in Words do
      if Dictionary.ContainsKey(AWord) then
        Dictionary[AWord] := Dictionary[AWord] + 1
      else
        Dictionary.Add(AWord, 1);

    // Tag alle forskellige ord og smid den på en liste
    for AWord in Dictionary.Keys do
      Buffer.Add(AWord);

    // Sorter listen
    Buffer.Sort;

    // Vis listen på skærmen
    for AWord in Buffer do
      with TheListView.Items.Add do
      begin
        Caption := AWord;
        SubItems.Add(IntToStr(Dictionary[AWord]));
      end;

  finally
    //Slå skærm opdateringer til
    TheListView.Items.EndUpdate;
   
    //Frigiv hukommelse
    FreeAndNil(Buffer);
    FreeAndNil(Dictionary);
    FreeAndNil(Words);
  end;
end;

Jeg vil ikke her kommentere yderligere på proceduren, idet jeg allerede har skrevet kommentarer i koden. Det komplette eksempel kan sædvanen tro hentes her.

Nu hvor jeg kan skille min fil ad i enkelte ord, og jeg har skrevet en procedure til at vise det på skærmen, må det være på tide at få skrevet en case insensitive sammenligningsklasse. Jeg har tidligere vist at en sådan skal bygges over skabelonen IEqualityComparer. Så nu er det blot at gå i gang.

type

  //opbyg klassen over IEqualityComparer
  TCaseInsensitiveStringComparer = class(TEqualityComparer<string>)
  public
    function Equals(const Left, Right: string): Boolean; override;
    function GetHashCode(const Value: string): Integer; override;
  end;

function TCaseInsensitiveStringComparer.Equals(const Left, Right: string): Boolean;
begin
  //Sammenlign de to strings uden hensyn til store og små bogstaver
  Exit(SameText(Left, Right));
end;

function TCaseInsensitiveStringComparer.GetHashCode(const Value: string): Integer;
begin
// Da vi sammenligner case insensitive kalder vi
// TEqualityComparer<string>.Default.GetHashCode med AnsiUpperCase(Value)
  Result := TEqualityComparer<string>.Default.GetHashCode(AnsiUpperCase(Value));
end;

Som det ses bruger jeg blot den oprindelige hash-algoritme fra TEqualityComparer<string>, men jeg kunne i princippet havde skrevet min egen her.

Til sidst er der blot at få kaldt koden. Henholdsvis for case sensitive og case insensitive versionen af min sammenligner:

Case sensitive kald:
  NumberInstances(TEqualityComparer<string>.Default, default);

Case insensitive kald :
  NumberInstances(TCaseInsensitiveStringComparer.Create(), Custom);

Det skal her bemærkes at det andet parameter er det listview, som jeg ønsker at vise mit resultat i. Mine listviews har jeg navngivet henholdsvis "Default" og "Custom".

Til slut vil jeg blot vise skærmbilledet for programmet :

Som det ses, så har den ene sammenligningsklasse fundet 15 forekomster af "Adler" og 1 forekomst af "ADLER". Hvorimod den anden "kun" har fundet "Adler", men til gengæld har den fundet 16 forekomster (15 + 1). Samme ses bl.a. med "Adventure".

Således har jeg nu illustreret, hvordan man bruger en TDictionary og skriver sin egen sammenligningsklasse. I mit eksempel her har jeg bare brugt to simple datatyper, men der er ikke noget i vejen for at bruge mere komplicerede datatyper som fx klasser og records, og så dertil skrive sin egne sammenligningsklasse.

Jeg vil lige minde om at det komplette eksempel kan hentes her.

Tilbage er blot at ønske alle mine læsere glædelig jul og godt nytår. Jeg vil bruge tiden mellem jul og nytår til at komme på plads på en ny blogging platform. Men mere om det senere.

Jens Borrisholt