MathGroup Archive 2008

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

Search the Archive

Re: Better way to write this

  • To: mathgroup at smc.vnet.net
  • Subject: [mg85085] Re: Better way to write this
  • From: Szabolcs Horvát <szhorvat at gmail.com>
  • Date: Sun, 27 Jan 2008 05:50:16 -0500 (EST)
  • Organization: University of Bergen
  • References: <fnet45$id5$1@smc.vnet.net>

Louis Theran wrote:
> I have the following function that takes as its input a number of
> lists and returns the elements in each of them that appear exactly
> once:
> 
> SpecialElements[lists:_List..]:=
> Module[{l,n,Sower,Reaper},
> l = {lists}; n = Length[l];
> Sower[l_,{idx_}]:= Sow[idx,{#}] & /@ l;
> Reaper[val_,{place_}] := Sow[val,place];
> Reaper[val_,x_]:= Null;
> Reap[Reap[MapIndexed[Sower, l],_,Reaper],Range[n]][[2]]]
> 
> This works pretty well, but since I am using it on rather large
> inputs, I was wondering if there is a faster way to implement it than
> Reap/Sow, which is sort of counting in unary.
>

Dear Louis,

If sorting the lists is not a problem, the following function will 
probably be faster than the Sow/Reap version in most cases:

specElem[lists__List] := With[
     {spec = Cases[Tally@Join[lists], {el_, 1} :> el]},
     Intersection[spec, #] & /@ {lists}
   ]


In[9]:= ll = RandomInteger[50000, {5, 50000}];

In[10]:= Timing[a = specElem @@ ll;]
Out[10]= {0.437, Null}

In[11]:= Timing[b = SpecialElements @@ ll;]
Out[11]= {7.734, Null}

In[12]:= a === (Sort@First[#] & /@ b)
Out[12]= True

In reality the performance can be very dependent on the input data: the 
number of input lists, and the number of different elements present in 
the lists compared to the length of the lists.

Szabolcs


  • Prev by Date: Re: Mathematica question
  • Next by Date: Problems with Dynamic Updating and Java Runtime
  • Previous by thread: Re: Better way to write this
  • Next by thread: DataRange in ListPlot