映射两组元素

Question

有一组元素索引为0，n。在任何时候，A集合中最多有m个元素可以是活动的(在使用中)，一个明显的条件是0 <= m <= n。我想在一个局部数组中索引那些活动的元素。一个元素可以在程序执行时动态停用，我希望当新的元素被激活时，它的索引可以被重用。

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

简单散列函数(元素索引、==局部索引)和暴力强制通过关联列表的可能解决方案不能很好地扩展到较大的n。

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

谢谢

Answer 1

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

没有最快的代码(tanstatfc) -- Michael Abrash

你的问题有很多解决方案。

第一步是选择数据结构和散列函数。

数据结构可以是：

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

1普通阵列

这是最简单的解决方案。如果您的分配是杂乱无章的(这意味着它们在空间中聚集在一起)，这甚至可能是一个很好的解决方案。

下面是它的工作原理：

1. 您需要一大块虚拟内存。你可以要求2 1GB的内存(即使是在1 1GB的机器上)，因为它只是虚拟的，只有当你实际使用它时才会提交。
2. 将数据块拆分为4KB的块，或其倍数块(处理器使用4KB块)，并创建索引数组开始指定是否已写入4K块，如果页面已提交，则检查索引，如果尚未提交，则提交它。
3. 写入列表。
4. 如果需要读取，请检查索引，如果页面尚未提交，则返回false，否则读取条目。

<>G229>

您可以在此结构中容纳2 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，并在开头插入项。

这对于具有非常随机索引的数据效果最好，碰撞的变化很小。

成功与否关键取决于你的散列函数，它需要尽可能多地选择一个不同的数组条目，太多的collisions，你就会一直在遍历相同的链表。

链表数组的示例代码

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=右branch).

• Whilst遍历树)，在下面附加较高排序的索引，并在较高排序的索引之上插入较低排序的索引。如果我们有要插入的项，则使用

1. 创建一个仅具有根
2. 的空树。(重物下沉到底部)。

使用二叉树的示例代码

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