Most efficient way to get average of all elements in list where each element occurs at least half as many times as the mode of the list
<p>I have a specific task to perform in python. Efficiency and speed are the most important here which is why I'm posting the question. </p>

<p>I need to get the average of items in a list, but only of the items that occur as least half as many times as the mode of the list occurs. </p>

<p>For instance if the list is <code>[1,2,2,3,4,4,4,4]</code> I need to get the average of <code>2,2,4,4,4,4</code>. Since <code>4</code> is the mode of the list and occurs four times, the only element that occurs at least half of four times (twice) is <code>2</code>. Thus I discount all occurrences <code>1</code> and <code>3</code> and average the list. </p>

<p>I'm not sure what the most efficient way to do this is. I know how to brute force calculate the solution, but that's obviously not the quickest implementation. </p>

<p>I thought it may be best to use a <code>numpy</code> array, but since I'll be appending to the list quite frequently, I didn't think this would be the best choice. </p>

<p>My other thoughts have been to possibly use a <code>Counter</code> based approach from the <code>collections</code> module. But once again, I don't know if it's the fastest or most sensible for performing a rather weird calculation like this. </p>

<p>If you decide to use numpy, here's a concise method using <code>numpy.unique</code> and <code>numpy.average</code>:</p>

<pre><code>In [54]: x = np.array([1, 2, 2, 3, 4, 4, 4, 4])

In [55]: uniqx, counts = np.unique(x, return_counts=True)

In [56]: keep = counts &gt;= 0.5*counts.max()

In [57]: np.average(uniqx[keep], weights=counts[keep])
Out[57]: 3.3333333333333335
</code></pre>

<p>Note that <code>np.unique</code> sorts its argument, so its time complexity is O(n*log(n)), while the problem can be solved with an algorithm that is O(n).  Do some timing comparisons using arrays with lengths that will be typical before you rule out this method based on its asymptotic time complexity.</p>

python list numpy average