“中位数中位数”算法的Python实现

Question

我用Python写了中位数算法的实现，但是它似乎没有输出正确的结果，而且对我来说也不是线性复杂度，你有什么想法吗？

def select(L):
    if len(L) < 10:
        L.sort()
        return L[int(len(L)/2)]
    S = []
    lIndex = 0
    while lIndex+5 < len(L)-1:
        S.append(L[lIndex:lIndex+5])
        lIndex += 5
    S.append(L[lIndex:])
    Meds = []
    for subList in S:
        print(subList)
    Meds.append(select(subList))
    L2 = select(Meds)
    L1 = L3 = []
    for i in L:
        if i < L2:
            L1.append(i)
        if i > L2:
            L3.append(i)
    if len(L) < len(L1):
        return select(L1)
    elif len(L) > len(L1) + 1:
        return select(L3)
    else:
        return L2

该函数的调用方式如下：

L = list(range(100))
shuffle(L)
print(select(L))

LE: 抱歉。GetMed 是一个简单的函数，它只是对列表进行排序并返回 len(list) 处的元素，应该在那里选择 select，我已经修复了，但仍然得到错误结果。至于缩进，代码没有错误，我看不出有什么问题 :-??

LE2: 我期望得到 50（对于当前 L），它给我输出从 30 到 70，没有更多也没有更少（目前为止）

LE3: 非常感谢，这解决了问题，现在它可以工作了。但我很困惑，我试图比较这种方法和天真的方法之间的差异，即我仅仅对数组进行排序并输出结果。从我到目前为止所读到的内容来看，select 方法的时间复杂度应该是 O(n) 确定性选择。虽然我可能无法与 Python 开发人员的优化竞争，但我确实希望得到比我得到的更接近的结果，例如，如果我将列表的范围更改为 10000000，则 select 在 84.10837116255952 秒内输出结果，而排序和返回方法则在 18.92556029528825 秒内完成。有哪些好的方法可以使此算法更快？

- cpp_ninja

---

请修复您的格式。缩进似乎出了问题。 - Helgi

getMed()未定义。你得到了什么错误输出？你期望得到什么输出？ - Joel Cornett

Answer 1

1）您的代码缩进有误，请尝试以下方式：

def select(L):
    if len(L) < 10:
        L.sort()
        return L[int(len(L)/2)]
    S = []
    lIndex = 0
    while lIndex+5 < len(L)-1:
        S.append(L[lIndex:lIndex+5])
        lIndex += 5
    S.append(L[lIndex:])
    Meds = []
    for subList in S:
        print(subList)
        Meds.append(select(subList))
    L2 = select(Meds)
    L1 = L3 = []
    for i in L:
        if i < L2:
            L1.append(i)
        if i > L2:
            L3.append(i)
    if len(L) < len(L1):
        return select(L1)
    elif len(L) > len(L1) + 1:
        return select(L3)
    else:
        return L2

2) 你使用的方法并没有返回中位数，它只返回一个离中位数不太远的数字。要得到中位数，你需要计算有多少个数字大于你的伪中位数，如果大多数数字都大于伪中位数，则用大于伪中位数的数字重复算法，否则用其他数字重复。

def select(L, j):
    if len(L) < 10:
        L.sort()
        return L[j]
    S = []
    lIndex = 0
    while lIndex+5 < len(L)-1:
        S.append(L[lIndex:lIndex+5])
        lIndex += 5
    S.append(L[lIndex:])
    Meds = []
    for subList in S:
        Meds.append(select(subList, int((len(subList)-1)/2)))
    med = select(Meds, int((len(Meds)-1)/2))
    L1 = []
    L2 = []
    L3 = []
    for i in L:
        if i < med:
            L1.append(i)
        elif i > med:
            L3.append(i)
        else:
            L2.append(i)
    if j < len(L1):
        return select(L1, j)
    elif j < len(L2) + len(L1):
        return L2[0]
    else:
        return select(L3, j-len(L1)-len(L2))

警告： L = M = [] 不等于 L = [] 和 M = []

- Thomash

---

对于简单测试案例1，2，3，4，4，5，6，12，17，20将会失败。它返回的是5，但应该是4.5。 - waka-waka-waka

@VikhyathReddy 不，4.5不是这个序列的一个元素，怎么可能成为中位数呢？ - Thomash

@Jblasco 如果返回一个不在输入中的元素，则根据您需要中位数的情况可能不正确。在这个例子中，有一组整数，您想返回一个分数，这可能不合适，对于整数，您知道有一个具有良好属性的超集，允许您返回4和5之间的某些内容，但它不适用于任何类型的对象。无法拥有完美的中位数定义，既保证存在性又保证唯一性，但我的定义对于所有实际目的而言已经足够好了。 - Thomash

嗨，Thomash，也许在这个时候达成不同意更为明智，但我会做最后一次尝试。我不知道是否有其他类型的对象不允许类似的中位数技巧。无论如何，由于中位数的定义，对我来说很清楚，您不能通过始终返回两个较小者之一来给出有偏见的答案。我始终会支持中间两点的平均值，因为缺乏有关分布的更多信息，在4和5之间的点将真正地将列表分为两个元素数量相等的部分。 - Jblasco

我不敢说我的定义足够好以适用于所有实际目的...那太美好了，我绝对确定那是不可能的。 - Jblasco

Answer 2

以下是我的PYTHON实现。为了提高速度，您可能想使用PYPY。

对于您关于速度的问题： 每列5个数字的理论速度为~10N，因此我使用每列15个数字，以实现2倍速度的 ~5N，而最优速度为~4N。但是，我可能对最先进解决方案的最优速度有所疏漏。在我的测试中，我的程序比使用sort()的程序运行稍快。当然，您的情况可能会有所不同。

假设python程序名为"median.py"，一个运行它的例子是"python ./median.py 100"。为了进行速度基准测试，您可能想注释掉验证代码并使用PYPY。

#!/bin/python
#
# 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. return the i-th smallest item of A
        #
        return sorted(A)[i]
    else:
        # 1. partition A into columns of items_per_column items each. items_per_column is odd, say 15.
        # 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 validation.
#
print find_i_th_smallest( L, (len(L) - 1) / 2)

- user5818263