# A set of elements

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] –  andre Feb 5 at 19:54

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. –  Mr.Wizard Feb 5 at 20:03
@Mr.Wizard Yes, Dispatch should still be useful. Association is basically Dispatch on steroids –  rm -rf Feb 5 at 20:05
+1. Out of curiosity, are these timings on your Raspberry Pi? If so what is the processor speed? –  RunnyKine Feb 5 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 at 22:04
@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. –  Leonid Shifrin Feb 5 at 22:42

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 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[set -> True, 1*^7, False];

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

0.0086


This is about 3.5 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.

-
You need to add IntegerQ to the output of BinarySearch` to get a Boolean result. –  rm -rf Feb 5 at 19:53
@rm-rf Right -- corrected. –  Mr.Wizard Feb 5 at 19:55
@Mr.Wizard I just love it when a Q turns into a benchmarking competition :D +1 –  Sektor Feb 5 at 20:27
@Sektor I'm glad you appreciate my philosophy. :-) –  Mr.Wizard Feb 5 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 at 20:37
show 1 more comment