3
|
6193 Views
|
5 Replies
|
12 Total Likes
View groups...
Share
GROUPS:

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

Posted 11 years ago
 When I'm searching for a value in a list, Mathematica seems to do a linear search:First@AbsoluteTiming[MemberQ[Range[10000], #]] & /@   Range[10000] // ListPlotIs 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?
5 Replies
Sort By:
Posted 11 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: http://searke.blogspot.com/2011/05/two-techniques-in-functional.html A very nice and neat exposition that inspires the above code.
Posted 11 years ago
 hashList = Dispatch[Thread[Range[10000] -> True]];Tally[First@Timing[Replace[#, hashList]] & /@ Range[10000]]{{0., 10000}}Create a dispatch table.
Posted 11 years ago
 Ah, that's a nice way of doing it - the extra memory requirements aren't too bad, either.
Posted 11 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@MemberQOut[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 11 years ago
 @Peter: Thanks for this!
Community posts can be styled and formatted using the Markdown syntax.