logo标签列表

高效GUID数据结构

delphidata-structuresdelphi-2010guidunique
12

我正在寻找一种数据结构，能够快速（最好是O(1)的速度）确定给定的GUID是否为GUID集合的成员。

我的当前方法是使用带有值0的TDictionary。

虽然这个方法很快，但似乎浪费了使用哈希映射重排GUID的时间，因为GUID是根据定义被认为是唯一的，并且字典处理不需要的值。

肯定有更好的解决方案，但我找不到。你能找到吗？

3个回答
13
非常少的数据结构提供O(1)访问。一个是数组，另一个是哈希表（David的答案），我只知道另一个：Trie。这里有一个比特位Trie的简单实现：具有一些有趣的特性：
  • 免疫内存碎片化，因为不进行重新分配。
  • O(1)添加和存在测试。当然，涉及O(1)的常量相当大。

代码：

program Project23;

{$APPTYPE CONSOLE}

uses
  SysUtils, Generics.Collections;

type

  PGuidTrieNode=^TGuidTrieNode;
  TGuidTrieNode = record
    Sub:array[Boolean] of PGuidTrieNode;
  end;
  TGuidByteArray = array[0..15] of Byte;

  TGuidTrie = class
  protected
    Root: PGuidTrieNode;
  public
    constructor Create;
    destructor Destroy;override;

    procedure Add(G: TGUID);
    function Exists(G: TGUID): Boolean;
  end;

{ TGuidTrie }

procedure TGuidTrie.Add(G: TGUID);
var GBA: TGuidByteArray absolute G;
    Node: PGuidTrieNode;
    i: Integer;
    Bit: Integer;
    IsBitSet: Boolean;
const BitMask: array[0..7] of Byte = (1, 2, 4, 8, 16, 32, 64, 128);
begin
  Assert(SizeOf(G) = SizeOf(TGuidByteArray));
  Node := Root;
  for i:=0 to High(GBA) do
  begin
    for Bit := 0 to 7 do
    begin
      IsBitSet := (GBA[i] and BitMask[Bit]) <> 0;
      if (i = High(GBA)) and (Bit = 7) then
        begin
          // Payload
          Node.Sub[IsBitSet] := Pointer(1);
        end
      else
        begin
          if not Assigned(Node.Sub[IsBitSet]) then
            Node.Sub[IsBitSet] := GetMemory(SizeOf(TGuidTrieNode));
          Node := Node.Sub[IsBitSet];
        end;
    end;
  end;
end;

constructor TGuidTrie.Create;
begin
  Root := GetMemory(SizeOf(TGuidTrieNode))
end;

destructor TGuidTrie.Destroy;

  procedure KillNode(Node: PGuidTrieNode);
  var i:Integer;
  begin
    if Assigned(Node.Sub[True]) then
        if Node.Sub[True] <> Pointer(1) then
        begin
          KillNode(Node.Sub[True]);
        end;
    FreeMemory(Node);
  end;

begin
  KillNode(Root);
  inherited;
end;

function TGuidTrie.Exists(G: TGUID): Boolean;
var GBA: TGuidByteArray absolute G;
    Node: PGuidTrieNode;
    i: Integer;
    Bit: Integer;
    IsBitSet: Boolean;
const BitMask: array[0..7] of Byte = (1, 2, 4, 8, 16, 32, 64, 128);
begin
  Assert(SizeOf(G) = SizeOf(TGuidByteArray));
  Node := Root;
  for i:=0 to 15 do
  begin
    for Bit := 0 to 7 do
    begin
      IsBitSet := (GBA[i] and BitMask[Bit]) <> 0;
      if not Assigned(Node.Sub[IsBitSet]) then
      begin
        Result := False;
        Exit;
      end;
      Node := Node.Sub[IsBitSet];
    end;
  end;
  Result := True; // Node now contains the Payload
end;

const G1: TGUID = '{68D09F12-3E0D-4963-B32C-4EE3BD90F69C}';
      G2: TGUID = '{BEED37F6-9757-41DC-8463-AF094392652B}';

var T: TGuidTrie;

