Message Boards Message Boards


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

Posted 10 years ago
5 Replies
12 Total Likes
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

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?
POSTED BY: Patrick Stevens
5 Replies
Posted 10 years ago
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 :-)

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: A very nice and neat exposition that inspires the above code.
POSTED BY: William Rummler
hashList = Dispatch[Thread[Range[10000] -> True]];
Tally[First@Timing[Replace[#, hashList]] & /@ Range[10000]]
{{0., 10000}}
Create a dispatch table.
Ah, that's a nice way of doing it - the extra memory requirements aren't too bad, either.
POSTED BY: Patrick Stevens
Posted 10 years ago
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.
POSTED BY: Peter Fleck
@Peter: Thanks for this!
POSTED BY: Patrick Stevens
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
or Discard

Group Abstract Group Abstract