sorting - 如何在删除重复项的同时执行排序+索引?
问题描述
我使用以下代码对项目和索引进行排序:values
andindex
数组中大约有 256*1024*1024 个条目。
未压缩的values
数组占用大约 10GB,这就是为什么我想通过将有很多重复值组合在一起来压缩它的原因。
我提出了以下概念验证代码,但Compress
方法存在问题。每次找到重复项时,它都会在索引中执行一次搜索,这会花费 O(N 2 ) 时间。
我需要保留一个索引,因为我需要能够访问数组中的元素,就好像没有发生重复数据删除一样。
这是使用简单的default
属性数组属性完成的,因此模仿了原始数组:
function TLookupTable.GetItems(Index: integer): TSlice;
begin
Result:= FData[FIndex[Index]];
end;
概念证明代码(狗慢)如下。
TMyArray = class
class procedure QuickSort<T,Idx>(var Values: array of T; var Index: array of Idx; const Comparer: IComparer<T>;
L, R: Integer);
class procedure Compress<T>(const Values: array of T; var Index: array of Integer; out CompressedValues: TArray<T>; const Comparer: IComparer<T>);
end;
class procedure TMyArray.QuickSort<T,Idx>(var Values: array of T; var Index: array of Idx; const Comparer: IComparer<T>;
L, R: Integer);
var
I, J: Integer;
pivot, temp: T;
TempIdx: Idx;
begin
if (Length(Values) = 0) or ((R - L) <= 0) then
Exit;
repeat
I := L;
J := R;
pivot := Values[L + (R - L) shr 1];
repeat
while Comparer.Compare(Values[I], pivot) < 0 do Inc(I);
while Comparer.Compare(Values[J], pivot) > 0 do Dec(J);
if I <= J then begin
if I <> J then begin
temp := Values[I];
Values[I] := Values[J];
Values[J] := temp;
//Keep the index in sync
tempIdx := Index[I];
Index[I] := Index[J];
Index[J] := tempIdx;
end;
Inc(I);
Dec(J);
end;
until I > J;
if L < J then QuickSort<T,Idx>(Values, Index, Comparer, L, J);
L := I;
until I >= R;
end;
class procedure TMyArray.Compress<T>(const Values: array of T; var Index: array of integer; out CompressedValues: TArray<T>; const Comparer: IComparer<T>);
var
i,j: integer;
Count: integer;
Duplicate: integer;
begin
Count:= 256*1024*1024;
SetLength(CompressedValues, Count);
CompressedValues[0]:= Values[0];
Duplicate:= 0;
for i := 1 to High(Values) do begin
//Compress duplicate values
if Comparer.Compare(Values[i], CompressedValues[Duplicate]) = 0 then begin
//Search for the indexed item
//Very time consuming: O(N*N)
for j:= i to High(Index) do if Index[j] = i then begin
Index[j]:= Duplicate; //Fix up the index
Break;
end; {for j}
end else begin
Inc(Duplicate);
if Duplicate >= Count then begin
Inc(Count, 1024*1024);
SetLength(CompressedValues, Count);
end;
CompressedValues[Duplicate]:= Values[i];
end;
end; {for i}
SetLength(CompressedValues, Duplicate+1)
end;
如何加快压缩步骤以使其花费 O(N) 时间?
如果有一种方法可以同时保留索引并删除重复项和排序,那就太好了。我在下面的回答将排序和重复数据删除分为两个单独的阶段。
解决方案
诀窍是不理会原始数据数组,只对索引进行排序。然后,我们可以利用原始数据的顺序正确这一事实,并使用它来构建新索引。
此外,这意味着我们不再需要自定义Sort
函数;它还移动了更少的数据。
像这样创建索引:
FIndex: TArray<integer>;
....
SetLength(FIndex, Length(FAllData));
for i:= 0 to count-1 do begin
FIndex[i]:= i;
end;
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));
像这样更改 TMyArray 类:
TMyArray = class
class procedure Compress<T>(const Values: array of T; var Index: TArray<integer>; out CompressedValues: TArray<T>; const Comparer: IComparer<T>);
end;
class procedure TMyArray.Compress<T>(const Values: array of T; var Index: TArray<integer>; out CompressedValues: TArray<T>; const Comparer: IComparer<T>);
const
Equal = 0;
var
i,j: integer;
Count: integer;
Duplicate: integer;
IndexEntry: integer;
OutIndex: TArray<integer>;
begin
Count:= 16*1024*1024; //Start with something reasonable
SetLength(CompressedValues, Count);
SetLength(OutIndex, Length(Index));
Duplicate:= 0;
CompressedValues[0]:= Values[Index[0]];
OutIndex[Index[0]]:= 0;
for i:= 1 to High(Index) do begin
if Comparer.Compare(Values[Index[i]], CompressedValues[Duplicate]) = Equal then begin
OutIndex[Index[i]]:= Duplicate;
end else begin
Inc(Duplicate);
//Grow as needed
if (Duplicate >= Length(CompressedValues)) then SetLength(CompressedValues, Length(CompressedValues) + 1024*1024);
CompressedValues[Duplicate]:= Values[Index[i]];
OutIndex[Index[i]]:= Duplicate;
end;
end;
Index:= OutIndex;
SetLength(CompressedValues, Duplicate+1);
end;
推荐阅读
- c - C - 消除循环口吃?
- mysql - sql查询错误#语法
- python - 如何使用 conda 或 virtualenv 在虚拟环境之间共享包?
- python-3.x - Matplotlib imshow() 不显示 numpy.ones 数组
- dart - 扩展 Flutter 应用的基类
- alexa - Alexa 模拟器“挂起”
- javascript - 动态创建同一组件的多个实例。
- android - Firebase SHA1-Certificate 已被另一个应用程序使用
- jupyter-notebook - 修改 Jupyter 主目录的问题
- uwp - 具有广泛文件系统访问权限的无效 XML 清单