begin
  try

    T := TGuidTrie.Create;
    try
      if T.Exists(G1) then WriteLn('Exists')
                      else WriteLn('NOT Exists');
      T.Add(G1);
      if T.Exists(G1) then WriteLn('Exists')
                      else WriteLn('NOT Exists');

      if T.Exists(G2) then WriteLn('Exists')
                      else WriteLn('NOT Exists');
      T.Add(G2);
      if T.Exists(G2) then WriteLn('Exists')
                      else WriteLn('NOT Exists');
    finally T.Free;
    end;

  except
    on E: Exception do
      Writeln(E.ClassName, ': ', E.Message);
  end;
end.
3
我认为 Trie 并不比哈希表本质上更慢，特别是当用于自然数据时；而且它们具有有趣的保证属性，不像哈希表提供的“统计”属性。但考虑到要索引的数据的性质，我会说 GUID 是 Trie 的最坏情况，同时也是哈希表的最佳情况。哈希表会喜欢那些随机数据，而 Trie 将无法找到足够的共同前缀来使用高效的存储。 - Cosmin Prund
SO的最佳表现：解决问题并获得对问题领域的新见解！+1 - sum1stolemyname
7

我认为你已经完成了99%的工作。

哈希（Hashing）听起来像是正确的解决方案。利用GUID的特殊性质的明显方法是提供自己的哈希函数，将构成GUID的4个32位整数合并为一个32位整数。我会只使用异或（XOR）运算符对这4个整数进行操作。

我假设你正在使用Generics.Collections.TDictionary。你可以通过向构造函数传递自定义比较器来提供自己的哈希函数。我不会担心存储多余的值，因为我认为这不会以可感知的方式影响性能。

我相信你正在将GUID作为128位整数而不是字符串进行存储。

最后，我想到GUID的默认比较器可能已经按照这种方式生成哈希码。在做出任何更改之前，检查一下这一点是值得的。

编辑

默认哈希码使用Bob Jenkins哈希应用于二进制数据。使用异或可能会更快，但默认哈希码似乎不会成为性能瓶颈。

换句话说，TDictionary<TGUID,Integer>将完全满足您的需求。

1
我只会将这4个整数相加。一个异或操作也可以实现。 - Andrej Kirejeŭ
@Andrei 是的，这样会更好，不需要操心范围检查。谢谢。 - David Heffernan
从汇编的角度来看，异或操作并不比加法更快 - 例如，ZLib作者在创建Adler32时进行了一些良好的速度优化。 - Arnaud Bouchez
@A.Bouchez 我想这只是避免了与范围检查的折腾。当然，你可以使用内联汇编来实现，那么编译器就永远不需要知道！ - David Heffernan
我昨天已经点过赞了，因此无法为此编辑再次点赞。我想补充一些内容：在我的一个“宠物”项目中，我使用了一个TDictionary<SHA1,Integer>，并索引了大量的数据。它一直运行良好，直到我用完了RAM，然后它突然崩溃了。如果数据适合放入RAM，则使用TDictionary进行索引没有问题。对于不适合放入RAM的数据，我实现了一个哈希表，并将其备份到磁盘上的文件中，对于我的工作负载，它的性能优于我的B-Tree实现。总的来说，TDictionary<>是一个非常棒的数据结构，这个回答应该会得到更多的赞。 - Cosmin Prund
2
type
    PGuidDictionaryItem = ^TGuidDictionaryItem;

    TGuidDictionaryItem = record
        Key: TGuid;
        Value: Pointer;
        Next: PGuidDictionaryItem;
    end;

    TGuidDictionary = class
    private
    const
        HashSize = 2048;
    var
        Size: integer;
        FTable: array [0..HashSize-1] of PGuidDictionaryItem;

        function GetHashCode(Guid: TGUID): integer;
    public
        constructor Create;
        destructor Destroy; override;

        procedure Add(Key: TGUID; Value: TObject);
        function TryFind(Key: TGUID; out Value: TObject): boolean;
        function Contains(Key: TGUID): Boolean;
        procedure Remove(Key: TGuid);
    end;

{ TGuidDictionary }

procedure TGuidDictionary.Add(Key: TGUID; Value: TObject);
var
    Hc: integer;
    PHi: PGuidDictionaryItem;
