Ускорение этапа сжатия в коде на Delphi: достижение сложности O(N)

Delphi , Базы данных , Сортировка и Фильтр

При работе с большими массивами данных, такими как в вопросе, где есть около 25610241024 элементов в массивах "значений" и "индексов", важно оптимизировать код для достижения наилучшей производительности. В данном случае, проблема заключается в том, что метод "Compress" имеет сложность O(N^2), что делает его медленным для больших массивов данных.

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

Ниже представлен пример кода на Object Pascal (Delphi), который реализует данный подход:

type
  TMyArray = class
  private
    FAllData: TArray<T>;
    FIndex: TArray<Integer>;
  public
    constructor Create(const AData: TArray<T>);
    procedure Compress(out CompressedValues: TArray<T>; out Index: TArray<Integer>);
  end;

constructor TMyArray.Create(const AData: TArray<T>);
begin
  SetLength(FAllData, Length(AData));
  Copy(AData[0], FAllData[0], Length(AData));
  SetLength(FIndex, Length(FAllData));
  for i:= 0 to High(FIndex) do
    FIndex[i]:= i;
  TArray.Sort<Integer>(FIndex, TDelegatedComparer<Integer>.Construct(
    function(const Left, Right: Integer): Integer
    begin
      if FAllData[Left] > FAllData[Right] then Exit(1);
      if FAllData[Left] < FAllData[Right] then Exit(-1);
      Result:= 0;
    end));
end;

procedure TMyArray.Compress(out CompressedValues: TArray<T>; out Index: TArray<Integer>);
const
  Equal = 0;
var
  i, Duplicate: Integer;
  Count: Integer;
  IndexEntry: Integer;
  OutIndex: TArray<Integer>;
begin
  Count:= 16*1024*1024;  //Start with something reasonable
  SetLength(CompressedValues, Count);
  SetLength(OutIndex, Length(FIndex));
  Duplicate:= 0;
  CompressedValues[0]:= FAllData[FIndex[0]];
  OutIndex[FIndex[0]]:= 0;
  for i:= 1 to High(FIndex) do
  begin
    if TComparer<T>.Default.Compare(FAllData[FIndex[i]], CompressedValues[Duplicate]) = Equal then
      OutIndex[FIndex[i]]:= Duplicate
    else
    begin
      Inc(Duplicate);
      //Grow as needed
      if (Duplicate >= Length(CompressedValues)) then SetLength(CompressedValues, Length(CompressedValues) + 1024*1024);
      CompressedValues[Duplicate]:= FAllData[FIndex[i]];
      OutIndex[FIndex[i]]:= Duplicate;
    end;
  end;
  Index:= OutIndex;
  SetLength(CompressedValues, Duplicate+1);
end;

Конструктор "Create" создает новый экземпляр TMyArray, инициализирует массив данных "FAllData" и массив индексов "FIndex". Массив индексов сортируется с помощью TArray.Sort, используя пользовательский сравнитель, который сравнивает элементы массива данных "FAllData".

Метод "Compress" сжимает массив данных и возвращает сжатый массив и новый массив индексов. Он использует тот же подход, что и в альтернативном ответе, но с некоторыми изменениями. В частности, он использует TComparer

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

Оптимизация этапа сжатия в коде на Delphi для достижения сложности O(N) при работе с большими массивами данных.

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

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

:: Главная :: Сортировка и Фильтр ::