Znajdowanie mediany listy w Pythonie

181

Jak znaleźć medianę listy w Pythonie? Lista może mieć dowolny rozmiar, a numery nie są gwarantowane w żadnej określonej kolejności.

Jeśli lista zawiera parzystą liczbę elementów, funkcja powinna zwrócić średnią z dwóch środkowych.

Oto kilka przykładów (posortowanych do celów wyświetlania):

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
źródło
9
Odpowiedzi tutaj są dobre, więc myślę, że chcę, aby była to w przybliżeniu kanoniczna odpowiedź na znalezienie median, w dużej mierze po to, bym mógł to zamknąć . Pamiętaj, że to pytanie ma 30 tysięcy wyświetleń. Byłbym wdzięczny, gdyby to pytanie nie zostało w żaden sposób zamknięte lub zapomniane, aby mogło pozostać w wynikach wyszukiwania i zamiast tego wyssać te widoki.
Veedrac

Odpowiedzi:

213

Python 3.4 ma statistics.median:

Zwraca medianę (wartość środkowa) danych liczbowych.

Gdy liczba punktów danych jest nieparzysta, zwróć środkowy punkt danych. Gdy liczba punktów danych jest parzysta, mediana jest interpolowana przez przyjęcie średniej z dwóch wartości średnich:

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

Stosowanie:

import statistics

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

statistics.median(items)
#>>> 3

Jest również dość ostrożny z typami:

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

from decimal import Decimal
statistics.median(map(Decimal, items))
#>>> Decimal('3')
Veedrac
źródło
Idealne, działało dla mnie, aby dodać to, pip3 install itunizeraby dodać dane mediany do wyników zapytania. Pozdrawiam
jamescampbell
Co jeśli chcesz znaleźć medianę posortowanej tablicy. Nie można więc użyć wbudowanej funkcji statystyki.median, ponieważ zwolni ona podczas sortowania ponownie
GilbertS
2
@GilbertS Następnie spójrz na środkowy element lub uśrednij środkowe dwa.
Veedrac
163

(Pracuje z ):

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

Dla użyj statistics.median:

>>> from statistics import median
>>> median([5, 2, 3, 8, 9, -2])
4.0
AJ Uppal
źródło
9
Chociaż nie pisze funkcji, jest to jednak bardziej „pytoniczne” rozwiązanie
imho
6
@dartdog Nie bardzo; nie zaleca się przymuszania do tablicy Numpy bez uzasadnionego powodu. Zmusiłeś typy i, co gorsza, utraciłeś wsparcie dla dowolnych typów.
Veedrac
1
Zdobyte punkty, przydatne.
lotnik
3
Ta funkcja jest jednak znacznie bardziej pracochłonna, niż trzeba.
Martijn Pieters
3
PEP 450 stanowi dobry argument przeciwko nieużywaniu biblioteki. W końcu popełnisz błąd.
Alex Harvey
51

Funkcja sorted () jest do tego bardzo pomocna. Użyj posortowanej funkcji, aby uporządkować listę, a następnie po prostu zwróć środkową wartość (lub uśrednij dwie środkowe wartości, jeśli lista zawiera parzystą liczbę elementów).

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
źródło
Jest to jednak bardzo nieefektywne: sortowanie w znacznie gorszym przypadku (Theta (n lg n)) jest znacznie więcej pracy niż wybór mediany (Theta (n)) ...
Jeremy
12

Oto czystsze rozwiązanie:

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

Uwaga: odpowiedź została zmieniona, aby uwzględnić sugestie w komentarzach.

Batuhan Ulug
źródło
7
float(sum(…) / 2)należy zastąpić sum(…) / 2.0; w przeciwnym razie, jeśli sum(…)jest liczbą całkowitą, otrzymasz zmiennoprzecinkową liczbę całkowitą. Na przykład: float(sum([3, 4]) / 2)jest 3.0, ale sum([3, 4]) / 2.0jest 3.5.
musiphil
Dla kompletności @musiphil: tylko w python 2 i tylko jeśli jeszcze tego nie zrobiłeś from __future__ import division.
Chris L. Barnes,
11

Możesz wypróbować algorytm szybkiego wyboru , jeśli potrzebne są krótsze czasy działania średniej wielkości liter. Quickselect ma średnią (i najlepszą) sprawność O(n), chociaż może skończyć się O(n²)w zły dzień.

Oto implementacja z losowo wybraną osią obrotu:

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)

Możesz w prosty sposób zmienić to w metodę znajdowania median:

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

Jest to bardzo niezoptymalizowane, ale jest mało prawdopodobne, że nawet zoptymalizowana wersja osiągnie lepsze wyniki niż Tim Sort (wbudowany CPython sort), ponieważ jest to naprawdę szybkie . Próbowałem wcześniej i przegrałem.

Veedrac
źródło
Dlaczego więc nawet o tym myśleć, jeśli sort () jest szybszy?
Maks.
@Max Jeśli używasz PyPy, lub jakiegoś typu, którego nie możesz sortłatwo, lub chcesz napisać rozszerzenie C dla szybkości itp.
Veedrac
10

Oczywiście możesz użyć wbudowanych funkcji, ale jeśli chcesz stworzyć własne, możesz zrobić coś takiego. Sztuką jest użycie operatora ~, który zamienia liczbę dodatnią na ujemną. Na przykład ~ 2 -> -3 i użycie wartości ujemnej dla listy w Pythonie policzy elementy od końca. Więc jeśli masz środek == 2, to zajmie trzeci element od początku i trzeci element od końca.

