MathGroup Archive 2010

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Extracting some elements, members of another list

  • To: mathgroup at smc.vnet.net
  • Subject: [mg112433] Re: Extracting some elements, members of another list
  • From: Valeri Astanoff <astanoff at gmail.com>
  • Date: Wed, 15 Sep 2010 04:40:08 -0400 (EDT)
  • References: <i6nedc$g8u$1@smc.vnet.net>

On 14 sep, 11:14, Nacho <ncc1701... at gmail.com> wrote:
> Hi!
>
> I would like your advice about this problem:
>
> I have a list of elements, consisting in phone numbers with some data:
>
> list1= { { phone1, data1}, {phone2, data2}, {phone3, data3} .... }
>
> And a list of phones, a subset of the phone numbers in list1
>
> list2= {phone2, phone3, phone7... }
>
> I'd like to extract the elements from list1 whose phone numbers are
> present in list 2, that is:
>
> result= { { phone2, data2}, {phone3, data3, {phone7, data7} .... }
>
> I've used this with small lists and it works fine:
>
> result = Select[list1, MemberQ[list2, #[[1]]] &];
>
> The problem is that now I would like to use it with big lists. list1
> is over 1.000.000 elements long and list2 is about 500.000 elements
> long.  Ordering is not a problem, I could resort the lists.
>
> Any hint to extract this list faster? It seems to take a lot of time
> (estimation is about 5 hours and I have to do it repeatedly)
>
> Thanks!

Good day,

Assuming both lists are sorted, you could match
them this way (an example with size n=10000):

In[1]:= n = 10000;
list1 = Table[{k,RandomInteger[{1,n}]},{k,1,n}] ;
list2 = list1[[All,1]][[Floor[n/4];; Floor[3n/4]]] ;

In[4]:= (list3 = {#,True}& /@ list2;
list4 = {#,False}& /@ Complement[list1[[All,1]],list2];
list5 = Union[list3, list4];
list6 = Transpose[{list1, list5}];
Cases[list6,{{_,_},{_,True}}][[All,1]])//Timing//Short

Out[4]//Short= {0.094,{{2500,8261},{2501,8320},<<4997>>,{7499,6791},
{7500,943}}}


In[5]:= Select[list1,MemberQ[list2,#[[1]]]&]//Timing//Short

Out[5]//Short= {9.219,{{2500,8261},{2501,8320},<<4997>>,{7499,6791},
{7500,943}}}


In[7]:= 9.219/0.094

Out[7]= 98.0745


Matching lists seems to be 100 times faster then MemberQ

hth

--
Valeri Astanoff


  • Prev by Date: Re: Inconsistent behaviour of Integrate
  • Next by Date: Re: Generalizing Complement to handle multiple occurrences of elements
  • Previous by thread: Re: Extracting some elements, members of another list
  • Next by thread: Re: Extracting some elements, members of another list