映射两组元素

| 有一组索引为[0，n]的元素。在任何时候，A集合中最多m个元素可以处于活动状态（使用中），明显的条件是0 <= m <= n。我想索引本地数组内的那些活动元素。可以在程序执行时动态停用元素，并且我希望在激活新元素时可以重新使用其索引。我想以最有效的方式将元素索引映射到它的本地索引，因为我正在使用本地索引来快速查找活动元素数据。平凡的哈希函数（元素索引==本地索引）和通过关联列表的强行强制的可能解决方案在n较大时无法很好地扩展。动态扩展/收缩数据结构是显而易见的优势。谢谢

已邀请:

1 个回复

博沮富教全

我想以最有效的方式将元素索引映射到它的本地索引没有最快的代码（tanstatfc）这样的东西-Michael Abrash 您的问题有很多解决方案。第一步是选择数据结构和哈希函数。数据结构可以是：普通数组+直哈希数组包含指向链接列表的起始指针+哈希到起始元素二叉树，其中散列表示树的分支我要停在那里。 1个普通数组这是最简单的解决方案。而且，如果您的分配过于陈旧（这意味着它们在空间上聚集在一起），这甚至可能是一个很好的解决方案。运作方式如下：您需要大量的虚拟内存。您可以声明2GB的内存（即使是在1GB的计算机上），因为它只是虚拟的，只有在您实际使用它的情况下才会提交。将块拆分为4KB块或其倍数（x86处理器使用4KB块），并使索引数组开始指定是否已提交4K块。如果需要编写，请在索引中检查页面是否已提交，如果尚未提交，则提交它。写到列表。如果需要阅读，请检查索引，如果尚未提交页面，没有命中，返回false，否则请阅读条目。在此结构中，每个条目可容纳2GB / 4字节= 5亿个条目。这对于分组在一起的群集中的数据最有效。如果索引是随机的，这将是低效的。这是Delphi的伪代码：使用虚拟内存的直接列表的示例代码

type
  TElement = record
    Data: string; //really a pointer to string in Delphi
    function PutInList(IndexNr: integer): PElement;
    constructor CreateFromList(Index: integer);
  end;

  PElement = ^TElement;
  TElements = array[0..0] of TElement;
  PElements = ^TElements;

const
  ArraySize = (1024 * 1024 * 1024 * 2); //2GB
  BlockSize = 4096;
  NumberOfBlocks = (ArraySize) div (BlockSize); //2GB in 4KB blocks
  BitsPerInt32 = 32;
  IndexCount = NumberOfBlocks div BitsPerInt32;

var
  IndexBlock: array[0..IndexCount-1]; //1 bit for each block = 64KB.

var
  Elements: PElements;

