Print Page - Removing duplicates from an array

Free Pascal => General => Topic started by: BillMcEnaney on May 19, 2022, 07:07:24 pm

Title: Removing duplicates from an array
Post by: BillMcEnaney on May 19, 2022, 07:07:24 pm

Hi, everyone,

Here's my Pascal function to remove duplicates from a list stored in an array. Please forgive me for any FPC-related mistakes because I'm used to ANSI Standard Pascal.

Here are the type and constant declarations for the program.

const
Capacity = 80;

type
Index_Range = 0..Capacity;
Element_Tupe = integer;
List = array[Index_Range] of Element_Type;

Code: [Select]

function Remove_Duplicates(Table: List; Table_Length: Index_Range): List;
   var
      Result: List;
      Here, There: Index_Range;
      Duplicates: set of Element_Type;
   begin
      There := 1;
      for Here ::= 1 to Table_Length do
         if Table[Here] not in Duplicates
         then
            begin
               include(Duplicates, Table[Here]);
               Result[There] := Table[Here];
               There := succ(There)
            end;
         if Duplicates = []
            then Result := Table;
        Remove_Duplicates := Result
   end;

The compiler made my laptop complain about the if-statement until I changed Element_Type to 0..5. So I wonder whether the set of integers between 1 and MaxInt is too big to represent with a Pascal set. Am I right about that?

I could overwrite duplicates in the original list. But I use the set and the result list to speed up the function.

Title: Re: Removing duplicates from an array
Post by: howardpc on May 19, 2022, 11:38:45 pm

Quote from: BillMcEnaney on May 19, 2022, 07:07:24 pm

So I wonder whether the set of integers between 1 and MaxInt is too big to represent with a Pascal set. Am I right about that?

