# Efficiently Delete Duplicates

The Goal

I have a list consisting of 2 million lists of (positive) integers. The length of the list when flattened is about 60 million. The goal is to Flatten the list (Catenate) and delete all duplicates.

The Issue

The list consists of very large numbers (>10^11) and DeleteDuplicates causes the error SystemException["MemoryAllocationFailure"].

My Attempts

As a dummy, let list be defined as:

a := RandomInteger[10^10, 30];
list = Table[a, 2*^6];


Using Catenate and DeleteDuplicates on list consumes a lot of memory:

MaxMemoryUsed[DeleteDuplicates@Catenate@list]
(* 3475344280 *)


I have tried Folding Join and DeleteDuplicates

Fold[DeleteDuplicates[Join[#1, #2]]&, {}, list]


It takes less memory but takes too much time (takes ~300x more time).

I attempted using @RayKoopman 's method, which actually took more memory and crashed my computer.

DD[data_] := Part[data,Sort@Part[Range[Length@data][[#]],
Most@FoldList[Plus,1,Length/@Split@data[[#]]]]]& @ Ordering@data;
DD@Catenate@list


The Question

How could one memory-efficiently remove all duplicates in a very long list?

Note: My list consists of only positive integers.

• What percentage of duplicates do you have? If it is significant, you could start with smaller pieces of your list and whittle those down, to be reunited and treated later on. – Yves Klett Aug 5 '16 at 6:02

Don't use Catenate; it is unpacking your lists!

On["Packing"]

Catenate[list] // ByteCount


DeveloperFromPackedArray::punpack1: Unpacking array with dimensions {30}. >>

DeveloperFromPackedArray::punpack1: Unpacking array with dimensions {30}. >>

DeveloperFromPackedArray::punpack1: Unpacking array with dimensions {30}. >>

General::stop: Further output of DeveloperFromPackedArray::punpack1 will be suppressed during this calculation. >>

1440000080


Join instead:

Join @@ list // ByteCount   (* no messages *)

480000144


Code:

DeleteDuplicates[Join @@ list] // ByteCount       (*  479855632   *)

DeleteDuplicates[Join @@ list] // MaxMemoryUsed   (*  2039547560  *)

Union @@ list // MaxMemoryUsed                    (*  1936000536  *)


I would use Union @@ list:

a := RandomInteger[10^10, 30];
list = Table[a, 2*^6];

MaxMemoryUsed[Union @@ list;]/MaxMemoryUsed[2 list;]


2.01666

If it is important that no sorting is applied, the following uses less memory than your Fold approach and its faster, though still slow (~sqrt(300)x more time)

Catenate[Reap[Nest[(Sow[First[#]]; DeleteCases[Rest[#],
Alternatives @@ First[#]]) &, list, Length[list]]][[2, 1]]]

• Union isn't really as important as avoiding Catenate, which you also did. +1 nevertheless. – Mr.Wizard Aug 5 '16 at 11:43

Actually I do not agree with your statement that DeleteDuplicates uses a lot memory. Let us take your example and make some tests taking MaxMemoryUsed[2 list] as a reference:

MaxMemoryUsed[2 list]
(*960 000 520*)

MaxMemoryUsed[Flatten[list]]/MaxMemoryUsed[2 list ] // N
(*2.74375*)

fl=Flatten[list];
MaxMemoryUsed[DeleteDuplicates[fl]]
(*2.12015*)

MaxMemoryUsed[DeleteDuplicates[Flatten[list]]]
(*3.62015*)


From this data we see that DeleteDuplicates uses a moderate amount of memory that is even smaller than that of Flatten! Notice also, that the memory scales linearly in all cases.