Re: Extracting some elements, members of another list
- To: mathgroup at smc.vnet.net
- Subject: [mg112469] Re: Extracting some elements, members of another list
- From: Ray Koopman <koopman at sfu.ca>
- Date: Thu, 16 Sep 2010 06:01:44 -0400 (EDT)
- References: <i6q0l9$l5o$1@smc.vnet.net>
On Sep 15, 1:38 am, Leonid Shifrin <lsh... at gmail.com> wrote:
> Hi,
>
> The following function:
>
> Clear[memberPositions];
> memberPositions[x_List, y_List] :=
> Module[{tag},
> Pick[Range[Length[x]],
> Replace[x, Dispatch[Thread[Rule[Intersection[x, y], tag]]], {1}],
> tag]]
>
> Is a fast way to find positions in list <x> which are also in <y>, for
> arbitrary lists <x> and <y>. Using it, it worked in about 5 seconds on my
> machine (M7.0 32bit WinXP AMD Phenom II - 2800 Ghz). Here is how you do it:
>
> Model your lists:
>
> In[16]:= list1 = Transpose[
> {RandomInteger[{1000000,9999999},1000000],
> Table[ToExpression["data"<>ToString[i]],{i,1,1000000}]}];
>
> In[17]:= list2 = RandomSample[list1[[All,1]],500000];
>
> Get the result:
>
> In[18]:= list1[[memberPositions[list1[[All,1]],list2]]]//Short//Timing
> Out[18]= {5.203,{{9506759,data1},{3854419,data2},{1093656,data3},
> <<526944>>,{6991722,data999997},{9278309,data1000000}}}
This is very quick the first time thru, but each successive call
slows by an increasing amount. Here are 5 sequential sample times
for the same two input lists: {4.84, 5.34, 6.39, 7.21, 8.95}.
What's causing the slowdown, and how can it be fixed?