Getting average of top 1/3 values

I have a 1-D array with over 100 values that changes depending on the case. I need to find a way to easily determine the highest one-third of the values and then calculate their average. For example, if my array was [1,2,3,4,5,6,7,8,9] the highest 1/3 of the values would be [7,8,9] and then the average would be 8. I just have too many values and the amount of values change every time to do this manually. Any suggestions would be greatly appreciated.

q=np.quantile(arr, 2/3)
arr[arr>q].mean()

It is faster than sort. Because it doesn't really need to sort all values.
Although it is the same order of magnitude.

For example, for an array size 1000000, the sort based solution takes 120 ms on my PC, while this solution takes 36 ms.

But I must admit, for 100 values, there is no need for optimization, and cost is just in overhead probably.

I think Quickselect is probably the way to go.

In numpy you can use np.partition to implement it.

k = int(np.ceil(len(arr) * 2 / 3))
mean = np.partition(arr, k)[k:].mean()

On my computer this is slightly faster than the naive np.sort(arr)[k:].mean() method when len(arr) is 100.

However, when len(arr) is 1_000_000 then this is significantly faster than either np.quantile approach proposed by @chrslg (which likely uses quickselect as well) or the naive sort approach.

Benchmarking

len(arr) == 100 (average of 10_000 trials)
sort: 0.00131 ms
quantile: 0.00923 ms
partition: 0.00117 ms

len(arr) == 1_000_000 (average of 100 trials)
sort: 5.794 ms
quantile: 1.358 ms
partition: 0.792 ms

Its not the most beatiful solution but solves your problem fast.

In this solution i will get the smaller integer if len(vect)/3 is not a integer. I do this because if the lenght of your vector is not divisible by 3 you will have a non integer number for 1/3.
If you want to get the next integer. Ex. len(vect)/3 = 5.6 you want 6. then change math.floor function and use math.ceil.

import math
import numpy as np

vect =  [1,7,3,4,9,6,2,8,5]

np.mean(np.sort(vect)[len(vect)-math.floor(len(vect)/3):])

#Return:
#8 --- the mean of [7,8,9]

First of all, you need to sort this list so the top three values are actually the highest values.

The command used to sort lists in python is <list_object>.sort()

Since I don't have your values I'm gonna generate a list with random values:

from random import randint
values = [random.randint(1,100) for value in range(100)]
values.sort()

This will result in a crescent ordered list.

Now we get the 1/3 equivalent value:

third = round(len(values)/3)

The result is le length of the list divided by three and rounded up.

Now we sum the last 1/3 values of that list:

one_third = sum(values[-third:])/len(values[-third:])

This is what you need, in a pythonic way.

I have a solution similar to the previous one.

from statistics import mean
from math import floor

vect = [1,2,3,4,5,6,7,8,9]

cut = floor(len(vect)/3)

print(max(vect[:cut], vect[cut:2*cut], vect[2*cut:], key=lambda x:mean(x)))

Instead of printing you can return the list with the highest 1/3 values. I used an additional variable cut for the clarity and key in the max function to choose the biggest one based on the mean of the cut fragment.

I took the source array (a Numpy array) as:

arr =  np.array([1, 7, 3, 4, 9, 6, 2, 8, 5, 1])

My first assumption is that it is enough to round down the
size of the source array, so the proper formula can be:

arr.size // 3

The second assumption is that you don't need to perform "full" sort.
It is enough to call np.partition, where:

• The first argument is the source array.
• The second argument is the "threshold": Initial n elements are
  "smaller" and the rest are "bigger".

So the proper threshold, leaving 2/3 of smaller elements should be:

n = arr.size - arr.size // 3

getting 7.

And the partitioning should be called as:

np.partition(arr, n)

To take the "bigger" elemenst (last 1/3), we can use indexing as:

[n:]

so the code to get the "bigger" part is:

np.partition(arr, n)[n:]

getting array([7, 8, 9]).

And to get the mean, we can call np.mean, so the whole code is:

result = np.mean(np.partition(arr, n)[n:])