You wonder correctly. FPC sets are limited to Byte range ordinals (0..255).
There are generics libraries that offer sets with greater ranges and more functionalities (e.g. a set Count property) than the built-in FPC set implementation.
For instance see here (https://github.com/avk959/LGenerics) .

Title: Re: Removing duplicates from an array
Post by: BobDog on May 20, 2022, 07:17:14 pm

Is this it in fp maybe?

Code: Pascal [Select][+]

 
const
   Capacity = 255;
 
type
   Index_Range = 0..Capacity;
   Element_Type = integer;
   List = array[Index_Range] of Element_Type;
   aod= array of Element_Type;
   
   function Remove_Duplicates(Table: List; Table_Length: Index_Range):aod;
   var
      Result:array of Element_type;// 
     
      Here, There: Index_Range;
      Duplicates:set of index_range;
   begin
    setlength(result,capacity);
    Duplicates:=[0];
      There := 1;
      for Here := 1 to Table_Length do
         if (Table[Here] in Duplicates) =false then
         
            begin
               include(Duplicates, Table[Here]);
               Result[There] := Table[Here];
               There := succ(There)
            end;
         if Duplicates = []
            then Result := Table;
            setlength(result,There);
        Remove_Duplicates := Result
   end;
   
   
  function range(mymin:int32;mymax:int32):int32;
   begin
   range:=trunc(int((Random*(Mymax-mymin+1)))+MyMin);
  end; 
 
   
   
   var
   i:integer;
   table:List;
   answer:aod;
   begin
   for i:=0 to high(table) do table[i]:=range(100,110);
   writeln('Before:');
   for i:=0 to high(table) do write(table[i],' ');
   answer:=Remove_Duplicates(table,high(table));
   writeln;
   writeln('After:');
   for i:=1 to high(answer) do write(answer[i],' ');
   writeln;
   writeln('Press return to end');
   readln;
   end.
 
 

And my attempt, keeping the order and using dynamic arrays and template (generics), but not sets.

Code: Pascal [Select][+]

 
generic function CleanUp<T>(a:T):T;
var
 n1,n2,flag:int32;
 count:int32=1;
 ret:T;
begin
  setlength(ret,high(a));
  ret[0]:=a[0];
  For n1 :=1 To high(a) do
  begin
   flag:=0;
   For n2 :=0 to  n1-1 do
    begin
    If (a[n1]=a[n2]) Then 
     begin
      flag:=1;
      break;
      end;
     end;
 If (flag=0) Then
    begin
     ret[count]:=a[n1];
     count:=count+1;
    end;
 end;
 setlength(ret,count);
 exit(ret);
end;
 
 function range(mymin:int32;mymax:int32):int32;
   begin
   range:=trunc(int((Random*(Mymax-mymin+1)))+MyMin);
  end; 
 
 
type aoi=array of int32;
type aos=array of char;
var ans:aoi=nil;
var ret:aos=nil;
var j:int32;
var i:aoi;
var s:aos;
 
begin
setlength(i,255);
for j:=0 to high(i) do i[j]:=range(100,110);
writeln('Before:');
for j:=low(i) to high(i) do write(i[j],' ');
writeln;
writeln('After:');
ans:=specialize CleanUp<aoi>(i);
for j:=low(ans) to high(ans) do write(ans[j],' ');
writeln;
writeln;
writeln;
setlength(s,50);
for j:=0 to high(s) do if range(1,10)>5 then s[j]:=chr(range(65,90)) else s[j]:=chr(range(97,122));//s[j]:=range
writeln('Before:');
for j:=low(s) to high(s) do write(s[j],' ');
writeln;
writeln('After:');;
ret:=specialize CleanUp<aos>(s);
for j:=low(ret) to high(ret) do write(ret[j],' ');
writeln;
writeln('Press return to end');
readln;
 
end.
 
 
 

Title: Re: Removing duplicates from an array
Post by: 440bx on May 20, 2022, 07:57:27 pm

Just a suggestion, while sets in FPC are limited to 256 elements, bitpacked arrays of boolean are not.

That would allow creating a bitmap of duplicates to be used to remove them in a subsequent pass.

Title: Re: Removing duplicates from an array
Post by: avk on May 23, 2022, 12:26:19 pm

The bitmap for the above range (1..MaxInt) must be at least 2²⁸ bytes in size and must be initialized.
It doesn't look very practical, does it?

Title: Re: Removing duplicates from an array
Post by: Warfley on May 23, 2022, 12:50:38 pm

Using (bit)sets is not a real alternative for large value ranges. The alternative by BobDog is inplace, but has complexity of O(n²) and is therefore quite slow.
Therefore I would suggest as an alternative, to use a dynamic set datastructure, either a hashset, which has an average lookup complexity of O(1) or a sorted set (e.g. RBT) which has a lookup time of O(logn), but the advantage of being easiely pre allocatable.

E.g.

Code: Pascal [Select][+]

uses
  Generics.Collections;
 
type
  TIntArray = array of Integer;
  TIntSet = specialize THashSet<Integer>;
 
function RemoveDublicates(Data: TIntArray): TIntArray;
var
  Visited: TIntSet;
  WriteHead: SizeInt;
  Elem: Integer;
begin
  SetLength(Result, Length(Data));
  WriteHead := 0;
  Visited := TIntSet.Create;
  try
    for Elem in Data do
      if not Visited.Contains(Elem) then
      begin
        Result[WriteHead] := Elem;
        Inc(WriteHead);
        Visited.Add(Elem);
      end;
  finally
    Visited.Free;
  end;
  SetLength(Result, WriteHead);
end;
 
var
  Data: Array of Integer = (5,2,1,3,5,2,3,4,1,2);
  Elem: Integer;
begin
  Data := RemoveDublicates(Data);
  for Elem in Data do
    WriteLn(Elem);
  ReadLn;
end.

With a hash set the average runtime complexity of this function should be O(n), and therefore quite efficient, while not blowing up the memory consumption like a bitset would

Title: Re: Removing duplicates from an array
Post by: 440bx on May 23, 2022, 01:18:17 pm

Quote from: avk on May 23, 2022, 12:26:19 pm

The bitmap for the above range (1..MaxInt) must be at least 2²⁸ bytes in size and must be initialized.
It doesn't look very practical, does it?

You got that right, I didn't say it was a small set :D but even a 32 bit process can afford the (approx) 260MB it will take.

I think the really critical part is the number of elements in the array. For a large number of elements, 2 or 3 hundred thousand+, it might be reasonable to temporarily have a bitmap that large. Honestly, I don't know where the cut-off is but, for smaller counts, I have no doubt there are smaller and faster ways.

Title: Re: Removing duplicates from an array
Post by: BobDog on May 23, 2022, 05:36:22 pm

Quote from: Warfley on May 23, 2022, 12:50:38 pm

Using (bit)sets is not a real alternative for large value ranges. The alternative by BobDog is inplace, but has complexity of O(n²) and is therefore quite slow.
Therefore I would suggest as an alternative, to use a dynamic set datastructure, either a hashset, which has an average lookup complexity of O(1) or a sorted set (e.g. RBT) which has a lookup time of O(logn), but the advantage of being easiely pre allocatable.

E.g.
Code: Pascal [Select][+][-]
uses
Generics.Collections;

type
TIntArray = array of Integer;
TIntSet = specialize THashSet<Integer>;

function RemoveDublicates(Data: TIntArray): TIntArray;
var
Visited: TIntSet;
WriteHead: SizeInt;
Elem: Integer;
begin
SetLength(Result, Length(Data));
WriteHead := 0;
Visited := TIntSet.Create;
try
for Elem in Data do
if not Visited.Contains(Elem) then
begin
Result[WriteHead] := Elem;
Inc(WriteHead);
Visited.Add(Elem);
end;
finally
Visited.Free;
end;
SetLength(Result, WriteHead);
end;

var
Data: Array of Integer = (5,2,1,3,5,2,3,4,1,2);
Elem: Integer;
begin
Data := RemoveDublicates(Data);
for Elem in Data do
WriteLn(Elem);
ReadLn;
end.
With a hash set the average runtime complexity of this function should be O(n), and therefore quite efficient, while not blowing up the memory consumption like a bitset would

Here are the results for 10 million elements.

BobDog
1250 milliseconds
1055 1059 1072 1085 1060 1086 1042 1062 1065 1038 1044 1030 1090 1005 1097 1027 1048 1079 1082 1053 1057 1039 1093 1084 1007 1034 1008 1002 1037 1096 1078 1014 1087 1098 1047 1080 1046 1052 1068 1011 1064 1058 1054 1095 1076 1010 1041 1026 1018 1074 1021 1013 1001 1032 1015 1061 1022 1091 1045 1036 1070 1006 1067 1017 1075 1031 1003 1099 1016 1100 1025 1024 1066 1019 1009 1088 1051 1028 1012 1029 1069 1092 1000 1040 1083 1071 1043 1077 1089 1073 1050 1023 1035 1081 1049 1020 1094 1063 1004 1056 1033

Warfley
219 milliseconds
1055 1059 1072 1085 1060 1086 1042 1062 1065 1038 1044 1030 1090 1005 1097 1027 1048 1079 1082 1053 1057 1039 1093 1084 1007 1034 1008 1002 1037 1096 1078 1014 1087 1098 1047 1080 1046 1052 1068 1011 1064 1058 1054 1095 1076 1010 1041 1026 1018 1074 1021 1013 1001 1032 1015 1061 1022 1091 1045 1036 1070 1006 1067 1017 1075 1031 1003 1099 1016 1100 1025 1024 1066 1019 1009 1088 1051 1028 1012 1029 1069 1092 1000 1040 1083 1071 1043 1077 1089 1073 1050 1023 1035 1081 1049 1020 1094 1063 1004 1056 1033

array of length 10000000 with range(1000,1100) each element

Title: Re: Removing duplicates from an array
Post by: avk on May 24, 2022, 03:46:10 pm

Quote from: 440bx on May 23, 2022, 01:18:17 pm

...
I think the really critical part is the number of elements in the array. For a large number of elements, 2 or 3 hundred thousand+, it might be reasonable to temporarily have a bitmap that large. Honestly, I don't know where the cut-off is but, for smaller counts, I have no doubt there are smaller and faster ways.

It is possible to try to roughly estimate the effect of range size and array length on performance.
I am used LGenerics on a Win64 machine:

Code: Pascal [Select][+]

program proj;
 
{$mode objfpc}{$h+}
{$modeswitch advancedrecords}
{$maxstacksize $40000000}
 
uses
  SysUtils, Math, lgUtils, lgHashSet, lgHash, lgTreeSet;
 
var
  ArrayLen: Integer = 10000;
  RepCount: Integer = 1000;
 
const
  TryCount = 5;
 
type
  THelper = record
    class function HashCode(aValue: DWord): SizeInt; static; inline;
    class function Equal(L, R: DWord): Boolean; static; inline;
  end;
 
  generic TRangeTest<const UpBound: Integer> = record
  const
    UPPER = UpBound or Ord(UpBound = 0);
 
  type
    TElType           = 1..UPPER;
    TElArray          = array of TElType;
    TRemoveDuplicates = function(const a: array of TElType): TElArray;
 
    TTestFun = record
      Fun: TRemoveDuplicates;
      DisplayText: string;
    end;
 
    TBitSet      = specialize TGSet<TElType>;
    THashSetType = specialize TGLiteChainHashSet<TElType, THelper>;
    THashSet     = THashSetType.TSet;
    TTreeSet     = specialize TGLiteTreeSet<TElType, DWord>;
 
    class function  BitSet(const a: array of TElType): TElArray; static;
    class function  HashSet(const a: array of TElType): TElArray; static;
    class function  TreeSet(const a: array of TElType): TElArray; static;
    class procedure Execute; static;
  end;
 
class function THelper.HashCode(aValue: DWord): SizeInt;
begin
  Result := JdkHash(aValue);
end;
 
class function THelper.Equal(L, R: DWord): Boolean;
begin
  Result := L = R;
end;
 
class function TRangeTest.BitSet(const a: array of TElType): TElArray;
var
  s: TBitSet;
  I, J: SizeInt;
begin
  SetLength(Result, Length(a));
  J := 0;
  for I := 0 to High(a) do
    begin
      if a[I] in s then continue;
      s.Include(a[I]);
      Result[J] := a[I];
      Inc(J);
    end;
  SetLength(Result, J);
end;
 
{$warn 5089 off}
class function TRangeTest.HashSet(const a: array of TElType): TElArray;
var
  s: THashSet;
  I, J: SizeInt;
begin
  s.EnsureCapacity(Min(Ord(High(TElType)) - Ord(Low(TElType)) + 1, Length(a)));
  SetLength(Result, Length(a));
  J := 0;
  for I := 0 to High(a) do
    if s.Add(a[I]) then
      begin
        Result[J] := a[I];
        Inc(J);
      end;
  SetLength(Result, J);
end;
 
class function TRangeTest.TreeSet(const a: array of TElType): TElArray;
var
  s: TTreeSet;
  I, J: SizeInt;
begin
  s.EnsureCapacity(Min(Ord(High(TElType)) - Ord(Low(TElType)) + 1, Length(a)));
  SetLength(Result, Length(a));
  J := 0;
  for I := 0 to High(a) do
    if s.Add(a[I]) then
      begin
        Result[J] := a[I];
        Inc(J);
      end;
  SetLength(Result, J);
end;
 
class procedure TRangeTest.Execute;
var
  a, u: TElArray;
  CurrFun: TTestFun;
  I, J: SizeInt;
  BestScore, Score: QWord;
const
  TestFuns: array of TTestFun = (
    (Fun: @BitSet;  DisplayText: '    BitSet:  '),
    (Fun: @HashSet; DisplayText: '    HashSet: '),
    (Fun: @TreeSet; DisplayText: '    TreeSet: ')
  );
begin
  WriteLn('  Subrange: 1..', UPPER);
  SetLength(a, ArrayLen);
  for I := 0 to High(a) do
    a[I] := Random(UPPER) + 1;
 
  for CurrFun in TestFuns do
    begin
      BestScore := High(QWord);
      for I := 1 to TryCount do
        begin
          Score := GetTickCount64;
          for J := 1 to RepCount do
            u := CurrFun.Fun(a);
          Score := GetTickCount64 - Score;
          if Score < BestScore then
            BestScore := Score;
        end;
      WriteLn(CurrFun.DisplayText, BestScore);
    end;
end;
 
procedure RunTest;
begin
  WriteLn('Array length: ', ArrayLen);
  specialize TRangeTest<1024>.Execute;
  specialize TRangeTest<65536>.Execute;
  specialize TRangeTest<4194304>.Execute;
  specialize TRangeTest<268435456>.Execute;
  specialize TRangeTest<2147483647>.Execute;
  WriteLn;
end;
 
begin
  RunTest;
  ArrayLen := 50000; RepCount := 200;
  RunTest;
  ArrayLen := 200000; RepCount := 50;
  RunTest;
  ArrayLen := 1000000; RepCount := 10;
  RunTest;
  ArrayLen := 5000000; RepCount := 2;
  RunTest;
  ReadLn;
end.
 

And I got something like this:

Code: Text [Select][+]

Array length: 10000
  Subrange: 1..1024
    BitSet:  0
    HashSet: 78
    TreeSet: 655
  Subrange: 1..65536
    BitSet:  15
    HashSet: 171
    TreeSet: 1342
  Subrange: 1..4194304
    BitSet:  124
    HashSet: 156
    TreeSet: 1388
  Subrange: 1..268435456
    BitSet:  10484
    HashSet: 156
    TreeSet: 1372
  Subrange: 1..2147483647
    BitSet:  80138
    HashSet: 171
    TreeSet: 1373
 
Array length: 50000
  Subrange: 1..1024
    BitSet:  0
    HashSet: 78
    TreeSet: 608
  Subrange: 1..65536
    BitSet:  46
    HashSet: 343
    TreeSet: 1684
  Subrange: 1..4194304
    BitSet:  47
    HashSet: 374
    TreeSet: 1919
  Subrange: 1..268435456
    BitSet:  2231
    HashSet: 374
    TreeSet: 1918
  Subrange: 1..2147483647
    BitSet:  16177
    HashSet: 374
    TreeSet: 1918
 
Array length: 200000
  Subrange: 1..1024
    BitSet:  0
    HashSet: 78
    TreeSet: 608
  Subrange: 1..65536
    BitSet:  31
    HashSet: 203
    TreeSet: 1638
  Subrange: 1..4194304
    BitSet:  31
    HashSet: 592
    TreeSet: 2777
  Subrange: 1..268435456
    BitSet:  718
    HashSet: 592
    TreeSet: 2823
  Subrange: 1..2147483647
    BitSet:  4227
    HashSet: 592
    TreeSet: 2808
 
Array length: 1000000
  Subrange: 1..1024
    BitSet:  0
    HashSet: 78
    TreeSet: 608
  Subrange: 1..65536
    BitSet:  15
    HashSet: 141
    TreeSet: 1622
  Subrange: 1..4194304
    BitSet:  47
    HashSet: 795
    TreeSet: 4836
  Subrange: 1..268435456
    BitSet:  312
    HashSet: 826
    TreeSet: 5070
  Subrange: 1..2147483647
    BitSet:  1046
    HashSet: 826
    TreeSet: 5070
 
Array length: 5000000
  Subrange: 1..1024
    BitSet:  0
    HashSet: 78
    TreeSet: 593
  Subrange: 1..65536
    BitSet:  15
    HashSet: 140
    TreeSet: 1591
  Subrange: 1..4194304
    BitSet:  62
    HashSet: 717
    TreeSet: 6489
  Subrange: 1..268435456
    BitSet:  234
    HashSet: 889
    TreeSet: 7628
  Subrange: 1..2147483647
    BitSet:  405
    HashSet: 889
    TreeSet: 7613  
 

Title: Re: Removing duplicates from an array
Post by: 440bx on May 24, 2022, 05:08:22 pm

Quote from: avk on May 24, 2022, 03:46:10 pm

It is possible to try to roughly estimate the effect of range size and array length on performance.

Thank you @avk.

From the results you posted I'd estimate the threshold to be in the vicinity of 2 million elements. That's quite a bit more than I than initially thought.

That really shows the value of testing off-the-cuff estimates :)

