Реализация быстрого выбора в python. функция нестабильна и возвращает разные значения.

Я попытался реализовать быстрый выбор, чтобы найти наименьшее число m'th в списке. Когда я запускаю программу, она возвращает правильные значения когда-то и некорректные значения других времен в одном массиве. Что я делаю неправильно, это кодРеализация быстрого выбора в python. функция нестабильна и возвращает разные значения.

def select_mth_smallest(A, m): 
    pivot = np.random.choice(A) 
    # split into 3 partitions 
    A1 = [] 
    A2 = [] 
    A3 = [] 
    for item in A: 
     if item < pivot: 
      A1.append(item) 
     if item > pivot: 
      A3.append(item) 
     else: 
      A2.append(item) 
    #find where m'th largest element is and recurse accordingly 
    if len(A1) >= m: 
     return select_mth_smallest(A1, m) 
    elif (len(A1) + len(A2)) >= m: 
     return pivot 
    else: 
     return select_mth_smallest(A3,m - (len(A1)+len(A2)))

Вот вход, в котором алгоритм терпит неудачу.

A = [1,2,3,4,5] 

select_mth_smallest(A,5)

При повторном выполнении вышеуказанного утверждения я получаю, 5 (правильно) и 4 (неверно) чередующе.

Одна вещь, которая особенно меня озадачивает (я новичок в python), заключается в том, что я получаю разные возвращаемые значения для функции при повторении с одним и тем же входом. Выглядит довольно спорадически. BTW Я использую Jupyter

источник

2016-05-02 Prag1

Посмотрите на свои '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '. Один из них ошибочен. – user2357112

Извините, я проверил, это кажется правильным. Можете быть более конкретными. Спасибо – Prag1

Является ли он самым большим или самым маленьким? Ваш заголовок, имя функции и комментарий, похоже, не согласны. ~~ Также, что произойдет, если pivot окажется наименьшим элементом в текущем 'A'? Тогда 'A1' будет пустым, поскольку ничто не меньше, чем точка поворота, и вы будете вызывать' select_mth_smallest ([], m) ', и в этом случае [' numpy.random.choice' будет вызывать 'ValueError'] (http://docs.scipy.org/doc/numpy-1.10.0/reference/generated/numpy.random.choice.html).~~ Есть несколько крайних случаев, которые вам нужно учитывать. Что, если стержень является m-м наименьшим/наибольшим элементом? Изменить: неверно прочитать условные выражения – KevinOrr

Вы добавляете некоторые элементы в несколько разделов.

if item < pivot: 
     A1.append(item) 
    if item > pivot: 
     A3.append(item) 
    else: 
     A2.append(item)

A1 это набор элементов меньше, чем стержень. A3 - это набор предметов, которые больше, чем ось. A2, однако, представляет собой набор позиций меньше или равно на ось, потому что 2-й оператор if выполняет для все элементы, и та или иная ветка будет выполнена.

Вы хотите один, один if с предложением elif и else.

if item < pivot: 
     A1.append(item) 
    elif item > pivot: 
     A3.append(item) 
    else: 
     A2.append(item)

источник

2016-05-02 20:50:26 chepner

Реализация быстрого выбора в python. функция нестабильна и возвращает разные значения.

ответ

Смежные вопросы