Is there a way to tell Mathematica that a list is sorted?

Questions
1

When I’m searching for a value in a list, Mathematica seems to do a linear search:

First@AbsoluteTiming[MemberQ[Range[10000], #]] & /@ 
  Range[10000] // ListPlot

graphTim.jpg
graphTim.jpg360×213 28.9 KB

Is there a way I can tell Mathematica that the list is sorted, and hence that it’s allowed to use the much faster binary search?

2

MemberQ would need to know that its first argument is sorted.
However the only option it takes is in order to check for the variable type instead of the variable value:

In[1]:= Options@MemberQ

Out[1]= {Heads -> False}

Short of any global internal variable that I am not aware of there therefore seems to be no way to affect the Search algorithm.

It’s a great idea though, so I filed an according suggestion for you.

3

@Peter: Thanks for this!

4 
hashList = Dispatch[Thread[Range[10000] -> True]];
Tally[First@Timing[Replace[#, hashList]] & /@ Range[10000]]

{{0., 10000}}

Create a dispatch table.

5

Ah, that’s a nice way of doing it - the extra memory requirements aren’t too bad, either.

6

That is a really cool way of doing it. One adaptation for reuse that uses closures:

makeSearcher[xs_List] :=
 Module[{lookup = Dispatch@Thread[xs -> True]},
  Function[x, TrueQ@Replace[x, lookup]]]

test = Range@10000;

searcher = makeSearcher@test;

fast = searcher /@ test; // AbsoluteTiming

(* Out: {0.035002, Null} *)

slow = MemberQ[test, #] & /@ test; // AbsoluteTiming

(* Out: {9.002515, Null} *)

fast === slow

(* Out: True *)

Over 250x speed-up for an input list of 10k elements :slight_smile:

I’ve always been more comfortable with closures outside of Mathematica in more traditional functional languages like Lisp/Racket/et al. A colleague of mine wrote a neat little blog post a while back about closures in Mathematica: http://searke.blogspot.com/2011/05/two-techniques-in-functional.html A very nice and neat exposition that inspires the above code.