delphi - 如何改进在字典中加载和搜索的代码(Delphi)？

Question

我是一名 Delphi 程序员。我制作了一个程序，该程序使用带有单词和表达式的字典(作为“字符串数组”加载到程序中)。它使用基于“校验和”的搜索算法(我希望这是正确的词)。基于此将字符串转换为整数:

var
   FHashSize: Integer; //stores the value of GetHashSize
   HashTable, HashTableNoCase: array[Byte] of Longword;
   HashTableInit: Boolean = False;

const
   AnsiLowCaseLookup: array[AnsiChar] of AnsiChar = (
      #$00, #$01, #$02, #$03, #$04, #$05, #$06, #$07,
      #$08, #$09, #$0A, #$0B, #$0C, #$0D, #$0E, #$0F,
      #$10, #$11, #$12, #$13, #$14, #$15, #$16, #$17,
      #$18, #$19, #$1A, #$1B, #$1C, #$1D, #$1E, #$1F,
      #$20, #$21, #$22, #$23, #$24, #$25, #$26, #$27,
      #$28, #$29, #$2A, #$2B, #$2C, #$2D, #$2E, #$2F,
      #$30, #$31, #$32, #$33, #$34, #$35, #$36, #$37,
      #$38, #$39, #$3A, #$3B, #$3C, #$3D, #$3E, #$3F,
      #$40, #$61, #$62, #$63, #$64, #$65, #$66, #$67,
      #$68, #$69, #$6A, #$6B, #$6C, #$6D, #$6E, #$6F,
      #$70, #$71, #$72, #$73, #$74, #$75, #$76, #$77,
      #$78, #$79, #$7A, #$5B, #$5C, #$5D, #$5E, #$5F,
      #$60, #$61, #$62, #$63, #$64, #$65, #$66, #$67,
      #$68, #$69, #$6A, #$6B, #$6C, #$6D, #$6E, #$6F,
      #$70, #$71, #$72, #$73, #$74, #$75, #$76, #$77,
      #$78, #$79, #$7A, #$7B, #$7C, #$7D, #$7E, #$7F,
      #$80, #$81, #$82, #$83, #$84, #$85, #$86, #$87,
      #$88, #$89, #$8A, #$8B, #$8C, #$8D, #$8E, #$8F,
      #$90, #$91, #$92, #$93, #$94, #$95, #$96, #$97,
      #$98, #$99, #$9A, #$9B, #$9C, #$9D, #$9E, #$9F,
      #$A0, #$A1, #$A2, #$A3, #$A4, #$A5, #$A6, #$A7,
      #$A8, #$A9, #$AA, #$AB, #$AC, #$AD, #$AE, #$AF,
      #$B0, #$B1, #$B2, #$B3, #$B4, #$B5, #$B6, #$B7,
      #$B8, #$B9, #$BA, #$BB, #$BC, #$BD, #$BE, #$BF,
      #$C0, #$C1, #$C2, #$C3, #$C4, #$C5, #$C6, #$C7,
      #$C8, #$C9, #$CA, #$CB, #$CC, #$CD, #$CE, #$CF,
      #$D0, #$D1, #$D2, #$D3, #$D4, #$D5, #$D6, #$D7,
      #$D8, #$D9, #$DA, #$DB, #$DC, #$DD, #$DE, #$DF,
      #$E0, #$E1, #$E2, #$E3, #$E4, #$E5, #$E6, #$E7,
      #$E8, #$E9, #$EA, #$EB, #$EC, #$ED, #$EE, #$EF,
      #$F0, #$F1, #$F2, #$F3, #$F4, #$F5, #$F6, #$F7,
      #$F8, #$F9, #$FA, #$FB, #$FC, #$FD, #$FE, #$FF);

implementation

function GetHashSize(const Count: Integer): Integer;
begin
   if Count < 65 then
      Result := 256
   else
      Result := Round(IntPower(16, Ceil(Log10(Count div 4) / Log10(16))));
end;

function Hash(const Hash: LongWord; const Buf; const BufSize: Integer): LongWord;
var P: PByte;
   I: Integer;
begin
   P := @Buf;
   Result := Hash;
   for I := 1 to BufSize do
   begin
      Result := HashTable[Byte(Result) xor P^] xor (Result shr 8);
      Inc(P);
   end;
end;

function HashStrBuf(const StrBuf: Pointer; const StrLength: Integer; const Slots: LongWord): LongWord;
var P: PChar;
   I, J: Integer;
begin
   if not HashTableInit then
      InitHashTable;
   P := StrBuf;
   if StrLength <= 48 then // Hash all characters for short strings
      Result := Hash($FFFFFFFF, P^, StrLength)
   else
   begin
      // Hash first 16 bytes
      Result := Hash($FFFFFFFF, P^, 16);
      // Hash last 16 bytes
      Inc(P, StrLength - 16);
      Result := Hash(Result, P^, 16);
      // Hash 16 bytes sampled from rest of string
      I := (StrLength - 48) div 16;
      P := StrBuf;
      Inc(P, 16);
      for J := 1 to 16 do
      begin
         Result := HashTable[Byte(Result) xor Byte(P^)] xor (Result shr 8);
         Inc(P, I + 1);
      end;
   end;
  // Mod into slots
   if Slots <> 0 then
      Result := Result mod Slots;
end;

procedure InitHashTable;
var I, J: Byte;
   R: LongWord;
begin
   for I := $00 to $FF do
   begin
      R := I;
      for J := 8 downto 1 do
         if R and 1 <> 0 then
            R := (R shr 1) xor $EDB88320
         else
            R := R shr 1;
      HashTable[I] := R;
   end;
   Move(HashTable, HashTableNoCase, Sizeof(HashTable));
   for I := Ord('A') to Ord('Z') do
      HashTableNoCase[I] := HashTableNoCase[I or 32];
   HashTableInit := True;
end;

HashStrBuf 的结果是“and (FHashSize - 1)”，并用作“整数数组的数组”(FHashSize 大小)中的索引，以存储该“字符串数组”中的字符串索引。这样，当搜索字符串时，它会被转换为“校验和”，然后代码在具有该索引的“分支”中搜索，将此字符串与字典中具有相同“校验和”的字符串进行比较。

理想情况下，字典中的每个字符串都应具有唯一的校验和。但在“现实世界”中，大约 2/3 的单词与其他单词共享相同的“校验和”。因此，搜索速度不是那么快。在这些字典中，字符串由以下字符组成:['a'..'z',#224..#246,#248..#254,#154,#156..#159,#179,#186, #191,#190,#185,'0'..'9', '''']有什么方法可以改进“散列”，以便字符串具有更独特的“校验和”？噢，一种方法是增加“整数数组的数组”(FHashSize)的大小，但不能增加太多，因为它需要大量的 RAM。

另一件事:这些词典仅作为单词/表达式(而不是“校验和”)存储在 HDD 上。它们的“校验和”是在程序启动时生成的。但这需要花费很多秒的时间......有什么办法可以加快程序的启动速度吗？也许通过改进“散列”功能，也许通过将“校验和”存储在硬盘上并从那里加载它们......

任何意见都将不胜感激......

PS:这是搜索代码:

function TDictionary.LocateKey(const Key: AnsiString): Integer;
var i, j, l, H: Integer;
   P, Q: PChar;
begin
   Result := -1;
   l := Length(Key);
   H := HashStrBuf(@Key[1], l, 0) and (FHashSize - 1);
   P := @Key[1];
   for i := 0 to High(FHash[H]) do  //FHash is that "array of array of integer"
   begin
      if l <> FKeys.ItemSize[FHash[H][i]] then //FKeys.ItemSize is an byte array with the lengths of strings from dictionary
         Continue;
      Q := FKeys.Pointer(FHash[H][i]); //pointer to string in dictionary
      for j := 0 to l - 1 do
         if (P + j)^ <> (Q + j)^ then
            Break;
      if j = l then
      begin
         Result := FHash[H][i];
         Exit;
      end;
   end;
end;

Answer 1

不要reinvent the wheel !

恕我直言，您的散列远非高效，并且您的碰撞算法可以改进。

以 IniFiles 单元和 THashedStringList 为例。它有点旧，但对于使用哈希的字符串列表来说是一个好的开始。

有很多很好的 Delphi 实现，例如 SuperObject还有很多other code ...

看看我们的SynBigTable单元，它可以非常快速地处理内存或文件中的数据数组，并具有完整的索引搜索。或our latest TDynArray wrapper围绕任何动态数据数组，对其实现类似 TList 的方法，包括快速二分搜索。我非常确定，如果您使用有序索引然后使用快速二分搜索，它可能比使用散列的手动调整代码更快。

后记:

关于字符串内容的纯哈希速度，看一下这个函数 - 对于 Delphi 7，将 RawByteString 重命名为 AnsiString，将 PPtrInt 重命名为 PPointer，将 PtrInt 重命名为 Integer:

function Hash32(const Text: RawByteString): cardinal;
function SubHash(P: PCardinalArray): cardinal;
{$ifdef HASINLINE}inline;{$endif}
var s1,s2: cardinal;
    i, L: PtrInt;
const Mask: array[0..3] of cardinal = (0,$ff,$ffff,$ffffff);
begin
  if P<>nil then begin
    L := PPtrInt(PtrInt(P)-4)^; // fast lenght(Text)
    s1 := 0;
    s2 := 0;
    for i := 1 to L shr 4 do begin // 16 bytes (4 DWORD) by loop - aligned read
      inc(s1,P^[0]);
      inc(s2,s1);
      inc(s1,P^[1]);
      inc(s2,s1);
      inc(s1,P^[2]);
      inc(s2,s1);
      inc(s1,P^[3]);
      inc(s2,s1);
      inc(PtrUInt(P),16);
    end;
    for i := 1 to (L shr 2)and 3 do begin // 4 bytes (DWORD) by loop
      inc(s1,P^[0]);
      inc(s2,s1);
      inc(PtrUInt(P),4);
    end;
    inc(s1,P^[0] and Mask[L and 3]);      // remaining 0..3 bytes
    inc(s2,s1);
    result := s1 xor (s2 shl 16);
  end else
    result := 0;
end;
begin // use a sub function for better code generation under Delphi
  result := SubHash(pointer(Text));
end;

我们的 SynCommons.pas 甚至还有一个纯粹的 asm 版本，甚至更快。单元。我不知道有任何更快的哈希函数(它比 crc32/adler32/IniFiles.hash 更快...)。它基于 adler32，但使用 DWORD 对齐读取和求和以获得更好的速度。当然，这可以通过 SSE asm 来改进，但这里是一个快速的纯 Delphi 哈希函数。

然后不要忘记使用“乘法”/“二进制和运算”进行哈希解析，就像在 IniFiles 中一样。它将减少哈希列表的迭代次数。

但是由于您没有提供搜索源代码，我们无法知道这里可以改进什么。