begin
    Hc := GetHashCode(Key);

    if FTable[Hc] <> nil then
    begin
        PHi := FTable[Hc];
        repeat
            if TGuidEx.EqualGuids(PHi.Key, Key) then
                Break;

            PHi := Phi.Next;
        until PHi = nil;
    end
    else
        Phi := nil;

    if PHi <> nil then
        PHi.Value := Value
    else
    begin
        New(PHi);
        PHi.Value := Value;
        PHi.Key := Key;
        PHi.Next := FTable[Hc];
        FTable[Hc] := PHi;
    end;
end;

function TGuidDictionary.Contains(Key: TGUID): Boolean;
var
    O: TObject;
begin
    Result := TryFind(Key, O);
end;

constructor TGuidDictionary.Create;
var
    i: integer;
begin
    inherited;

    for i := Low(FTable) to High(FTable) do
        FTable[i] := nil;
end;

destructor TGuidDictionary.Destroy;
var
    i: integer;
    Phi, PhiNext: PGuidDictionaryItem;
begin
    for i := Low(FTable) to High(FTable) do
    begin
        Phi := FTable[i];
        while Phi <> nil do
        begin
            PhiNext := Phi.Next;
            Dispose(Phi);
            Phi := PhiNext;
        end;
    end;

    inherited;
end;

function TGuidDictionary.GetHashCode(Guid: TGUID): integer;
var
    N: array [0..3] of integer absolute Guid;
begin
    Result := Abs(N[0] xor N[1] xor N[2] xor N[3]) mod HashSize;
end;

procedure TGuidDictionary.Remove(Key: TGuid);
var
    Hc: Integer;
    Phi, BeforPhi: PGuidDictionaryItem;

begin
    Hc := GetHashCode(Key);

    BeforPhi := nil;
    Phi := FTable[Hc];
    while (Phi <> nil) and not TGuidEx.EqualGuids(Phi.Key, Key) do
    begin
        BeforPhi := Phi;
        Phi := Phi.Next;
    end;

    if Phi = nil then
        Exit;

    if BeforPhi <> nil then
        BeforPhi.Next := Phi.Next
    else
        FTable[Hc] := Phi.Next;

    Dispose(Phi);
end;

function TGuidDictionary.TryFind(Key: TGUID; out Value: TObject): boolean;
var
    Hc: Integer;
    Phi: PGuidDictionaryItem;
begin
    Hc := GetHashCode(Key);
    Phi := FTable[Hc];
    while (Phi <> nil) and not TGuidEx.EqualGuids(Phi.Key, Key) do
        Phi := Phi.Next;

    if Phi <> nil then
        Value := TObject(Phi.Value)
    else
        Value := nil;

    Result := Phi <> nil;
end;

procedure TestDictMisc.TestGuidDictionary;
const
    G1: TGUID = '{68D09F12-3E0D-4963-B32C-4EE3BD90F69C}';
    G2: TGUID = '{BEED37F6-9757-41DC-8463-AF094392652B}';
var
    T: TGuidDictionary;
    Obj1, Obj2, O: TObject;
begin
    T := TGuidDictionary.Create;
    Obj1 := TObject.Create();
    Obj2 := TObject.Create();
    try
        CheckFalse(T.Contains(G1));

        T.Add(G1, Obj1);
        CheckTrue(T.Contains(G1));

        T.Add(G2, Obj2);
        CheckTrue(T.Contains(G2));

        T.Add(G2, Obj2);
        CheckTrue(T.Contains(G2));

        CheckTrue(T.TryFind(G1, {out} O));
        CheckSame(Obj1, O);

        CheckTrue(T.TryFind(G2, {out} O));
        CheckSame(Obj2, O);

        T.Remove(G1);
        CheckFalse(T.Contains(G1));
        CheckFalse(T.TryFind(G1, {out} O));

        T.Add(G1, Obj1);
        CheckTrue(T.TryFind(G1, {out} O));
        CheckSame(Obj1, O);

    finally
        Obj1.Free();
        Obj2.Free();

        T.Free;
    end;
end;
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接