Нахождение медианы списка в Python

181

Как вы находите медиану списка в Python? Список может быть любого размера, и номера не гарантируются в каком-либо определенном порядке.

Если список содержит четное количество элементов, функция должна вернуть среднее значение из средних двух.

Вот несколько примеров (отсортированных для отображения):

median([1]) == 1
median([1, 1]) == 1
median([1, 1, 2, 4]) == 1.5
median([0, 2, 5, 6, 8, 9, 9]) == 6
median([0, 0, 0, 0, 4, 4, 6, 8]) == 2
ChucksPlace
источник
9
Ответы здесь хорошие, поэтому я думаю, что я хочу, чтобы это был примерно канонический ответ для поиска медиан, в основном, чтобы я мог закрыть это . Обратите внимание, что этот вопрос имеет 30 тысяч просмотров. Я был бы признателен, если бы этот вопрос не был закрыт или забыт каким-либо образом, чтобы он мог остаться в результатах поиска и вместо этого высосать эти представления.
Veedrac

Ответы:

214

Python 3.4 имеет statistics.median:

Вернуть медиану (среднее значение) числовых данных.

Если число точек данных нечетное, вернуть среднюю точку данных. Когда число точек данных является четным, медиана интерполируется путем взятия среднего из двух средних значений:

>>> median([1, 3, 5])
3
>>> median([1, 3, 5, 7])
4.0

Использование:

import statistics

items = [6, 1, 8, 2, 3]

statistics.median(items)
#>>> 3

Это довольно осторожно с типами:

statistics.median(map(float, items))
#>>> 3.0

from decimal import Decimal
statistics.median(map(Decimal, items))
#>>> Decimal('3')
Veedrac
источник
Отлично, мне удалось добавить его, pip3 install itunizerчтобы добавить медианные данные в результаты запроса. Приветствия
jamescampbell
Что делать, если вы хотите найти медиану отсортированного массива. Таким образом, вы не можете использовать встроенную функцию statistics.median, потому что она будет замедляться при повторной сортировке
GilbertS
2
@GilbertS Тогда посмотрите на средний элемент, или усредните средние два.
Ведрак
163

(Работает с ):

