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
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
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++.