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>To get the mode of the list, you must iterate through the whole list at least once (Technically, you could stop as soon as the count of one of the elements is more than the remaining items in the list, but the efficiency is negligible).</p>

<p>Python has an efficient and easy way to do this with <code>Counter</code>.</p>

<pre><code>from __future__ import division
from collections import Counter
from itertools import islice

data = [1,2,2,3,4,4,4,4]
c = Counter(data)

# Get the mode
mode, mode_n = c.most_common(1)[0]

# Store the cumulative sum and count so we can compute the mean
# Process the most common element (the mode) first since we
# already have that data.
cumulative_sum = mode * mode_n
cumulative_n = mode_n

# Process the remaining elements. most_common returns the remaining
# elements and their counts in descending order by the number of times
# the appear in the original list.  We can skip the first element since
# we've already processed it.  As soon as an element is less numerous
# than half the mode, we can stop processing further elements.
for val, val_n in islice(c.most_common(), 1, None):
    if val_n &lt; mode_n / 2:
        break
    cumulative_sum += val * val_n
    cumulative_n += val_n

# Compute the Mean
avg = cumulative_sum / cumulative_n
</code></pre>

<p>The only thing I'm not completely sure of is how you treat modes that appear an odd number of times.  If the mode appeared <code>5</code> times, do you round up to <code>3</code> or down to <code>2</code> when checking the other elements?</p>

<p>Currently, it's rounding up, but if you wanted to round down, you could just change it to this:</p>

<pre><code>if val_n &lt; mode_n // 2:
</code></pre>

python list numpy average