Вопрос по python, algorithm – Python-реализация алгоритма «медиана медиан»

2

Я написал эту реализацию алгоритма медианы медиан в 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))

Л.Э .: Извините. GetMed была функцией, которая просто сортировала список и возвращала элемент в len (list), он должен был быть выбран там, я исправил это сейчас, но все же я получаю неправильные результаты. Что касается отступа, код работает без ошибок, и я не вижу в этом ничего плохого: - ??

LE2: Я ожидаю 50 (для текущего L), это дает мне выходы от 30 до 70, не больше, не меньше (пока)

LE3: Большое спасибо, это помогло, теперь это работает. Я путаюсь, хотя, я пытаюсь провести сравнение между этим методом и наивным, где я просто сортирую массив и выводю результаты. Теперь, из того, что я прочитал, временная сложность метода select должна быть O (n)Детерминированный отбор, Хотя я, вероятно, не могу конкурировать с разработчиками Python для оптимизации, я ожидал более близких результатов, чем получил, например, если я изменю диапазон списка на 10000000, select выводит результат за 84.10837116255952 секунд, а метод сортировки и возврата делает это в 18.92556029528825. Какие есть хорошие способы сделать этот алгоритм быстрее?

getMed() не определено. Какой вывод вы получаете неправильно, какой вывод вы ожидаете? Joel Cornett
Пожалуйста, исправьте форматирование. Отступы, кажется, сломаны. Helgi

Ваш Ответ

2   ответа
2

1) Ваш код неверен, попробуйте это:

def select(L):
    if len(L) < 10:
        L.        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.
        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? tommy.carstensen
Старый пост, но @ вака-вака-вака прав. Медиана списка четных чисел обычно принимается как среднее из ДВУХ центральных элементов, в противном случае, если вы возьмете более низкое или более высокое значение, вы будете смещены. Jblasco
@ Jblasco Возвращение элемента, которого нет на входе, может быть неправильным, в зависимости от того, для чего вам нужна медиана. В этом примере есть набор целых чисел, и вы хотите вернуть дробное число, которое может быть неуместным, для целых чисел вы знаете, что существует надмножество с хорошими свойствами, которое позволяет вам возвращать что-то между 4 и 5, но не будет работать на любой объект. Невозможно иметь идеальное определение медианы, которое гарантировало бы как существование, так и единственность, но мое определение достаточно хорошо длявс практические цели. Thomash
Сбой для простого теста 1, 2, 3, 4, 4, 5, 6, 12, 17, 20 # возвращает 5, должен возвращать 4,5 waka-waka-waka
@ VikhyathReddy Нет, 4.5 не является элементом последовательности, как это может быть медиана? Thomash
0

ь вместо PYPY.

На твой вопрос о СКОРОСТИ: Теоретическая скорость для 5 чисел на столбец составляет ~ 10N, поэтому я использую 15 чисел на столбец для скорости 2X при ~ 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)

Похожие вопросы