Поиск медианы списка в Python

Ответ 1

В 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')

Ответ 2

(Работает с python-2.x):

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

Для python-3.x используйте statistics.median:

>>> from statistics import median
>>> median([5, 2, 3, 8, 9, -2])
4.0

Ответ 3

Функция 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

Ответ 4

Здесь более чистое решение:

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

Примечание. Ответ изменен для включения предложения в комментарии.

Ответ 5

Вы можете попробовать алгоритм quickselect, если потребуется ускоренное время работы в среднем случае. Quickselect имеет среднюю (и лучшую) производительность корпуса 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), потому что это очень быстро. Я пробовал раньше, и я проиграл.

Ответ 6

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

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

Ответ 7

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

Кроме того, вы не должны использовать list как имя переменной, так как он тень python собственный list.

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]

Ответ 8

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

Ответ 9

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

Ответ 10

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

В запросе Tom Tom в своем комментарии я добавил свой код здесь, для справки. Я считаю, что критическая часть скорости использует 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 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)

Ответ 11

Вот что я придумал во время этого упражнения в 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])

Ответ 12

медианная функция

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

Ответ 13

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

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

Ответ 14

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])

Ответ 15

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

def median(numbers):
    return (sorted(numbers)[int(round((len(numbers) - 1) / 2.0))] + sorted(numbers)[int(round((len(numbers) - 1) // 2.0))]) / 2.0

Ответ 16

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])

Ответ 17

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]))

Ответ 18

Здесь утомительный способ найти медиану без использования функции 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

Ответ 19

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

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)