Fastest way to check for list membership

Question

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

Answer 1

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.

Answer 2

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!

Answer 3

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

memberQFunction1[set_]:=Module[{f,ass},
    ass=<|Thread[set -> True]|>;
    f[x_]:=Lookup[ass,x,False];
    f
]

memberQFunction2[set_]:=Module[{f,rule},
    rule=Dispatch@Append[Thread[set->True],_-> False];
    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.

Answer 4

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

Once inserted, access to its elements is ultra-fast:

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