Я бы хотел сопоставить индекс элемента с его локальным индексом наиболее эффективным способом
Нет такого понятия, как самый быстрый код (tanstatfc) - Майкл Абраш
Есть много решений вашей проблемы.
Первый шаг - выбрать структуру данных и хэш-функцию.
Структура данных может быть:
- Простой массив + прямой хеш
- Массив, содержащий начальный указатель на связанный список + хеш-связывание с начальным элементом
- Двоичное дерево, где хеш обозначает ветви дерева
- Я собираюсь на этом остановиться.
1 Простой массив
Это самое простое решение. И если ваши выделения выделены блобом (это означает, что они сгруппированы вместе в пространстве) , это может быть даже хорошим решением.
Вот как это работает:
- Вы претендуете на большой кусок виртуальной памяти. Вы можете требовать 2 ГБ памяти (даже на машине с 1 ГБ), потому что это всего лишь виртуальная память, которая будет зафиксирована только в том случае, если вы действительно ее используете.
- Разделите блок на блоки по 4 КБ, или их кратные (процессоры x86 используют блоки по 4 КБ) и заставьте индексный массив начать указывать, был ли зафиксирован блок 4 КБ.
- Если вам нужно написать, проверьте в индексе, была ли страница зафиксирована, если нет, зафиксируйте ее.
- Написать в список.
- Если вам нужно прочитать, проверьте индекс, если страница не была зафиксирована, попадания нет, верните false, иначе прочитайте запись.
В этой структуре можно разместить 2 ГБ / 4 байта на запись = 500 миллионов записей.
Это лучше всего подходит для данных, сгруппированных в кластеры, расположенные близко друг к другу.
Если индексы случайные, это будет неэффективно.
Вот псевдокод 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 и вставьте элемент в начале.
Это лучше всего подходит для данных с очень случайным индексом, с небольшим изменением коллизий.
Успех в решающей степени зависит от вашей хэш-функции, ему нужно выбрать как можно больше другой записи массива, слишком много 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 = правая ветвь).
- При обходе дерева добавляйте индексы с более высоким рейтингом ниже и вставляйте индексы с более низким рейтингом выше индексов с более высоким рейтингом. (Тяжелые предметы опускаются на дно).
Пример кода с использованием двоичного дерева
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;
Рекомендовать читать:
Кнут: TAOCP I: фундаментальные алгоритмы, глава 2 ISBN 0-201-03809-9
Cormen, Leiserson & Rivest: Введение в алгоритмы, глава III Структуры данных ISBN 0-07-013143-0