Python - двоичный поиск слишком медленный и приводит к сбою компьютера - как я могу улучшить алгоритм
Я работал над проблемой бинарного поиска.
Вместо сопоставления одного номера ключа с заданным списком проблема требовала от меня сопоставления списка (списка B) ключей с другим списком (списком A). Если ключ соответствует числу в списке A, то выходные данные должны возвращать первый индекс в A, где присутствует число. Если номер ключа отсутствует в списке А, то вернуть -1
Скажем, что список A и список B:
A = [1, 5, 8, 12, 13]
B = [8, 1, 23, 1, 11]
Поскольку 8 присутствует в обоих списках, выход равен 2, потому что 8 в списке A находится в [2]. Используя эту логику, общий конечный результат должен стать следующим:
matched_list = [2, 0, -1, 0, -1]
Ниже мой код. Было бы очень признательно, если бы вы также могли найти какие-либо логические ошибки в строках, однако меня больше всего беспокоит время выполнения. Когда я нажимаю ввод на своем компьютере, обработка занимает целую вечность, и программное обеспечение (я использовал VS Code) в конечном итоге дает сбой.
У меня было 16 ГБ ОЗУ и Intel Core i7, так что это должно быть не устройство, а алгоритм.
def binary_search(A, B, n):
# We match the numbers in key list, B, to the numbers in A
low, high = 0, n-1
# low limit is initialised to A[0], the first number of list A
# high limit initialised to the last number of the list, A[n-1]
matched_list = []
for i in B:
middle = (high+low)//2
while low <= high:
if i > A[middle]:
low = middle+1
elif i < A[middle]:
high = middle-1
else:
matched_list.append(middle)
if low > high:
return(-1)
return(matched_list)
A = [1, 5, 8, 12, 13]
B = [8, 1, 23, 1, 11]
n = 5 # this is the length of list A
print(binary_search(A, B, n))
Есть ли способ улучшить мой алгоритм?
Ответы 4
Я исправил ошибки в функции. см. этот код:
def binary_search(A, B, n):
matched_list = []
for i in B:
low, high = 0, n - 1
while low <= high:
middle = (high + low) // 2
if i > A[middle]:
low = middle + 1
elif i < A[middle]:
high = middle - 1
else:
matched_list.append(middle)
break
if low > high:
matched_list.append(-1)
return matched_list
В вашем коде
while low <= high:
if i > A[middle]:
low = middle+1
elif i < A[middle]:
high = middle-1
else:
matched_list.append(middle)
Оператор else не ломается, из-за чего он застревает в бесконечном цикле. Добавление оператора break решит эту проблему.
Предложение: поскольку карты/словари, как правило, работают быстрее, вы можете использовать их для эффективного решения этой проблемы в O(N), а не в O(NlogN).
Теперь я вижу свою проблему, спасибо, что напомнили мне об этой петле. Итак, причина того, что моя программа никогда не останавливалась и не выдавала ответ, заключалась в том, что я ее не нарушал....... И да, я посмотрю на карту для улучшения
1-й - вы не можете использовать бинарный поиск, если пространство не отсортировано.
2-й - если вы хотите улучшить алгоритм, используйте карты, и сложность будет линейной.
3-й - если вы хотите использовать бинарный поиск, вы можете легко вставить свои значения в набор, а затем найти ответ с помощью lower_bound.
@cliff_leaf, в вашем случае было бы проще просто использовать dict(), чтобы сохранить числовой индекс в словаре для быстрого поиска O (1) позже с помощью B: (Двоичный поиск, вероятно, не подходит в этом случае.) Вы можете настроить код так, чтобы он прерывался/выходил, когда вы найдете первое совпадающее число - 8 и останавливаетесь, если это то, что вы хотите - найдите первое совпадение.
>>> A = [1, 5, 8, 12, 13]
>>> B = [8, 1, 23, 1, 11]
>>> aa = {n: i for i, n in enumerate(A)}
>>> aa
{1: 0, 5: 1, 8: 2, 12: 3, 13: 4}
>>> for n in B:
if n in aa: print(aa[n])
2
0
0
Ничего себе, если честно, я никогда не думал о таком алгоритме. Словарь и функция перечисления, я посмотрю и реализую их в своей программе. Спасибо
Рад, что это может помочь. Тогда хочешь проголосовать за мой пост?
Думаю, я уже это сделал, возможно, система работала медленно.
Ах, спасибо, так что причина, по которой программа не остановилась, заключалась в том, что я забыл разорвать цикл. Теперь это имеет смысл. И спасибо за исправление другой ошибки