Menemukan median daftar dalam Python

181

Bagaimana Anda menemukan median daftar di Python? Daftar dapat dari berbagai ukuran dan jumlahnya tidak dijamin dalam urutan tertentu.

Jika daftar berisi sejumlah elemen, fungsi harus mengembalikan rata-rata dua tengah.

Berikut adalah beberapa contoh (diurutkan untuk keperluan tampilan):

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
sumber
9
Jawaban di sini bagus, jadi saya pikir saya ingin ini kira-kira jawaban kanonik untuk menemukan median, sebagian besar sehingga saya bisa menutup ini . Perhatikan bahwa pertanyaan itu memiliki 30 ribu tampilan. Saya akan menghargai jika pertanyaan ini tidak ditutup atau dilupakan dengan cara apa pun sehingga dapat tetap pada hasil pencarian dan menyedot pandangan itu sebagai gantinya.
Veedrac

Jawaban:

214

Python 3.4 memiliki statistics.median:

Kembalikan median (nilai tengah) data numerik.

Ketika jumlah titik data ganjil, kembalikan titik data tengah. Ketika jumlah titik data genap, median diinterpolasi dengan mengambil rata-rata dari dua nilai tengah:

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

Pemakaian:

import statistics

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

statistics.median(items)
#>>> 3

Ini cukup berhati-hati dengan tipe, juga:

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

from decimal import Decimal
statistics.median(map(Decimal, items))
#>>> Decimal('3')
Veedrac
sumber
Sempurna, berhasil bagi saya untuk menambahkannya pip3 install itunizeruntuk menambahkan data median ke hasil permintaan. Cheers
jamescampbell
Bagaimana jika Anda ingin menemukan median array yang diurutkan. Jadi, Anda tidak dapat menggunakan fungsi built in stats.median karena akan melambat saat mengurutkan lagi
GilbertS
2
@ GrebertS Lalu lihat elemen tengah, atau rata-rata dua tengah.
Veedrac
163

(Bekerja dengan ):

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

Untuk , gunakan statistics.median:

>>> from statistics import median
>>> median([5, 2, 3, 8, 9, -2])
4.0
AJ Uppal
sumber
9
Meskipun tidak menulis fungsi, ini masih merupakan solusi yang lebih "pythonic" imho
dartdog
6
@dartdog Tidak juga; tidak disarankan untuk memaksa ke array Numpy tanpa alasan yang bagus. Anda telah memaksa jenis dan, lebih buruk, kehilangan dukungan untuk jenis sewenang-wenang.
Veedrac
1
Poin yang diambil, berguna.
dartdog
3
Namun, fungsi ini jauh lebih sulit daripada yang seharusnya.
Martijn Pieters
3
PEP 450 membuat argumen yang bagus untuk tidak menggunakan perpustakaan. Anda akhirnya akan membuat kesalahan.
Alex Harvey
51

Fungsi diurutkan () sangat membantu untuk ini. Gunakan fungsi yang diurutkan untuk memesan daftar, kemudian cukup mengembalikan nilai tengah (atau rata-rata dua nilai tengah jika daftar berisi elemen dalam jumlah genap).

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
sumber
Ini sangat tidak efisien: penyortiran jauh lebih berhasil dalam kasus terburuk (Theta (n lg n)) daripada memilih median (Theta (n)) ...
Jeremy
12

Inilah solusi yang lebih bersih:

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

Catatan: Jawaban berubah untuk memasukkan saran dalam komentar.

Batuhan Ulug
sumber
7
float(sum(…) / 2)harus diganti dengan sum(…) / 2.0; jika tidak, jika sum(…)bilangan bulat, Anda akan mendapatkan versi float dari hasil bagi bilangan bulat. Sebagai contoh: float(sum([3, 4]) / 2)is 3.0, but sum([3, 4]) / 2.0is 3.5.
musiphil
Untuk kelengkapan, @musiphil: hanya di python 2, dan hanya jika Anda belum melakukannya from __future__ import division.
Chris L. Barnes
11

Anda dapat mencoba algoritma pemilihan cepat jika waktu rata-rata berjalan lebih cepat diperlukan. Quickselect memiliki kinerja kasus rata-rata (dan terbaik) O(n), meskipun dapat berakhir O(n²)pada hari yang buruk.

Berikut ini implementasi dengan pivot yang dipilih secara acak:

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)

Anda dapat mengubah ini menjadi metode untuk menemukan 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

Ini sangat tidak dioptimalkan, tetapi tidak mungkin bahkan versi yang dioptimalkan akan mengungguli Tim Sort (bawaan CPython sort) karena itu sangat cepat . Saya sudah mencoba sebelumnya dan saya kalah.

Veedrac
sumber
Jadi mengapa bahkan berpikir tentang ini jika sort () lebih cepat?
Maks
@ Max Jika Anda menggunakan PyPy, atau tipe tertentu Anda tidak dapat sortdengan mudah, atau bersedia untuk menulis ekstensi C untuk kecepatan, dll.
Veedrac
10

Tentu saja Anda dapat menggunakan fungsi-fungsi bawaan, tetapi jika Anda ingin membuatnya sendiri, Anda dapat melakukan sesuatu seperti ini. Kuncinya di sini adalah dengan menggunakan ~ operator yang mengubah angka positif menjadi negatif. Misalnya ~ 2 -> -3 dan menggunakan negatif untuk daftar di Python akan menghitung item dari akhir. Jadi jika Anda memiliki pertengahan == 2 maka akan mengambil elemen ketiga dari awal dan item ketiga dari akhir.

