# 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] Commented 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
Commented Feb 5, 2014 at 19:53
• @rm-rf Right -- corrected. Commented Feb 5, 2014 at 19:55
• @Sektor I'm glad you appreciate my philosophy. :-) Commented 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
Commented 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... Commented 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. Commented Feb 5, 2014 at 20:03
• +1. Out of curiosity, are these timings on your Raspberry Pi? If so what is the processor speed? Commented 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
Commented 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. Commented 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. Commented 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.

V 12.1 introduced CreateDataStructure:

A link to its many members: DataStructures

A suitable choice for the question at hand would be SortedMultiset

1. Structure

ds = CreateDataStructure["SortedMultiset"];

Scan[ds["Insert", #] &, Range @ 10]

ds["Elements"]


{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

ds["Visualization"]


2. Timings

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

ds = CreateDataStructure["SortedMultiset"];

Scan[ds["Insert", #] &, list] // Timing // First


5.7673

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


0.00152

Compare to "normal" MemberQ:

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


4.74134

• Interesting. But you will need quite many queries to ammortize the huge insertion time of the tree. And I doubt that it will ever be more efficient than a Sort combined with a binary search, at least for simple data types. Commented Nov 17, 2023 at 16:50
• Scan[ds["Insert", #] &, list] must have an enormous calling overhead. One can try to build the tree also with CreateDataStructure["SortedMultiset", list]. I had hoped that it would improve the timings, but it barely did so. Which tells me that the data structure is badly designed. I guess this constructor is not implemented on the C/C++ side of the backend. Commented Nov 17, 2023 at 16:50
• But you might also consider that a SINGLE MemberQ-Query takes 4.74 seconds. Doesn't amortization come soon enough? On the other hand I agree that a compiled binary search would be more efficient, but not everybody has the expertise to write such code.
– eldo
Commented Nov 17, 2023 at 16:59
• nf = Nearest[list];found = Flatten[nf[Range[1, 1*^7, 7777], {1, 0}]];` might be a good compromise between built time and lookup time. It outputs all the elements found and not the boolean flags. But that can easily be converted. Commented Nov 17, 2023 at 17:03