Title: Re: Removing duplicates from an array
Post by: Thaddy on May 29, 2022, 08:14:14 am

Note OP's capacity is 81, not 80...

Title: Re: Removing duplicates from an array
Post by: circular on May 29, 2022, 08:59:14 am

Another approach is to sort the array. Then it is easy to remove the duplicates with a loop, by having a second index that progress only when a new value is found and where it is copied to. This can be done inplace. In the end set the length of the array of the number of distinct items found.

Title: Re: Removing duplicates from an array
Post by: Thaddy on May 29, 2022, 01:31:20 pm

Another approach is using generics.collections and TArray<T>. And indeed it needs to sort, which it can.
That should be a two liner with the correct TDuplicates for TList<T>
Not tested (yet) but it should work.

The magic is in combining the array and the list.

Title: Re: Removing duplicates from an array
Post by: avk on May 29, 2022, 02:45:53 pm

Quote from: circular on May 29, 2022, 08:59:14 am

Another approach is to sort the array. Then it is easy to remove the duplicates with a loop, by having a second index that progress only when a new value is found and where it is copied to. This can be done inplace. In the end set the length of the array of the number of distinct items found.

Of course, in LGenerics the T(some)ArrayHelper.SelectDistinct() method does exactly that, but this method does not preserve the order of the elements in the array.