def median(data):
    data.sort()
    mid = len(data) // 2
    return (data[mid] + data[~mid]) / 2
Vlad Bezden
źródło
8

Możesz użyć, list.sortaby uniknąć tworzenia nowych list sortedi sortować listy w miejscu.

Nie powinieneś także używać listjako nazwy zmiennej, ponieważ przesłania ona własną listę Pythona .

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]
Padraic Cunningham
źródło
5
Proste funkcje narzędziowe prawdopodobnie nie powinny mutować żadnych argumentów (zwłaszcza jeśli nazwa funkcji to rzeczownik IMO). Również użycie posortowanej funkcji .sort () oznacza, że ​​argument nie musi być listą. Może to być dowolny iterator.
Czy S
1
Chodziło mi o funkcję mutującą listę. Wspomniałem o wsparciu dowolnego iterowalnego jako miłego posortowanego efektu ubocznego, ale to nie jest jego główna korzyść. Z jednej strony spodziewałbym się, że mediana (lista) będzie działać jak prawie wszystkie inne wbudowane funkcje matematyczne. next () mutuje, ale nie mogę wymyślić żadnych innych. Mutacja niespodzianka to bolesna dupa podczas debugowania.
Czy S
@WillS, jak to jest zaskoczeniem, gdy jest udokumentowane? Co jeśli masz do czynienia z dużymi danymi lub masz ograniczoną ilość pamięci i nie możesz wykonać kopii listy, co wtedy?
Padraic Cunningham,
2
Spraw, by funkcja oczekiwała posortowanej listy i udokumentuj ją. mylist.sort(); middle(mylist), ale z pewnością jest to kwestia gustu. Po prostu uważam, że mutacja powinna być zarezerwowana dla metod, o ile to możliwe. Przyczyna list.sort () zwraca None zamiast samej listy, aby zachowanie było jak najbardziej oczywiste i jasne. Ukrywanie wszystkiego w dokumentacji jest jak ukrywanie drobnych druków.
Czy S
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
źródło
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
Bulent
źródło
1
Wygląda na to, że pierwszy wiersz kodu został pominięty, możesz rozwiązać ten problem, edytując swój post i wcinając nagłówek funkcji 4 spacjami.
Johan
4

Moje rozwiązanie opublikowałem w implementacji w Pythonie algorytmu „mediana median” , który jest nieco szybszy niż użycie sort (). Moje rozwiązanie wykorzystuje 15 liczb na kolumnę, dla prędkości ~ 5N, która jest większa niż prędkość ~ 10N przy użyciu 5 liczb na kolumnę. Optymalna prędkość wynosi ~ 4N, ale mogę się mylić.

Na prośbę Toma w jego komentarzu dodałem tutaj mój kod w celach informacyjnych. Uważam, że kluczową częścią szybkości jest użycie 15 liczb na kolumnę zamiast 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)
użytkownik5818263
źródło
3

Oto, co wymyśliłem podczas tego ćwiczenia w 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
źródło
2

funkcja mediany

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
Юрий Мойдом Киев
źródło
2

Miałem pewne problemy z listami wartości zmiennoprzecinkowych. Skończyło się na tym, że użyłem fragmentu kodu ze statystyki python3.median i działa idealnie z wartościami zmiennoprzecinkowymi bez importowania. źródło

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
Daniel
źródło
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
źródło
1

Zdefiniowałem funkcję mediany dla listy liczb jako

def median(numbers):
    return (sorted(numbers)[int(round((len(numbers) - 1) / 2.0))] + sorted(numbers)[int(round((len(numbers) - 1) // 2.0))]) / 2.0
Fred Beck
źródło
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])
Luke Willey
źródło
3
Chociaż ten kod może odpowiedzieć na pytanie, zapewnienie dodatkowego kontekstu dotyczącego tego, dlaczego i / lub jak ten kod odpowiada na pytanie, poprawia jego długoterminową wartość.
rollstuhlfahrer
1
Bardzo mi przykro! Właśnie zacząłem, Stack Overflow, i nie wiem, jak dodać podsumowanie ....
Luke Willey
Kliknij link „Edytuj” pod postem i dodaj podsumowanie, a następnie zapisz.
Robert Columbia,
1

mediana fukcji:

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
źródło
1

W przypadku, gdy potrzebujesz dodatkowych informacji o rozmieszczeniu listy, metoda percentylowa prawdopodobnie będzie przydatna. A wartość mediany odpowiada 50. percentylowi listy:

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
źródło
1

Prosta funkcja zwracająca medianę z podanej listy:

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

jeśli chcesz korzystać z biblioteki, możesz po prostu to zrobić;

import statistics

statistics.median([9, 12, 20, 21, 34, 80])
AG
źródło
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]))
sim
źródło
0

Bardziej uogólnionym podejściem do mediany (i percentyli) byłoby:

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
źródło
-2

Oto żmudny sposób na znalezienie mediany bez użycia medianfunkcji:

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
Podoba mi się
źródło
Czy to bańka? Czemu?
Ry-
dlaczego zamieniasz wartości?
ravi tanwar
-3

To bardzo proste;

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

I możesz użyć wartości zwracanej w ten sposób median = median(anyList)

Farhan
źródło
1
Mediana wymaga posortowania tablicy przed znalezieniem punktu środkowego.
Saurabh Jain
sListzwraca posortowaną tablicę. Nie zwraca mediany
Farhan