Реализация Python алгоритма «медианы медианов»

Я написал эту реализацию медианы алгоритма медианов в 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), он должен был быть там выбран, я исправил его сейчас, но все же я получаю неправильные результаты. Что касается отступов, код работает без ошибок, и я не вижу в этом ничего плохого: – ??

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

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

2 Solutions collect form web for “Реализация Python алгоритма «медианы медианов»”

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 = []

Ниже приведена моя реализация PYTHON. Для большей скорости вы можете использовать PYPY вместо этого.

Для вашего вопроса о SPEED: теоретическая скорость для 5 чисел на столбец составляет ~ 10 Н, поэтому я использую 15 номеров на столбец, для скорости 2X при ~ 5 Н, а оптимальная скорость – 4 Н. Но я мог ошибаться в отношении оптимальной скорости самого современного решения. В моем собственном тесте моя программа работает немного быстрее, чем с помощью 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) 
  • Самая длинная повторяемая (k раз) подстрока
  • Действительно ли эта основная функция работает?
  • Как разделить текст на куски, минимизируя решение?
  • Python Найдите номер большинства в O (n) времени и O (1) память
  • Определить период неизвестного источника
  • Алгоритм создания трехмерной гильбертовой пространственно-заполняющей кривой в Python
  • Определить невыпуклую оболочку набора отрезков
  • Как вы можете распараллеливать регулярный поиск одной длинной строки?
  • Python - лучший язык программирования в мире.