映射两组元素

Question

有一组索引为 [0, n] 的元素。在任何时候，A 集中最多 m 个元素可以处于活动状态（使用中），明显的条件是 0 <= m <= n。我想在本地数组中索引这些活动元素。可以在程序执行时动态停用元素，并且我希望在激活新元素时可以重用其索引。

我想以最有效的方式将元素索引映射到其本地索引，因为我使用本地索引来快速查找活动元素数据。

简单散列函数（元素索引 == 本地索引）和通过关联列表进行暴力破解的可能解决方案对于大 n 来说不能很好地扩展。

数据结构的动态扩展/收缩是一个明显的优点。

谢谢

Answer 1

我想以最有效的方式将元素索引映射到它的本地索引

没有最快的代码（tanstatfc） - Michael Abrash

有您的问题有多种解决方案。
第一步是选择数据结构和哈希函数。

数据结构可以是：

1. 普通数组 + 直散列
2. 数组保存指向链表的起始指针 + 散列链接到起始元素
3. 二叉树，其中散列表示树的分支，
4. 我将在此停止。

1 普通数组

这是最简单的解决方案。如果您的分配很混乱（这意味着它们在空间中聚集在一起），这甚至可能是一个很好的解决方案。
它的工作原理如下：

1. 您声明一大块虚拟内存。您可以申请 2GB 内存（即使在 1GB 机器上），因为它只是虚拟的，只有在您实际使用它时才会被提交。
2. 将块分割为 4KB 块，或其倍数（x86 处理器使用 4KB 块），并让索引数组开始指定是否已提交 4K 块。
3. 如果需要写入，请检查索引中该页面是否已提交，如果尚未提交，请提交。
4. 写入列表。
5. 如果需要读取，请检查索引，如果页面尚未提交，则没有命中，返回 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. 散列索引，这指向您的数组项。
3. 遍历链接列表，直到找到正确的项目。
4. 要插入项目：执行步骤 1 和 2，然后在开头插入项目。

这最适合具有非常随机索引的数据，碰撞变化很小。
成功与否很大程度上取决于您的哈希函数，它需要尽可能多地选择不同的数组条目，太多冲突，您将一直在同一个链表中行走。

链表数组的示例代码

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 个二叉树

1. 创建一个只有根的空树
2. 如果我们有一个项目要插入，使用索引中的位来遍历树（0 = 左分支，1 = 右分支）。
3. 遍历树时，在下面附加较高排名的索引，并在较高排名的索引之上插入较低排名的索引。 （重的物品沉到底部）。

使用二叉树的示例代码

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
科门、莱瑟森和Rivest：算法导论，第三章数据结构 ISBN 0-07-013143-0