Title: Re: Removing duplicates from an array
Post by: BobDog on May 30, 2022, 03:13:33 pm

Quote from: Thaddy on May 29, 2022, 01:31:20 pm

Another approach is using generics.collections and TArray<T>. And indeed it needs to sort, which it can.
That should be a two liner with the correct TDuplicates for TList<T>
Not tested (yet) but it should work.

The magic is in combining the array and the list.

Anyway, it is too slow to sort the elements in a large array.
I tested with quicksort, the sort time taken is about the total task time taken in my previous method, then you have to remove the duplicates, easy enough in a sorted array.
I didn't bother making a remove procedure, it wasn't worth it.

Title: Re: Removing duplicates from an array
Post by: avk on May 30, 2022, 05:59:15 pm

Quote from: BobDog on May 30, 2022, 03:13:33 pm

...
Anyway, it is too slow to sort the elements in a large array.
I tested with quicksort, the sort time taken is about the total task time taken in my previous method, then you have to remove the duplicates, easy enough in a sorted array.
I didn't bother making a remove procedure, it wasn't worth it.

It seems your conclusion is too hasty.
I tried running TGOrdinalArrayHelper.SelectDistinct (denoted Sorting) in the benchmark from my post #8 and got the following timings:

Code: Text [Select][+]

Array length: 10000
  Subrange: 1..1024
    Sorting: 47
  Subrange: 1..65536
    Sorting: 78
  Subrange: 1..4194304
    Sorting: 94
  Subrange: 1..268435456
    Sorting: 109
  Subrange: 1..2147483647
    Sorting: 109
 
