Блог

Главная - Вопросы по программированию - Быстрый выбор: что не так?

Быстрый выбор: что не так?

#python #algorithm

#python #алгоритм

Вопрос:

Я изучаю алгоритм быстрого выбора, но мой код не работает.

 def qselect(li, k):
    if len(li) <= 1:
        return li

    mid = len(li) // 2
    pivot = li[mid]

    left, equal, right = [], [], []

    for number in li:
        if number < pivot:
            left.append(number)
        elif number > pivot:
            right.append(number)
        else:
            equal.append(number)

    if k < len(left):
        qselect(left, k)
        return left[k-1]
    elif k < len(left)   len(equal):
        return equal[0]
    else:
        qselect(right, k)
        return right[k - len(left) - len(equal)]

li = [2, 36, 5, 21, 8, 13, 11, 20, 5, 4, 1]
k = 8
print(qselect(li,k))
  
 Traceback (most recent call last):
  File "q_median.py", line 39, in <module>
    print(qselect(li,k))
  File "q_median.py", line 30, in qselect
    qselect(right, k)
  File "q_median.py", line 31, in qselect
    return right[k - len(left) - len(equal)]
IndexError: list index out of range

Ошибка «вне индекса», и, насколько я знаю, это означает, что данный индекс больше, чем общая длина списка.

Однако, когда я проверяю длину каждого вложенного списка,

 len(left) = 7 
len(equal) = 1
len(right) = 3

Итак, я ожидал, что будет напечатано right[0] .

Что не так?

Комментарии:

1. Какого результата вы ожидаете?

2. Я думал, что 8-й элемент, который равен ’13’ из исходного списка, распечатан. @l’L’l

3. Вы определили k свой индекс списка k=8 , так и должно быть k=7 , поскольку индекс начинается с 0 .

4. Ну, у меня была такая же мысль, но она по-прежнему возвращает ту же ошибку

5. Взгляните: repl.it/repls/SoulfulTriflingMonitor

Ответ №1:

Что не так, так это то, что вы не проверили заявленные вами длины. Первое, что нужно сделать для отладки, это проверить значения, используемые в строке-нарушителе:

 else:
    qselect(right, k)
    print("right", len(right))
    print(k, len(left), len(equal), k - len(left) - len(equal)) 
    return right[k - len(left) - len(equal)]

Вывод:

 right 1
8 1 1 6
Traceback (most recent call last):
  File "C:UserswdwickarAppDataLocalProgramsPythonPython38ZZZ learningso.py", line 31, in <module>
    print(qselect(li,k))
  File "C:UserswdwickarAppDataLocalProgramsPythonPython38ZZZ learningso.py", line 24, in qselect
    qselect(right, k)
  File "C:UserswdwickarAppDataLocalProgramsPythonPython38ZZZ learningso.py", line 27, in qselect
    return right[k - len(left) - len(equal)]
IndexError: list index out of range

Обратитесь к этому прекрасному сайту отладки для получения дополнительной помощи.

Комментарии:

1. Спасибо! Я обдумал ваш ответ, но теперь мне интересно, почему len(справа) и len (слева) равны 1. Нужно ли добавлять дополнительные строки для объединения фрагментированного списка? Если да, то почему первое условие, если k < len(слева) работает, когда я ставлю небольшое число?

2. Не размышляйте: отслеживайте выполнение. Найдите конкретную точку отказа, а не просите меня провести общий обзор дизайна.

3. Спасибо! Я наконец-то изменил свой код! Я думаю, вы преподаете мне важный урок. Я ценю!

4. Да, постоянное совершенствование — это долгосрочная цель. Не забудьте каким-то образом удалить вопрос: удалить или принять и ответить (даже если вы сами его пишете). Это дает вам небольшой возврат репутации и позволяет Stack Overflow правильно заархивировать вопрос.