def median(lst):
    n = len(lst)
    s = sorted(lst)
    return (sum(s[n//2-1:n//2+1])/2.0, s[n//2])[n % 2] if n else None

>>> median([-5, -5, -3, -4, 0, -1])
-3.5

numpy.median():

>>> from numpy import median
>>> median([1, -4, -1, -1, 1, -3])
-1.0

Для , используйте statistics.median:

>>> from statistics import median
>>> median([5, 2, 3, 8, 9, -2])
4.0
Эй Джей Уппал
источник
9
Хотя он не пишет функцию, он все же является более «питоническим» решением imho
dartdog
6
@dartdog Не совсем; нежелательно приводить к массиву Numpy без веской причины. Вы привели типы и, что еще хуже, потеряли поддержку произвольных типов.
Veedrac
1
Очки взяты, полезны.
Дартдог
3
Однако эта функция гораздо более трудоемка, чем должна быть.
Мартин Питерс
3
PEP 450 дает хороший аргумент против использования библиотеки. Вы в конечном итоге совершите ошибку.
Алекс Харви
51

Функция sorted () очень полезна для этого. Используйте отсортированную функцию, чтобы упорядочить список, а затем просто вернуть среднее значение (или усреднить два средних значения, если список содержит четное количество элементов).

def median(lst):
    sortedLst = sorted(lst)
    lstLen = len(lst)
    index = (lstLen - 1) // 2

    if (lstLen % 2):
        return sortedLst[index]
    else:
        return (sortedLst[index] + sortedLst[index + 1])/2.0
swolfe
источник
Хотя это крайне неэффективно: в худшем случае сортировка - это гораздо больше работы (Theta (n lg n)), чем выбор медианы (Theta (n)) ...
Джереми
12

Вот более чистое решение:

def median(lst):
    quotient, remainder = divmod(len(lst), 2)
    if remainder:
        return sorted(lst)[quotient]
    return sum(sorted(lst)[quotient - 1:quotient + 1]) / 2.

Примечание: ответ изменен, чтобы включить предложение в комментарии.

Батухан Улуг
источник
7
float(sum(…) / 2)следует заменить на sum(…) / 2.0; в противном случае, если sum(…)это целое число, вы получите целочисленную версию с плавающей запятой. Например: float(sum([3, 4]) / 2)есть 3.0, но sum([3, 4]) / 2.0есть 3.5.
Musiphil
Для полноты, @musiphil: только в Python 2, и только если вы еще этого не сделали from __future__ import division.
Крис Л. Барнс
11

Вы можете попробовать алгоритм быстрого выбора , если требуется более быстрое среднее время выполнения. Быстрый выбор имеет среднюю (и лучшую) производительность по случаю O(n), хотя может закончиться O(n²)в плохой день.

Вот реализация со случайно выбранным шарниром:

import random

def select_nth(n, items):
    pivot = random.choice(items)

    lesser = [item for item in items if item < pivot]
    if len(lesser) > n:
        return select_nth(n, lesser)
    n -= len(lesser)

    numequal = items.count(pivot)
    if numequal > n:
        return pivot
    n -= numequal

    greater = [item for item in items if item > pivot]
    return select_nth(n, greater)

Вы можете тривиально превратить это в метод, чтобы найти медианы:

def median(items):
    if len(items) % 2:
        return select_nth(len(items)//2, items)

    else:
        left  = select_nth((len(items)-1) // 2, items)
        right = select_nth((len(items)+1) // 2, items)

        return (left + right) / 2

Это очень неоптимизировано, но маловероятно, что даже оптимизированная версия превзойдет Tim Sort (встроенный в CPython sort), потому что это действительно быстро . Я пробовал раньше, и я проиграл.

Veedrac
источник
Так зачем даже думать об этом, если sort () работает быстрее?
Макс
@Max Если вы используете PyPy, или какой-то другой тип, который вам sortнелегко, или хотите написать расширение C для скорости и т. Д.
Veedrac
10

Конечно, вы можете использовать встроенные функции, но если вы хотите создать свои собственные, вы можете сделать что-то вроде этого. Хитрость здесь в том, чтобы использовать оператор ~, который переворачивает положительное число в отрицательное. Например, ~ 2 -> -3 и использование отрицательного значения for для списка в Python будет считать элементы с конца. Так что, если у вас есть середина == 2, то третий элемент будет начинаться с начала, а третий - с конца.

def median(data):
    data.sort()
    mid = len(data) // 2
    return (data[mid] + data[~mid]) / 2
Влад Безден
источник
8

Вы можете использовать, list.sortчтобы избежать создания новых списков sortedи сортировки списков на месте.

Также вы не должны использовать listв качестве имени переменной, поскольку она скрывает собственный список Python .

def median(l):
    half = len(l) // 2
    l.sort()
    if not len(l) % 2:
        return (l[half - 1] + l[half]) / 2.0
    return l[half]
Падрайк Каннингем
источник
5
Простые служебные функции, вероятно, не должны изменять какие-либо аргументы (особенно, если имя функции является существительным IMO). Также использование sorted over .sort () означает, что аргумент не должен быть списком. Это может быть любой итератор.
Будет ли
1
Моя точка зрения касалась функции, изменяющей список. Я упомянул поддержку любого итерируемого как хороший побочный эффект сортировки, но это не главное преимущество. Я бы, например, ожидал, что медиана (список) будет работать как почти все другие встроенные функции или математические функции. next () видоизменяется, но я не могу думать ни о каких других. Сюрприз мутации является болью в заднице для отладки.
Будет ли
@WillS, как это удивительно, когда это задокументировано? Что если вы имеете дело с большими данными или у вас ограниченный объем памяти и вы не можете сделать копию списка, что тогда?
Padraic Cunningham
2
Сделайте так, чтобы функция ожидала отсортированный список и документировала это. mylist.sort(); middle(mylist), Но это , несомненно , дело вкуса. Я просто думаю, что мутация вообще должна быть зарезервирована для методов, насколько это возможно. Причина, по которой list.sort () возвращает None вместо самого списка, заключается в том, чтобы сделать поведение максимально очевидным и понятным. Сокрытие всего в документации похоже на сокрытие мелким шрифтом.
Будет ли
7
def median(array):
    """Calculate median of the given list.
    """
    # TODO: use statistics.median in Python 3
    array = sorted(array)
    half, odd = divmod(len(array), 2)
    if odd:
        return array[half]
    return (array[half - 1] + array[half]) / 2.0
warvariuc
источник
7
def median(x):
    x = sorted(x)
    listlength = len(x) 
    num = listlength//2
    if listlength%2==0:
        middlenum = (x[num]+x[num-1])/2
    else:
        middlenum = x[num]
    return middlenum
Бюлент
источник
1
Похоже, ваша первая строка кода пропущена, вы можете решить эту проблему, отредактировав ваш пост и вставив в заголовок функции 4 пробела.
Йохан
4

Я разместил свое решение в Python по реализации алгоритма "медиана медиан" , который немного быстрее, чем использование sort (). Мое решение использует 15 чисел на столбец, для скорости ~ 5N, которая быстрее, чем скорость ~ 10N для использования 5 чисел на столбец. Оптимальная скорость ~ 4N, но я могу ошибаться.

По просьбе Тома в своем комментарии я добавил сюда свой код для справки. Я считаю, что критической частью скорости является использование 15 чисел в столбце вместо 5.

#!/bin/pypy
#
# TH @stackoverflow, 2016-01-20, linear time "median of medians" algorithm
#
import sys, random


items_per_column = 15


def find_i_th_smallest( A, i ):
    t = len(A)
    if(t <= items_per_column):
        # if A is a small list with less than items_per_column items, then:
        #
        # 1. do sort on A
        # 2. find i-th smallest item of A
        #
        return sorted(A)[i]
    else:
        # 1. partition A into columns of k items each. k is odd, say 5.
        # 2. find the median of every column
        # 3. put all medians in a new list, say, B
        #
        B = [ find_i_th_smallest(k, (len(k) - 1)/2) for k in [A[j:(j + items_per_column)] for j in range(0,len(A),items_per_column)]]

        # 4. find M, the median of B
        #
        M = find_i_th_smallest(B, (len(B) - 1)/2)


        # 5. split A into 3 parts by M, { < M }, { == M }, and { > M }
        # 6. find which above set has A's i-th smallest, recursively.
        #
        P1 = [ j for j in A if j < M ]
        if(i < len(P1)):
            return find_i_th_smallest( P1, i)
        P3 = [ j for j in A if j > M ]
        L3 = len(P3)
        if(i < (t - L3)):
            return M
        return find_i_th_smallest( P3, i - (t - L3))


# How many numbers should be randomly generated for testing?
#
number_of_numbers = int(sys.argv[1])


# create a list of random positive integers
#
L = [ random.randint(0, number_of_numbers) for i in range(0, number_of_numbers) ]


# Show the original list
#
# print L


# This is for validation
#
# print sorted(L)[int((len(L) - 1)/2)]


# This is the result of the "median of medians" function.
# Its result should be the same as the above.
#
print find_i_th_smallest( L, (len(L) - 1) / 2)
user5818263
источник
3

Вот что я придумал во время этого упражнения в Codecademy:

def median(data):
    new_list = sorted(data)
    if len(new_list)%2 > 0:
        return new_list[len(new_list)/2]
    elif len(new_list)%2 == 0:
        return (new_list[(len(new_list)/2)] + new_list[(len(new_list)/2)-1]) /2.0

print median([1,2,3,4,5,9])
BynderRox
источник
2

Средняя функция

def median(midlist):
    midlist.sort()
    lens = len(midlist)
    if lens % 2 != 0: 
        midl = (lens / 2)
        res = midlist[midl]
    else:
        odd = (lens / 2) -1
        ev = (lens / 2) 
        res = float(midlist[odd] + midlist[ev]) / float(2)
    return res
Юрий Мойдом Киев
источник
2

У меня были некоторые проблемы со списками значений с плавающей точкой. В итоге я использовал фрагмент кода из python3 statistics.median и отлично работает со значениями с плавающей запятой без импорта. источник

def calculateMedian(list):
    data = sorted(list)
    n = len(data)
    if n == 0:
        return None
    if n % 2 == 1:
        return data[n // 2]
    else:
        i = n // 2
        return (data[i - 1] + data[i]) / 2
Даниил
источник
2
def midme(list1):

    list1.sort()
    if len(list1)%2>0:
            x = list1[int((len(list1)/2))]
    else:
            x = ((list1[int((len(list1)/2))-1])+(list1[int(((len(list1)/2)))]))/2
    return x


midme([4,5,1,7,2])
vk123
источник
1

Я определила медианную функцию для списка чисел как

def median(numbers):
    return (sorted(numbers)[int(round((len(numbers) - 1) / 2.0))] + sorted(numbers)[int(round((len(numbers) - 1) // 2.0))]) / 2.0
Фред Бек
источник
1
def median(array):
    if len(array) < 1:
        return(None)
    if len(array) % 2 == 0:
        median = (array[len(array)//2-1: len(array)//2+1])
        return sum(median) / len(median)
    else:
        return(array[len(array)//2])
Люк Уилли
источник
3
Хотя этот код может ответить на вопрос, предоставление дополнительного контекста относительно того, почему и / или как этот код отвечает на вопрос, повышает его долгосрочную ценность.
rollstuhlfahrer
1
Мне очень жаль! Я только начал, Переполнение стека, и я не знаю, как добавить резюме ....
Люк Уилли
Нажмите ссылку "Изменить" под своим сообщением и добавьте резюме, затем сохраните.
Роберт Колумбия
1

средняя функция:

def median(d):
    d=np.sort(d)
    n2=int(len(d)/2)
    r=n2%2
    if (r==0):
        med=d[n2] 
    else:
        med=(d[n2] + data[m+1]) / 2
    return med
FATI
источник
1

Если вам нужна дополнительная информация о распределении вашего списка, метод процентили, вероятно, будет полезен. И медианное значение соответствует 50-му процентилю списка:

import numpy as np
a = np.array([1,2,3,4,5,6,7,8,9])
median_value = np.percentile(a, 50) # return 50th percentile
print median_value 
Gabriel123
источник
1

Простая функция для возврата медианы заданного списка:

def median(lsts):
        if len(lsts)%2 == 0:  #Checking if the length is even
            return (lsts[len(lsts)//2] + lsts[(len(lsts) - 1) //2]) //2 # Applying formula which is sum of middle two divided by 2
            
        else:
            return lsts[len(lsts)//2] # If length is odd then get middle value
            
        
median([2,3,5,6,10]) #Calling function

если вы хотите использовать библиотеку, вы можете просто сделать это;

import statistics

statistics.median([9, 12, 20, 21, 34, 80])
AG
источник
0
import numpy as np
def get_median(xs):
        mid = len(xs) // 2  # Take the mid of the list
        if len(xs) % 2 == 1: # check if the len of list is odd
            return sorted(xs)[mid] #if true then mid will be median after sorting
        else:
            #return 0.5 * sum(sorted(xs)[mid - 1:mid + 1])
            return 0.5 * np.sum(sorted(xs)[mid - 1:mid + 1]) #if false take the avg of mid
print(get_median([7, 7, 3, 1, 4, 5]))
print(get_median([1,2,3, 4,5]))
сим
источник
0

Более обобщенный подход для медианы (и процентилей) будет следующим:

def get_percentile(data, percentile):
    # Get the number of observations
    cnt=len(data)
    # Sort the list
    data=sorted(data)
    # Determine the split point
    i=(cnt-1)*percentile
    # Find the `floor` of the split point
    diff=i-int(i)
    # Return the weighted average of the value above and below the split point
    return data[int(i)]*(1-diff)+data[int(i)+1]*(diff)

# Data
data=[1,2,3,4,5]
# For the median
print(get_percentile(data=data, percentile=.50))
# > 3
print(get_percentile(data=data, percentile=.75))
# > 4

# Note the weighted average difference when an int is not returned by the percentile
print(get_percentile(data=data, percentile=.51))
# > 3.04
conmak
источник
-2

Вот утомительный способ найти медиану без использования medianфункции:

def median(*arg):
    order(arg)
    numArg = len(arg)
    half = int(numArg/2)
    if numArg/2 ==half:
        print((arg[half-1]+arg[half])/2)
    else:
        print(int(arg[half]))

def order(tup):
    ordered = [tup[i] for i in range(len(tup))]
    test(ordered)
    while(test(ordered)):
        test(ordered)
    print(ordered)


def test(ordered):
    whileloop = 0 
    for i in range(len(ordered)-1):
        print(i)
        if (ordered[i]>ordered[i+1]):
            print(str(ordered[i]) + ' is greater than ' + str(ordered[i+1]))
            original = ordered[i+1]
            ordered[i+1]=ordered[i]
            ordered[i]=original
            whileloop = 1 #run the loop again if you had to switch values
    return whileloop
Мне нравиться
источник
Этот пузырь типа? Зачем?
Ry-
почему вы меняете значения?
Рави Танвар
-3

Это очень просто;

def median(alist):
    #to find median you will have to sort the list first
    sList = sorted(alist)
    first = 0
    last = len(sList)-1
    midpoint = (first + last)//2
    return midpoint

И вы можете использовать возвращаемое значение, как это median = median(anyList)

Фархан
источник
1
Медиана требует, чтобы вы отсортировали массив прежде, чем найдете середину.
Саурабх Джейн
sListвернуть отсортированный массив. Не возвращает медиану
Фархан