# choosing the fastest way of finding position

I have this list {1,7,8,10} for instance. and a second list which is always smaller or equal to the first one say {10,7}. How can I find the position of the elements of the second list in the first list: the answer to above example is {2,4}. but I want the answer in this form: {0,1,0,1} which implicitly gives {2,4}.

-
Have a look here. I don't claim that code can't be improved further, but it is reasonably fast. – Leonid Shifrin Feb 26 '14 at 17:39

list1 = {1, 7, 8, 10};
list2 = {10, 7};
Boole[MemberQ[list2, #] & /@ list1]


Edit, I found faster:

Module[{f}, SetAttributes[f, Listable];
(f[#] = 1) & /@ list2; f[_] = 0; f[list1]]


Edit, I found even faster (but list1 shouldn't contain duplicates):

Do initially: f[{_,_}] = 1; f[{_}] = 0;

Map[f[#] &, Split[Sort[Join[list1,
Intersection[list1, list2]]]]][[Ordering[Ordering[list1]]]]

-
thanks, no list1 does not have duplicates – Meqdad Feb 26 '14 at 19:24
+1 nice use of ordering. – ciao Feb 26 '14 at 23:08

About twice as fast as any so far (actually over triple on larger lists, but see updates below), including coolwater's cool use of ordering. The sparse-array method is fifty times faster if lists (as in OP case) allow its use:

list1 = DeleteDuplicates[RandomInteger[{1,5000000}, 1000000]];
list2 = RandomSample[list1, 1000];

ClearSystemCache[]
resmetime =
First@Timing@(resme =
Replace[list1, Dispatch[Append[Thread[list2 -> 1], _ -> 0]], 1])

ClearSystemCache[]
ClearAll[f]
f[{_, _}] = 1; f[{_}] = 0;

rescoolwatertime =
First@Timing@(rescoolwater =
Map[f[#] &,
Split[Sort[
Join[list1, Intersection[list1, list2]]]]][[Ordering[
Ordering[list1]]]])

(* using SparseArray *)
ressatime =
First@Timing@(ressa =
SparseArray[(List /@ list2) -> 1, Max[list1]][[list1]] //
Normal;)

{resmetime, rescoolwatertime, ressatime, rescoolwatertime/resmetime,
rescoolwatertime/ressatime, resme == rescoolwater == ressa}

(* {2.870418, 9.547261, 0.202801, 3.32609, 47.077, True} *)


On smallish lists of positive integers (under a few thousand elements in the target and a "reasonable" subset in the searched list), bitmasks will probably beat all:

Reverse[Most@IntegerDigits[Fold[BitSet, 0, list2], 2, Max[list1] + 1]][[list1]]


Finally, a pretty snippet that has some advantages: within the constraints of lists not having duplicates and the search list being a subset of the target, it is agnostic as to contents (i.e., not limited to integers, could be symbols, strings, sublists, etc.- a trait shared by my first replacement-based solution) and is quite quick. (you could adapt the sparse/bitmap methods with mapping to do the same, but you'd likely kill their advantage in their respective areas with such machinations.):

Subtract[Tally[Join[list1, list2]][[All, 2]], 1]


Some quick timings on the netbook.

Larger lists, 5% search size, single run (I did not run bitmap over 200K - netbook...):

Smaller lists, 5% search size, 500 runs each (most were so fast single runs were below clock resolution):

-
Very nice, but replacing (List /@ list2) with Transpose[{list2}] decreases timing with 10% on my machine – Coolwater Feb 27 '14 at 10:04
@Coolwater: well, let me check that out... – ciao Feb 27 '14 at 10:09
@Coolwater: Added to times (sparse2) - seems a wash on my lounge-book, of course version/environment can make a difference. Clean though, I like it! – ciao Feb 27 '14 at 10:21