function ClaimVirtualBlock: PElements; 
begin
  FillChar(IndexBlock, #0, SizeOf(IndexBlock)); //Zero init indexblock
  Result:= PElements(VirtualAlloc(nil, ArraySize, MEM_RESERVE, PAGE_READWRITE));
end;

function GetAddress(Index: integer): PElement; inline;
var
  DestAddress: PElement;
  BlockIndex: Integer;
  BlockDWord: integer;
  BlockMask: integer;
  BlockNotAllocated: boolean;
begin
  //Create a new element in our list
  Integer(DestAddress):= Index * SizeOf(TElement); 
  BlockIndex:= Integer(DestAddress) div 4096;
  BlockMask:= 1 shl (BlockIndex mod 32);
  BlockIndex:= BlockIndex div 32;
  BlockNotAllocated:= (IndexBlock[BlockIndex] and BlockMask) <> 0;
  if BlockNotAllocated then begin
    IndexBlock[BlockIndex]:= IndexBlock[BlockIndex] or BlockMask;
    if VirtualAlloc(DestAddress, BlockSize, MEM_COMMIT, PAGE_READWRITE) = nil then
      raise EOutOfMemoryError.Create(\'Out of physical memory\');
  end;
  Result:= DestAddress;
end;


function TElements.PutInList(IndexNr: integer): PElement;
begin
  Result:= GetAddress(IndexNr);
  Result^.Data:= Self.Data;
end;

constructor TElements.CreateFromList(Index: integer);
var
  ListElement: PElement;
begin
  ListElement:= GetAddress(Index);
  Self.IndexNr:= Index;
  Self.Data:= ListElement.Data;
end;

2带有链接列表的数组创建一个带有指向链接列表的指针的数组。散列索引，它指向您的数组项。遍历链接列表，直到找到正确的项目。对于插入项目：执行步骤1和2，并在开始处插入您的项目。这对于索引非常随机且碰撞变化很小的数据最有效。成功与否主要取决于您的哈希函数，它需要尽可能多地选择一个不同的数组条目，太多的“ 1”，您将一直无时无刻不在遍历相同的链表。链接列表数组的示例代码

type  
  PElement = ^TElement;
  TElement = record
    Index: integer;
    Data: string;
    Next: PElement;
    procedure PutInList;
    constructor CreateFromList(AIndex: integer);
  end;

const
  LargePrimeNumber = 100003;

var
  StartArray: array[0..LargePrimeNumber-1] of PElement;

procedure InitList;
begin
  FillChar(StartArray, #0, SizeOf(StartArray));
end;

function IndexToArrayHash(AnIndex: integer): integer; inline;
begin
  Result:= AnIndex mod LargePrimeNumber;
end;

procedure TElement.PutInList;
var
  ArrayIndex: integer;
begin
  ArrayIndex:= IndexToArrayHash(Self.Index);
  Self.Next:= StartArray[ArrayIndex];
  StartArray[ArrayIndex]:= @Self;
end;

constructor CreateFromList(AIndex: integer);  
var
  ArrayIndex: integer;
  Element: PElement;
begin
  ArrayIndex:= IndexToArrayHash(AIndex);
  Element:= StartArray[ArrayIndex];
  while (Element <> nil) and (Element.Index <> AIndex) do begin
    Element:= Element^.Next;
  end; {while}
  if (Element <> nil) then begin
    Self.Index:= Element^.Index;
    Self.Data:= Element^.Data;
    Self.Next:= nil;
  end;
end;

3二叉树使用索引中的位遍历树创建一个只有根的空树如果要插入项目，请使用索引中的位遍历树（0 =左分支，1 =右分支）。在遍历树时，将较高等级的索引附加在下方，而将较高等级的索引插入较高的索引。（重物沉入底部）。使用二叉树的示例代码

type
  PElement = ^TElement;
  TElement = record
    Left, Right: PElement;
    Index: integer;
    Data: string;
    procedure PutInList;
  end;

function GetFromList(AIndex: integer): PElement;

var
  Root: TElement;

const
  GoLeft: false;
  GoRight: true;

procedure InitRoot;
begin
  FillChar(Root, #0, SizeOf(Root));
end;

function TElement.PutInlist;
var
  CurrentElement: PElement;
  PrevElement:= PElement;
  Depth: integer;
  Direction: boolean;
begin
  PrevElement:= nil;
  CurrentElement:= @Root;
  Depth:= 0;
  //Walk the tree
  while (CurrentElement <> nil) and (CurrentElement.Index < Index) do begin
    PrevElement:= CurrentElement;
    Direction:= Odd(Index shr Depth);
    case Direction of
      GoLeft: CurrentElement:= CurrentElement^.Right;
      GoRight: CurrentElement:= CurrentElement^.Left;
    end; {case}
    Inc(Depth);
  end; {while}

  //Insert the item here
  case Direction of 
    GoLeft: PrevItem^.Left:= @Self;
    GoRight: PrevItem.Right:= @Self;
  end;

  //What to do with the currentItem.
  if Assigned(CurrentItem) then begin
    Direction:= Odd(CurrentItem^.Index shr Depth);
    case Direction of
      GoLeft: begin
        Self.Left:= CurrentItem;
        Self.Right:= CurrentItem^.Right;
      end; {GoLeft}
      GoRight: begin
        Self.Right:= CurrentItem;
        Left:= CurrentItem^.Left;
      end; {GoRight}
    end; {case}
  end; {if}
end;

function TElement.GetFromList(AIndex: integer): PElement;
var
  CurrentElement: PElement;
  Depth: integer;
  Direction: boolean;
begin
  CurrentElement:= @Root;
  Depth:= 0;
  //Walk the tree
  while (CurrentElement <> nil) and (CurrentElement.Index < Index) do begin
    Direction:= Odd(Index shr Depth);
    case Direction of
      GoLeft: CurrentElement:= CurrentElement^.Right;
      GoRight: CurrentElement:= CurrentElement^.Left;
    end; {case}
    Inc(Depth);
  end; {while}
  if Assigned(CurrentElement) and (CurrentElement^.Index = AIndex) then begin
    Result:= CurrentElement;
  end
  else Result:= nil;
end;

推荐阅读： Knuth：TAOCP I：基本算法，第2章ISBN 0-201-03809-9 Cormen，Leiserson和Rivest：算法简介，第三章数据结构ISBN 0-07-013143-0

要回复问题请先登录或注册

映射两组元素

1 个回复

发起人

lookup

indexing

set

delphi

map

问题状态

映射两组元素

与内容相关的链接

1 个回复

发起人

lookup

indexing

set

delphi

map

问题状态