Array length: 50000
  Subrange: 1..1024
    Sorting: 47
  Subrange: 1..65536
    Sorting: 109
  Subrange: 1..4194304
    Sorting: 93
  Subrange: 1..268435456
    Sorting: 109
  Subrange: 1..2147483647
    Sorting: 109
 
Array length: 200000
  Subrange: 1..1024
    Sorting: 47
  Subrange: 1..65536
    Sorting: 156
  Subrange: 1..4194304
    Sorting: 110
  Subrange: 1..268435456
    Sorting: 125
  Subrange: 1..2147483647
    Sorting: 125
 
Array length: 1000000
  Subrange: 1..1024
    Sorting: 46
  Subrange: 1..65536
    Sorting: 93
  Subrange: 1..4194304
    Sorting: 140
  Subrange: 1..268435456
    Sorting: 140
  Subrange: 1..2147483647
    Sorting: 140
 
Array length: 5000000
  Subrange: 1..1024
    Sorting: 46
  Subrange: 1..65536
    Sorting: 78
  Subrange: 1..4194304
    Sorting: 171
  Subrange: 1..268435456
    Sorting: 140
  Subrange: 1..2147483647
    Sorting: 140 
 

Title: Re: Removing duplicates from an array
Post by: 440bx on May 31, 2022, 12:09:59 am

