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$
1
  • $\begingroup$ Have a look here. I don't claim that code can't be improved further, but it is reasonably fast. $\endgroup$ Feb 26, 2014 at 17:39

2 Answers 2

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

$\endgroup$
3
  • $\begingroup$ Very nice, but replacing (List /@ list2) with Transpose[{list2}] decreases timing with 10% on my machine $\endgroup$
    – Coolwater
    Feb 27, 2014 at 10:04
  • $\begingroup$ @Coolwater: well, let me check that out... $\endgroup$
    – ciao
    Feb 27, 2014 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, 2014 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*)
$\endgroup$
1
  • $\begingroup$ thanks, no list1 does not have duplicates $\endgroup$
    – Meqdad
    Feb 26, 2014 at 19:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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