9
$\begingroup$

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?

$\endgroup$
2
  • 1
    $\begingroup$ For questions like this, which take a one-word answer, it's probably better if you ask in chat. Just a suggestion. $\endgroup$
    – Szabolcs
    Mar 6, 2014 at 23:40
  • 2
    $\begingroup$ 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. $\endgroup$
    – ciao
    Mar 7, 2014 at 0:26

3 Answers 3

9
$\begingroup$

Yes. You are looking for MemberQ.

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

$\endgroup$
1
13
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ Nice. I was waiting for someone to post this kind of method. +1 $\endgroup$
    – ciao
    Mar 8, 2014 at 11:56
  • $\begingroup$ @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). $\endgroup$ Mar 8, 2014 at 12:16
  • $\begingroup$ @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. $\endgroup$ Mar 8, 2014 at 12:18
  • $\begingroup$ 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...". $\endgroup$
    – ciao
    Mar 8, 2014 at 12:27
  • $\begingroup$ @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. $\endgroup$ Mar 8, 2014 at 13:07
3
$\begingroup$

In M11.1+ (perhaps earlier as well) you can use Nearest to test multiple elements at once. Here is a comparison with @LeonidShifrin's answer:

lrgTest = RandomInteger[100000,{100000}];

r1 = Nearest[lrgTest->"Index", Range[100000], {All, 0}];//AbsoluteTiming

pfl = makePositionFunction[lrgTest]; //AbsoluteTiming
r2 = Map[pfl,Range[100000]]; //AbsoluteTiming

r1 === r2

{0.044715, Null}

{0.191114, Null}

{0.156117, Null}

True

Almost 4 times faster.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.