@avk,

There is one thing I don't understand in the results you posted, it is: the (I presume) time taken for 5 million elements is the same as the time taken for 1 million elements. I understand sorting time isn't linear but, it should take longer to sort 5 million elements than 1 million.

Am I misinterpreting the results you posted ?

Title: Re: Removing duplicates from an array
Post by: avk on May 31, 2022, 06:50:36 am

If you look inside the benchmark code, you can see that the same number of elements (10M) is processed each time for all array lengths.
BTW in this case (TGOrdinalArrayHelper) the sorting time should be exactly linear.

Title: Re: Removing duplicates from an array
Post by: SymbolicFrank on May 31, 2022, 08:45:36 am

If you want to keep the order as it is, it's probably still simpler to first create an index, then sort and remove the duplicates and last to use the index to put it back in the original order.

Title: Re: Removing duplicates from an array
Post by: BobDog on May 31, 2022, 01:20:57 pm

Here is my contribution remove duplicates by sorting.

Code: Pascal [Select][+]

 
uses
sysutils;
 
 //{$rangeChecks on}
 
 
generic Procedure QuickSort<T>(Var arr:array of T;Start:Int32;Finish:Int32);
Var
  i,j: Int64;
  x,temp:T;
Begin
  i := Start ;
  j := finish;
  x := arr[(Start+finish) Div 2];
  While I <= J Do
    Begin
      While arr[I] < x Do
        i:=i+ 1;
      While arr[J] > x Do
        j:=j- 1;
      If I<=J Then
        Begin
          temp := arr[j];
          arr[j] := arr[i];
          arr[i] := temp;
          I:= i+1;
          J:= j- 1;
        End;
    End;
  If J > Start Then specialize QuickSort<T>(arr,Start,J);
  If I < Finish Then specialize QuickSort<T>(arr,I,Finish);
