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.
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$