Удаление дубликатов из массива

[alcaedo]

Пока опробовал только 2 способа:

1) Функция. Создаётся массив такого-же размера, как исходный, типа boolean.
Исходный массив пробегается от начала к концу. Внутренний цикл от (начала+1) к концу. Если повтор, то в boolean-массиве ставится отметка об удалении элемента по индексу внешнего цикла, а внутренний цикл прерывается (break).
В конце элементы из исходного массива переносятся в Result, учитывая отметки в boolean-массиве.

2) Процедура, принимающая указатель на исходный массив.
Исходный массив пробегается от начала к концу. Внутренний цикл от (начала+1) к концу. Если встретился повтор, то самый последний элемент массива перемещается на место повторяющегося, а размер самого массива уменьшается. После переноса внутренний цикл продолжается с того же самого места, где встретился повтор, ведь перенесённый с конца элемент тоже может оказаться дубликатом.

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

Поделитесь опытом, может есть способы быстрее. Читал, что из отсортированного массива легче удалять дубли, но не проверял на скорость. Не окажется ли, что сортировка займёт слишком много времени?

[Аватар]

А сравнить? Да и сортировки разные бывают, значит проверить несколько вариантов сортировки. А так просто наобум ни кто не скажет

[alcaedo]

Задача не редкая. Должны же найтись люди, которые уже сравнили.

[evg_m]

Задача не редкая. Должны же найтись люди, которые уже сравнили.

Да, например вот ОН.

[JUDAS]

type
  TArray = array of double;



procedure DeleteDuplicate(var A : TArray);
var i,j,count: integer;
begin
  count := High(A);
  for i:=0 to Count do
  begin
    j:=i+1;
    repeat
      if A[i] = A[j] then
      begin
        A[j] := A[count];
        SetLength(A, Count);
        count := High(A);
      end else
      inc(j);
    until j>Count;
  end;
end;

[alcaedo]

JUDAS, так это тоже, что у меня второй вариант.

[Аватар]

размер самого массива уменьшается

Физический размер массива уменьшить один раз в самом конце, а в циклах работать с логическим размером. SetLength очень медленная

[JUDAS]

Сообщение от Аватар

Физический размер массива уменьшить один раз в самом конце, а в циклах работать с логическим размером. SetLength очень медленная

Можно и так.

Автор, я думал что нужна реализация, а не варианты
3. Перенос уникальный объектов в другой массив. Входная длина запоминается в переменную. Проходя по исходному массиву, ищем уникальные значения во втором массиве. Если таковых нет, в конец результирующего массива добавляем текущий элемент.

[SQLPowerUser]

Когда-то находил https://rsdn.ru/forum/delphi/3437315

[alcaedo]

Думаю, можно в этой же теме написать.
Вот есть процедура:

procedure _DupDelete(var SL:TArrayOfSome32ByteType);
var Hsl,N1,N2:int64;
begin
  Hsl:=high(SL);
  N1:=0;
  while N1<Hsl do
    begin
      N2:=N1+1;
      while N2<=Hsl do
        begin
          if SL[N1]=SL[N2] then
            begin
              SL[N2]:=SL[Hsl];
              dec(Hsl);
            end
            else inc(N2);
        end;
      inc(N1);
    end;
  setlength(SL,Hsl+1);

Пытаюсь переписать её на ассемблере. Не могу разобраться, что именно и как лучше передавать в процедуру. Вроде как надо бы передать адрес элемента с индексом 0, проверив предварительно, что массив не пустой. Или лучше передать просто массив? Или адрес массива?

// использование: SelLength(Massiv,_DupDeleteAsm(addr(Massiv[0])))
function _DupDeleteAsm(SL0:PSome32ByteType):int64;
asm
                                // RAX = Hsl
                                // RBX = N2
                                // RCX = SL
                                // RDX = N1
                                // R8 - для сравнения
                                // R8 и R9 - для пересылки 32 байт
        XOR     RAX,RAX
        TEST    SL0,SL0           // вот тут, возможно, надо проверять массив на nil, если передан сам массив
        JZ      @empty_array     // если массив nil, то выход и возврат RAX:=0
        MOV     RAX,[SL0-8]-1     // Hsl:=high(SL)
        SHL     RAX,5             // в RAX смещение от начала массива
        XOR     RDX,RDX           // N1:=0
  @while01:
        CMP     RDX,RAX           // while N1<Hsl do
        JAE     @finish
        MOV     RBX,RDX           // N2:=N1+1;
        ADD     RBX,32            // в RBX смещение от начала массива
  @while02:
        CMP     RBX,RAX           // while N2<=Hsl do
        JA      @end_of_array
        MOV     R8,[SL0+RDX]      // if SL[N1]=SL[N2] then ...
        CMP     R8,[SL0+RBX]
        JNE     @notEq
        MOV     R8,[SL0+RDX+8]
        CMP     R8,[SL0+RBX+8]
        JNE     @notEq
        MOV     R8,[SL0+RDX+16]
        CMP     R8,[SL0+RBX+16]
        JNE     @notEq
        MOV     R8,[SL0+RDX+24]
        CMP     R8,[SL0+RBX+24]
        JNE     @notEq
                                  // ... then SL[N2] := SL[Hsl]
        MOV     R9,RCX
        ADD     R9,RAX
        FILD    QWORD PTR [R9]    // Load First 8
        FILD    QWORD PTR [R9+8]  // Load Second 8
        MOV     R8,RCX
        ADD     R8,RBX
        FXCH
        FISTP   QWORD PTR [R8]    // Save First 8
        FISTP   QWORD PTR [R8+8]  // Save Second 8
        FILD    QWORD PTR [R9+16] // Load Third 8
        FILD    QWORD PTR [R9+24] // Load Last 8
        FXCH
        FISTP   QWORD PTR [R8+16] // Save Third 8
        FISTP   QWORD PTR [R8+24] // Save Last 8
        SUB     RAX,32            // dec(Hsl), в RAX смещение от начала массива
        JMP     @while02
  @notEq:
        ADD     RBX,32            // inc(N2), в RBX смещение от начала массива
        JMP     @while02
  @end_of_array:
        ADD     RDX,32            // inc(N1), в RDX смещение от начала массива
        JMP     @while01
  @finish:
        SHR     RAX,5             // теперь в RAX количество элементов, а не смещение
        INC     RAX
  @empty_array:
end;

Считаю, удобнее, если функция будет возвращать только размер массива, а само обрезание будет уже в той процедуре, которая вызвала _DupDeleteAsm, по мере надобности