End;
 
generic function RemoveDuplicates<T,Q>(arr:T):T;
var i,count:int32;
var ret:T;
begin
specialize quicksort<Q>(arr,0,high(arr));
count:=0;
setlength (ret,length(arr));
ret[0]:=arr[0];
for i:=0 to high(arr)-1 do
  begin
   if arr[i]<>arr[i+1] then
   begin
    count:=count+1;
    ret[count]:=arr[i+1];
   end;
end;
setlength(ret,count+1);
exit(ret);
end;
 
function range(mymin:int32;mymax:int32):int32;
   begin
   range:=trunc(int((Random*(Mymax-mymin+1)))+MyMin);
  end; 
 
type aoi=array of int32;
var
ans,i:aoi;
j:int32;
t:int64;
 
 
begin
ans:=nil;
i:=nil;
setlength(i,5000000);
for j:=0 to high(i) do i[j]:=range(1,1024);
writeln('Please wait');
t:=gettickcount64;
ans:=specialize RemoveDuplicates<aoi,int32>(i);
writeln(' Time taken = ',gettickcount64-t);
for j:=low(ans) to high(ans) do write(ans[j],' ');
writeln;
writeln('Press return to end . . .');
readln;
end.
 

It is easy to implement this way, but for indexing and returning to proper positions I'll have to think about.

Title: Re: Removing duplicates from an array
Post by: SymbolicFrank on May 31, 2022, 01:36:20 pm

Alternatively, you can sort the index. It amounts to the same thing.

Title: Re: Removing duplicates from an array
Post by: avk on June 05, 2022, 12:15:24 pm

Quote from: BobDog on May 31, 2022, 01:20:57 pm

Here is my contribution remove duplicates by sorting.
...
It is easy to implement this way, but for indexing and returning to proper positions I'll have to think about.

Maybe the simplest way:

store the values from the original array, along with their indices, into an auxiliary array;
sort auxiliary array entries by values(sorting must be stable);
remove entries in the auxiliary array that contain duplicate values;
sort the remaining records by indices;
store the values from the auxiliary array in the resulting order into the original array and adjust its length;

It is clear that in order for the performance of this method to compete with the hashset, both sorts must be very fast.

Title: Re: Removing duplicates from an array
Post by: jamie on June 05, 2022, 02:52:08 pm

you realize of course one could simply use a HASH table which allows for faster interactions.

Just sort the localized hashes.

Title: Re: Removing duplicates from an array
Post by: Thaddy on June 05, 2022, 03:57:22 pm

Quote from: jamie on June 05, 2022, 02:52:08 pm

you realize of course one could simply use a HASH table which allows for faster interactions.

Just sort the localized hashes.

Sorting hashes is utter nonsense. Ignore that.
Why?
Because hashes have no natural order, just a unique value, which means the sort has no meaning at all.
There is no relationship between the two, except that hashes are already sorted by nature..
Unique should be taken with a pinch of salt: accidents will happen. Elvis Costello is right.
Sorting on hash and then using it is O(n) so futile compared to real sorts.

https://www.youtube.com/watch?v=Ae_bdGihxy8
And:
https://en.wikipedia.org/wiki/Hashed_array_tree

Title: Re: Removing duplicates from an array
Post by: avk on June 05, 2022, 05:00:03 pm

Quote from: jamie on June 05, 2022, 02:52:08 pm

you realize of course one could simply use a HASH table which allows for faster interactions.
...

