Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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

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

2 Answers 2

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

share|improve this answer
    
Very nice, but replacing (List /@ list2) with Transpose[{list2}] decreases timing with 10% on my machine –  Coolwater Feb 27 at 10:04
    
@Coolwater: well, let me check that out... –  rasher Feb 27 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! –  rasher Feb 27 at 10:21
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*)
share|improve this answer
    
thanks, no list1 does not have duplicates –  Meqdad Feb 26 at 19:24
    
+1 nice use of ordering. –  rasher Feb 26 at 23:08

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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