Services & ResourcesWolfram ForumsMathGroup Archive

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

Re: Counting list elements above/below a given value

• To: mathgroup at smc.vnet.net
• Subject: [mg17375] Re: Counting list elements above/below a given value
• From: colin at tri.org.au (Colin Rose)
• Date: Thu, 6 May 1999 02:44:02 -0400
• Organization: Theoretical Research Institute
• References: <7g0qv1$drj@smc.vnet.net> <7gbkto$l17@smc.vnet.net>
• Sender: owner-wri-mathgroup at wolfram.com

The problem here is to *efficiently* count the number of elements
in a list above a given value. The list is of form:

    In[1]:=     m = Table[Random[], {280}, {280}];

and the solutions offered to date take form:

    In[2]:=     Count[Flatten[m], x_ /; x > 0.5] // Timing
    Out[2]=     {1.21667 Second, 38905}

    In[3]:=     Length[Select[Flatten[m], # > .5 &]] // Timing
    Out[3]=     {0.983333 Second, 38905}

    In[4]:=     Count[m - .5, _?Positive, {2}] // Timing
    Out[4]=     {0.85 Second, 38905}

    In[5]:=     Length[Select[Flatten[m] - .5, Positive]] // Timing
    Out[5]=     {0.566667 Second, 38905}

    __________________________________________

    This can be improved upon in two respects:

*1* COMPILING: The last solution can still be compiled:

    In[6]:=    MrSpeedy =  Compile[{{m, _Real, 1}, {val, _Real}}, 
                                  Length[Select[m - val, Positive]]]

    In[7]:=    MrSpeedy[Flatten[m], 0.5] // Timing
    Out[7]=    {0.366667 Second, 38905}


*2* BINARY SEARCH: In contrast to the approaches above, one can Sort the
    list, and then use a binary search algorithm to find
    the first element in this sorted list that is larger than VAL.
    Here, I adapt the BinarySearch algorithm provided in the
    
       AddOns -> Extra Packages -> ProgramminginMma 

    directory for our purposes:

    BinarySearchCount[list_, elem_] :=  Module[{lis, n0 = 1, n1, v},
       lis = Flatten[list];  
       lis = If[OrderedQ[lis], lis, Sort[lis]];
        n1 = Length[lis]; 
      While[n0 <= n1,
         v = Floor[(n0 + n1)/2];
         If[ lis[[v]] == elem, Return[Length[lis]-v] ];
         If[ lis[[v]] < elem, n0 = v+1, n1 = v-1 ]
      ];
      Length[lis]-(n0-1)  ]

Let's try it out:


      In[8]:=   BinarySearchCount[m, 0.5] // Timing
      Out[8]=   {0.2 Second, 38905}


Moreover, almost ALL the 'search' time goes into just sorting the list.
In fact, given a SORTED list, the search time is close to zero here:

      In[9]:=    lis = Sort[Flatten[m]]; 

     In[10]:=    BinarySearchCount[lis, 0.5] // Timing
     Out[10]=    {0. Second, 38905}

Cheers

Colin
 

PS: Timings are on a PowerMac Blue G3/400.

-- 
Colin Rose 
tr(I)    -  Theoretical Research Institute
__________________________________________
colin at tri.org.au    http://www.tri.org.au/