# Fastest way to check for List membership

I have a set of say 100 numbers {1,3,7,11,19,...3971}. All elements are previously determined. I want to check whether 376 belongs to this set or not. what is the fastest way? Thanks

• MemberQ[listOfElements,376] Feb 5, 2014 at 19:54

As andre notes this can be done simply with MemberQ. However, the set you show is ordered, so other methods may be faster. It probably won't matter for a set of "say 100 numbers" but it can make a big difference in longer sets.

Starting with a set of ordered unique elements:

set = Union @ RandomInteger[1*^7, 1*^6];


Timing using MemberQ:

Do[MemberQ[set, i], {i, 1, 1*^7, 77777}] // Timing // First

5.834


Timing using BinarySearch from the Combinatorica package:

Needs["Combinatorica"]

Do[IntegerQ @ BinarySearch[set, i], {i, 1, 1*^7, 77777}] // Timing // First

0.015


Also, if you are going to perform this test repeatedly, or if the set is not ordered, it is worth building a hash table:

rls = Dispatch @ Append[Thread[set -> True], _ -> False];


Now with a denser sampling:

Do[IntegerQ @ BinarySearch[set, i], {i, 1, 1*^7, 500}] // Timing // First

Do[Replace[i, rls], {i, 1, 1*^7, 500}] // Timing // First

1.748

0.015


Of course if you can test them all at once it's even better (note very dense sampling):

Do[Replace[i, rls], {i, 1, 1*^7, 15}] // Timing // First

Replace[Range[1, 1*^7, 15], rls, {1}] // Timing // First

0.671

0.39


Now, if all your elements are machine-size positive integers we can take this farther by building an array, then extracting values with Part:

 sa = SparseArray[Partition[set, 1] -> True, 1*^7, False];

sa[[ Range[1, 1*^7, 15] ]] // Timing // First

0.0268


This is about 1.1 million times faster than MemberQ on this set. This requires that each of the test elements is within the set or you will get Part:partw error messages. You could however Clip the input, setting out-of-bounds values to a known-False position. There is overhead (~0.34 second) in building the SparseArray but once that is complete element tests are very fast.

• You need to add IntegerQ to the output of BinarySearch to get a Boolean result.
– rm -rf
Feb 5, 2014 at 19:53
• @rm-rf Right -- corrected. Feb 5, 2014 at 19:55
• @Sektor I'm glad you appreciate my philosophy. :-) Feb 5, 2014 at 20:31
• @Mr.Wizard The sparse array approach is fast, but you're making an implicit assumption that all the keys being searched are less than the max value in the list. If the integer being checked is larger, then Part will complain. Of course, you can rectify this with a check, but that will probably also kill all the speed gains and perhaps make it slower than the rest of the approaches.
– rm -rf
Feb 5, 2014 at 20:37
• I'm trying to apply the SparseArray method. Apprently, under Matheamatica v10.0.2, your code for creating the SparseArray, returns now a SparseArray with Length@set dimensions. A Thread[set->True] is necessary, in some way according to the actual documentation. I'm not sure if it's an implementation bug, a documentation bug, a previous-version solved bug... Jan 15, 2015 at 8:36

If you're going to do several lookups repeatedly in a single set, using Associations in version 10 is orders of magnitude faster than BinarySearch. You can try it out if you have Mathematica 10 for Raspberry Pi (publicly available) or the pre-release version.

set = Union @ RandomInteger[1*^7, 1*^6];
assoc = <|Thread[set -> True]|>; (* One time operation *)
Do[Lookup[assoc, i, False], {i, 1, 1*^7, 77777}] // Timing // First
(* 0.000152 *)


Here's the timings for BinarySearch on my computer:

Do[IntegerQ@BinarySearch[set, i], {i, 1, 1*^7, 77777}] // Timing // First
(* 0.016991 *)


which is about 100 times slower!

• I was about to add a Dispatch table method to my answer, but that kind of took the wind out of my sails. I suppose I still should for pre-v10 users. Feb 5, 2014 at 20:03
• +1. Out of curiosity, are these timings on your Raspberry Pi? If so what is the processor speed? Feb 5, 2014 at 20:32
• @RunnyKine I benchmarked this on my Raspberry Pi and these are the results: For a set with 10^7 elements the Pi runs out of memory. So I reduced it to 10^6 elements. BinarySearch takes about the same time as Lookup (0.002725 and 0.003627 seconds, respectively), but the initial Association takes 21 seconds, so it's slower in most cases.
– shrx
Feb 5, 2014 at 22:04
• You can easily Compile binary search, to get competitive performance (I've done that many times). You can also construct a massive compiled binary search, which I believe can be even quite a bit faster. But of course, +1. Feb 5, 2014 at 22:37
• @rm-rf The main advantages of Association w.r.t. say DownValues - based hash - table, apart from speed, are that it is stateless / immutable and cheap to copy. This allows Association to play well with the core Mathematica constructs. OTOH, it has also advantages over Dispatch, since you can add new or update old key-value pairs in constant time, getting a new Association - while Dispatch you can't efficiently update once it is formed. Feb 5, 2014 at 22:42

Here is some time comparition between Dispatch and Association, creating a memberQFunction using @rm-rf and @Mr.Wizard solutions.

memberQFunction1[set_]:=Module[{f,ass},
f[x_]:=Lookup[ass,x,False];
f
]

memberQFunction2[set_]:=Module[{f,rule},
f[x_]:=x/.rule;
f
]

memberQFunction3[set_]:=Module[{f,rule},
rule=Dispatch@Map[#->True&,set];
f[x_]:=If[x/.rule,True,False,False];
f
]


Now let's create our hashed functions:

set = DeleteDuplicates[RandomInteger[1000000, 1000000]];
setSample = RandomSample[set, 100000];

mQ1 = memberQFunction1[set];
mQ2 = memberQFunction2[set];
mQ3 = memberQFunction3[set];


Testing it we get:

mQ1 /@ setSample // AbsoluteTiming // First
mQ2 /@ setSample // AbsoluteTiming // First
mQ3 /@ setSample // AbsoluteTiming // First

0.156000 (*Association*)
0.202800 (*Dispatch1*)
0.218400 (*Dispatch2*)


Association wins!

I hopped that the new MemberQ operator form would be Hashed, just like Nearest does, creating a NearestFunction, but it's not the case, so memberQFunction (with Association`) is a good alternative.