在Python中查找列表的中位数

Question

你如何在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

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

Answer 2

对于python-2.x:

使用numpy.median()做出一个线功能:

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

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

Answer 3

sorted()函数对此非常有帮助.使用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

Answer 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.

注意:答案已更改为在评论中包含建议.

Answer 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),因为它真的很快.我曾经尝试过,但我输了.

Answer 6

当然你可以使用内置函数,但如果你想创建自己的函数,你可以做这样的事情.这里的技巧是使用〜运算符将正数翻转为负数.例如~2 - > -3并且在Python中使用否定列表将从最后计算项目.因此,如果你有mid == 2那么它将从开始的第三个元素和从结尾的第三个元素.

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

Answer 7

您可以使用它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]

Answer 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

Answer 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

Answer 10

返回给定列表中位数的简单函数：

def median(lst):
    lst = sorted(lst)  # Sort the list first
    if len(lst) % 2 == 0:  # Checking if the length is even
        # Applying formula which is sum of middle two divided by 2
        return (lst[len(lst) // 2] + lst[(len(lst) - 1) // 2]) / 2
    else:
        # If length is odd then get middle value
        return lst[len(lst) // 2]

该函数的一些示例median：

>>> median([9, 12, 20, 21, 34, 80])  # Even
20.5
>>> median([9, 12, 80, 21, 34])  # Odd
21

如果你想使用库，你可以简单地这样做：

>>> import statistics
>>> statistics.median([9, 12, 20, 21, 34, 80])  # Even
20.5
>>> statistics.median([9, 12, 80, 21, 34])  # Odd
21

Answer 11

我在“中位数中位数”算法的 Python 实现中发布了我的解决方案，该算法比使用 sort() 快一点。我的解决方案每列使用 15 个数字，速度约为 5N，比每列使用 5 个数字的速度约为 10N 快。最佳速度是~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)