def median(data):
    data.sort()
    mid = len(data) // 2
    return (data[mid] + data[~mid]) / 2
Vlad Bezden
sumber
8

Anda dapat menggunakan list.sortuntuk menghindari membuat daftar baru dengan sorteddan mengurutkan daftar di tempat.

Anda juga tidak boleh menggunakan listnama variabel karena bayangan daftar python sendiri .

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
sumber
5
Fungsi utilitas sederhana mungkin tidak boleh mengubah argumen apa pun (Terutama jika nama fungsi adalah kata benda IMO). Juga menggunakan diurutkan atas .sort () berarti argumen tidak harus menjadi daftar. Bisa jadi iterator apa saja.
Will S
1
Maksud saya adalah tentang fungsi yang mengubah daftar. Saya sebutkan mendukung setiap iterable sebagai efek samping yang bagus dari penyortiran, tapi bukan itu manfaat utamanya. I untuk satu akan mengharapkan median (daftar) bekerja seperti hampir semua builtin atau fungsi matematika lainnya. next () bermutasi, tetapi saya tidak bisa memikirkan yang lain. Mutasi kejutan adalah rasa sakit di pantat untuk debugging.
Will S
@WillS, bagaimana kejutan ketika didokumentasikan? Bagaimana jika Anda berurusan dengan data besar atau Anda memiliki jumlah memori terbatas dan Anda tidak dapat membuat salinan daftar, lalu bagaimana?
Padraic Cunningham
2
Buat fungsi mengharapkan daftar dan dokumen yang diurutkan itu. mylist.sort(); middle(mylist), tapi kemudian itu tak diragukan lagi soal selera. Saya hanya berpikir mutasi secara umum harus disediakan untuk metode sejauh mungkin. Alasan list.sort () mengembalikan None bukannya daftar itu sendiri adalah untuk membuat perilaku sejelas dan sejelas mungkin. Menyembunyikan segala sesuatu dalam dokumentasi adalah seperti menyembunyikan barang-barang dalam cetakan kecil.
Will 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
sumber
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
sumber
1
Sepertinya baris kode pertama Anda ditinggalkan, Anda dapat menyelesaikan ini dengan mengedit posting Anda dan membuat indentasi header fungsi dengan 4 spasi.
Johan
4

Saya memposting solusi saya pada implementasi Python dari algoritma "median median" , yang sedikit lebih cepat daripada menggunakan sort (). Solusi saya menggunakan 15 angka per kolom, untuk kecepatan ~ 5N yang lebih cepat dari kecepatan ~ 10N menggunakan 5 angka per kolom. Kecepatan optimal ~ 4N, tapi saya bisa salah tentang itu.

Per permintaan Tom dalam komentarnya, saya menambahkan kode saya di sini, untuk referensi. Saya percaya bagian penting untuk kecepatan menggunakan 15 angka per kolom, bukan 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)
pengguna5818263
sumber
3

Inilah yang saya pikirkan selama latihan di Codecademy ini:

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
sumber
2

Fungsi median

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
Юрий Мойдом Киев
sumber
2

Saya punya beberapa masalah dengan daftar nilai float. Saya akhirnya menggunakan potongan kode dari python3 statistics.median dan bekerja sempurna dengan nilai float tanpa impor. sumber

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
sumber
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
sumber
1

Saya mendefinisikan fungsi median untuk daftar angka sebagai

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
sumber
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
sumber
3
Sementara kode ini dapat menjawab pertanyaan, memberikan konteks tambahan tentang mengapa dan / atau bagaimana kode ini menjawab pertanyaan meningkatkan nilai jangka panjangnya.
rollstuhlfahrer
1
Aku sangat menyesal! Saya baru saja mulai, Stack Overflow, dan saya tidak tahu bagaimana menambahkan ringkasan ....
Luke Willey
Klik tautan "Edit" di bawah posting Anda dan tambahkan ringkasan, lalu simpan.
Robert Columbia
1

median fuction:

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
sumber
1

Jika Anda memerlukan informasi tambahan tentang distribusi daftar Anda, metode persentil mungkin akan berguna. Dan nilai median sesuai dengan persentil ke-50 dari daftar:

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
sumber
1

Fungsi sederhana untuk mengembalikan median daftar yang diberikan:

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

jika Anda ingin menggunakan perpustakaan, Anda cukup melakukannya;

import statistics

statistics.median([9, 12, 20, 21, 34, 80])
AG
sumber
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
sumber
0

Pendekatan yang lebih umum untuk median (dan persentil) adalah:

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
sumber
-2

Inilah cara yang membosankan untuk menemukan median tanpa menggunakan medianfungsi:

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
Saya suka
sumber
Apakah ini semacam gelembung? Mengapa?
Ry-
mengapa Anda bertukar nilai?
ravi tanwar
-3

Ini sangat sederhana;

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

Dan Anda dapat menggunakan nilai pengembalian seperti ini median = median(anyList)

Farhan
sumber
1
Median mengharuskan Anda untuk mengurutkan array sebelum menemukan titik tengahnya.
Saurabh Jain
sListmengembalikan array yang diurutkan. Tidak mengembalikan median
Farhan