# Is there a function which instantly tells you whether an element is part of a list?

I have a very long list of numbers and I want to check whether there's a function (something that would look like PartOfQ[element,list]) that tells you immediately with a True or False as to whether the element in question is part of the list or not.

Ideally it would also tell you its index.

If there isn't a built-in such function, is there an efficient way of building such a function myself?

-
For questions like this, which take a one-word answer, it's probably better if you ask in chat. Just a suggestion. – Szabolcs Mar 6 '14 at 23:40
You should note "instant", if you mean time taken, is unrealistic: even the fast MemberQ will take noticeable time on large lists. If you have a need to query membership in a time-critical manner (and often), better to pre-build a hash-map/etc, which will give constant-time checks. – ciao Mar 7 '14 at 0:26

## 2 Answers

Yes. You are looking for MemberQ.

Position will tell you the indexes of all occurrences of the element.

-
Your CW answers today are Legion, like the flowers of my garden – Dr. belisarius Mar 7 '14 at 1:46

Since large lists were mentioned, I will provide a custom solution based on hashing, as hinted by @rasher, which might be appropriate here. We will construct a precomputed position function, which would return a list of positions for a given element, and an empty list if there are none:

ClearAll[makePositionFunction];
makePositionFunction[lst_List] :=
Module[{
rules =
Dispatch[
Append[
#[[1, 1]] -> #[[All, 2]] & /@
GatherBy[Transpose[{#, Range[Length[#]]}] &@lst, First],
_ -> {}
]
]
},
Function[elem, elem /. rules]
]


Here is an example of use:

tst  = RandomInteger[15, 15]

(* {0, 9, 14, 13, 1, 14, 10, 4, 6, 11, 14, 4, 8, 9, 1} *)


We construct a position function:

pf = makePositionFunction[tst];


And now use it:

pf[1]

(* {5, 15} *)

pf[2]

(* {} *)


Here is a power test

lrgTest = RandomInteger[100000,{100000}];
pfl = makePositionFunction[lrgTest];


Here we find positions of all numbers in range, in one go:

Map[pfl,Range[100000]]//Short//AbsoluteTiming

(* {0.255559,{{40535},{65319,80798},{27408},{84197},<<99992>>,{},{},{59995},{}}} *)


Note that it takes time to construct this function, so it will only make sense if you intend to query your list many times.

What I personally found interesting is that the above code based on Dispatch is about 4 times faster than the code based on compiled (to MVM target) binary search with inlined list ordering and original list (which I do not post here), which was a bit surprising for me. Perhaps, with the C target and additional vectorization over the searched elements, it could beat Dispatch, but my point is that Dispatch is pretty efficient.

-
Nice. I was waiting for someone to post this kind of method. +1 – ciao Mar 8 '14 at 11:56
@rasher Thanks. This of course comes to mind immediately. What I found surprising was that the byte-code compiled binary search was slower, even when we embed the original list and ordering permutation into the closure (which does make it faster because one doesn't need to transfer these to compiled function on every call). I would think that the optimized C-compiled version would be faster than Dispatch, but probably not by much (may be 2-3 times faster). – Leonid Shifrin Mar 8 '14 at 12:16
@rasher I also disagree with those who closed the question, I think that in the form it was asked it is not RTFM, and does not reduce to MemberQ and Position. Actually, I will vote to reopen it, and invite you to join me. – Leonid Shifrin Mar 8 '14 at 12:18
Done. And I too am often surprised (sometimes shocked) at how fast Dispatched rule replacement can be, as in "my code broke, it can't be this quick...". – ciao Mar 8 '14 at 12:27
@rasher Yeah, right. Dispatch is a really good tool. At least, we promote it here on SE quite a bit - I remember that in the past it has been quite an obscure command. When I was learning Mma as a programming language (around 2004 - 2006), there wasn't much information on how to use it effectively. Now things are different, thanks to our community here at SE. – Leonid Shifrin Mar 8 '14 at 13:07