6
$\begingroup$

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

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

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...):

enter image description here

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

enter image description here

| improve this answer | |
$\endgroup$
  • $\begingroup$ Very nice, but replacing (List /@ list2) with Transpose[{list2}] decreases timing with 10% on my machine $\endgroup$ – Coolwater Feb 27 '14 at 10:04
  • $\begingroup$ @Coolwater: well, let me check that out... $\endgroup$ – ciao Feb 27 '14 at 10:09
  • $\begingroup$ @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! $\endgroup$ – ciao Feb 27 '14 at 10:21
4
$\begingroup$
list1 = {1, 7, 8, 10};
list2 = {10, 7};
Boole[MemberQ[list2, #] & /@ list1]
(*timing about 1,30*)

Edit, I found faster:

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

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]]]]
(*timing about 0,45*)
| improve this answer | |
$\endgroup$
  • $\begingroup$ thanks, no list1 does not have duplicates $\endgroup$ – Meqdad Feb 26 '14 at 19:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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