Оптимизация отображения активных элементов в локальном массиве

Delphi , Базы данных , Индексы

В данной статье мы рассмотрим задачу отображения активных элементов из набора A, индексированного от [0, n], в локальный массив, где одновременно могут использоваться не более m элементов (0 <= m <= n). Элементы могут динамически деактивироваться во время выполнения программы, и их индексы должны быть переиспользованы при активации новых элементов. Цель состоит в том, чтобы отобразить индекс элемента на его локальный индекс в наиболее эффективном способе для быстрого поиска данных активного элемента.

Рассмотрим несколько подходов к решению этой задачи:

1. Простой массив + прямое хэширование
2. Массив с указателями на связанный список + хэш-связь с началом элемента
3. Двоичное дерево, где бит индекса определяет ветви дерева

1. Простой массив + прямое хэширование

Данный подход заключается в следующем:

a. Запросить большой блок виртуальной памяти. b. Разбить блок на 4КБ блоки (или кратные им) и создать индексный массив, указывающий, был ли 4КБ блок выделен. c. При записи проверить индексный массив, если страница не была выделена, выделить ее. d. При чтении проверить индексный массив, если страница не была выделена, значит, нет хита, вернуть false, иначе прочитать запись.

Этот метод работает лучше всего для данных, которые сгруппированы вблизи друг друга в пространстве. Если индексы случайны, этот метод будет неэффективным.

Пример кода на Object Pascal (Delphi):

type
  TElement = record
    Data: string;
    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 в 4КБ блоках
  BitsPerInt32 = 32;
  IndexCount = NumberOfBlocks div BitsPerInt32;

var
  IndexBlock: array[0..IndexCount-1]; //1 бит для каждого блока = 64КБ.

var
  Elements: PElements;

function ClaimVirtualBlock: PElements;
begin
  FillChar(IndexBlock, #0, SizeOf(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
  //Создать новый элемент в нашем списке
  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. Массив с указателями на связанный список + хэш-связь с началом элемента

Данный подход заключается в следующем:

a. Создать массив указателей на связанный список. b. Вычислить хэш индекса, который указывает на элемент массива. c. Пройти по связанному списку до тех пор, пока не будет найден правильный элемент. d. Для вставки элемента выполнить шаги 1 и 2, а затем вставить элемент в начало списка.

Этот метод работает лучше всего для данных с очень случайными индексами, с небольшим шансом столкновения. Успех этого метода во многом зависит от функции хэширования, она должна выбирать как можно больше разных элементов массива, слишком много "столкновений", и вы просто будете проходить один и тот же связанный список все время.

3. Двоичное дерево, где бит индекса определяет ветви дерева

Данный подход заключается в следующем:

a. Создать пустое дерево с корнем. b. Если есть элемент для вставки, использовать биты индекса для прохождения по дереву (0 = левая ветвь, 1 = правая ветвь). c. Во время прохождения по дереву добавлять вышестоящие индексы снизу и вставлять нижестоящие индексы выше вышестоящих (тяжелые элементы опускаются вниз).

Пример кода на Object Pascal (Delphi):

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;
  //Пройти по дереву
  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}

  //Вставить элемент здесь
  case Direction of
    GoLeft: PrevItem^.Left:= @Self;
    GoRight: PrevItem.Right:= @Self;
  end;

  //Что делать с текущим элементом.
  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;
  //Пройти по дереву
  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;

Выбор подхода к решению этой задачи зависит от характера данных и требуемой производительности. Каждый из рассмотренных методов имеет свои сильные и слабые стороны, и лучшим решением будет проанализировать конкретную ситуацию и выбрать наиболее подходящий подход.

Создано по материалам из источника по ссылке.

В статье рассматривается задача оптимизации отображения активных элементов в локальном массиве из набора индексированных элементов, где одновременно могут использоваться не более m элементов, с целью быстрого поиска данных активного эл

Комментарии и вопросы

Получайте свежие новости и обновления по Object Pascal, Delphi и Lazarus прямо в свой смартфон. Подпишитесь на наш Telegram-канал delphi_kansoftware и будьте в курсе последних тенденций в разработке под Linux, Windows, Android и iOS

:: Главная :: Индексы ::