I have a large integer packed array arr
. My array is multidimensional, but for simplicity let's consider 1D arrays for now. ArrayReshape
takes care of the rest.
I also have a set
of integers (a list).
The task is to replace those elements of arr
which are in set
with 1, and those which aren't with 0.
What is the best way to do it, where "best" means fastest for as long we don't run out of memory?
For testing purposes, let's use
n = 100000000;
k = 20;
arr = RandomInteger[100, n];
set = RandomInteger[100, k];
What have I tried so far?
Method 1. For a single element of set
, denoted elem
, we can test using 1 - Unitize[arr - elem]
. We can test for each element of set
one by one using
res = 1 - Fold[# Unitize[arr - #2] &, ConstantArray[1, Length[arr]], set];
This is linear in the size of set
, and we can do better than that. I used Fold
instead of mapping over set
to avoid having to simultaneously store a huge array in memory for each element of set
.
Method 2. An alternative is using associations for looking up the set elements, which should be no worse than logarithmic complexity in the size of set
(i.e. much better than linear).
ass = AssociationThread[set -> ConstantArray[1, Length[set]]]
res = Lookup[ass, arr, 0];
It's clear that for large enough k
this will be faster than method 1 due to its better complexity. In practice the threshold where that happens is only $k=5$ for my test data. But this method does not produce a packed array result, which is a disadvantage!
For comparison, I also implemented the same thing in C++ (using a naive lookup with std::set
). For $k=5$ I get the following timings: 5.9 s for method 1; 5.9 s for method 2 (re-packing the array takes an additional 0.7 s); 1.4 s for C++.
SparseArray
? Thinking out loud here... $\endgroup$Lookup
is never a packed array, thus it will take up 3 times the storage than a packed version would. I did not mean that the input toLookup
gets unpacked (in fact I didn't look at whether that happens). $\endgroup$