Are you one of those who only reads the last post in a thread?

Quote from: jamie on June 05, 2022, 02:52:08 pm

...
Just sort the localized hashes.

Funny approach, how would you implement it?

Title: Re: Removing duplicates from an array
Post by: jamie on June 05, 2022, 07:37:37 pm

Some of you are funny, have little common sense and yet you want to bite the hand that feeds you.

Bad planning starts an app off in the wrong direction.

Have fun sobbing in your sorrows while others like myself have no issues generating blazing fast execution code.

what a sad state of affairs.

Title: Re: Removing duplicates from an array
Post by: avk on June 05, 2022, 07:44:25 pm

Amen.

Title: Re: Removing duplicates from an array
Post by: Thaddy on June 05, 2022, 08:32:50 pm

Quote from: jamie on June 05, 2022, 07:37:37 pm

what a sad state of affairs.

Because you can't read? You got at least two proper answers.
And Amen.

Title: Re: Removing duplicates from an array
Post by: jamie on June 06, 2022, 01:41:51 pm

Of all people @Thaddy, you should be last one stepping up to the plate.

King of bloat and when some bloat does not work as desired add some more bloat on top of that bloat.

The vicious cycle continues.

Good job @Thaddy. Hope you get some more blinded sided followers to add to your crusade.

There are some that are simply unemployable, meanwhile I need to get back to work and make some real headway.

Happy Bloating.

Title: Re: Removing duplicates from an array
Post by: avk on June 06, 2022, 02:35:27 pm

It's a shame that the topic ceases to be constructive due to the efforts of participants who have contributed nothing but empty ranting to it.

Title: Re: Removing duplicates from an array
Post by: Thaddy on June 06, 2022, 09:01:54 pm

I am never bloating. You can't read. And where appropiate I always provide a compilable example.
IOW you are fired! in the unlikely case you ever worked for me. I know a rat compared to a rabbit.

Shut this.

Title: Re: Removing duplicates from an array
Post by: SymbolicFrank on June 07, 2022, 11:41:15 am

Turning them into indexed hashes and sorting those sounds good to me. Depending on how you sort, comparing them is often the thing that takes the most time and with hashes you only have to read the data once.
Then again, if the entries are long sentences, finding the first difference might be faster. I can think of edge cases either way.

Title: Re: Removing duplicates from an array
Post by: Joanna on June 16, 2022, 03:27:49 am

I understand that knowing how to remove duplicates from an array has academic merit but in real life programming wouldn’t it be better to work on the problem of duplicate values getting into the array to begin with? It seems like no matter what you do it’s going to take a lot of extra time and effort to undo the duplicates in array.
Has there ever been considered an Function indexof(Avalue) to detect duplicates of an array or maybe a flag to not allow duplicates? If seen this for various other things so it seems like it should be possible to implement them for arrays.

Title: Re: Removing duplicates from an array
Post by: Ten_Mile_Hike on August 01, 2022, 12:17:06 am

Code: Text [Select][+]

Wow,
 Hash tables, Log n ( time analysis), collections, helpers, generics, sorting procedures...
You guys are way over my level of ability. Nevertheless; here is how I would detect and
eliminate duplicates in an array and YES; my way is probably inefficient in both memory
and processor utilization, but it is just my way. 
 
=============pseudo code=================
var
  Array_dups[0..9] of integer=[8,6,9,11,6,22,3,8,6];
  Array_Fixed[0..9999] of integer; {Declare *expected* max range}
  x:integer;
 
Begin
   Initialize_All_Elements_to_Zero (array_Fixed);
   for x:=0 to High(Array_Dups) Do
     Array_Fixed[Array_Dups[x]] 
           :=  Array_Fixed[Array_Dups[x]]+1;
 
//////////////////////////////////////////////////////////////////////////////
 At this point the elements of Array_fixed indicate the following
         all elements  =0 did not occur in Array_Dups
         all elements  =1 occurred only once in Array_Dups
         all elements  >1 had duplicates in Array_Dups 
 
It is now trivial to assign the values of Array_Fixed back into 
Array_Dups or manipulate or assign them in any manner that you choose
  
 

Lazarus

Free Pascal => General => Topic started by: BillMcEnaney on May 19, 2022, 07:07:24 pm