как искать большой массив имен с помощью бинарного поиска - PullRequest
Новая
       8

как искать большой массив имен с помощью бинарного поиска

0 голосов
/ 05 июля 2018

Я новичок в python. Я реализую бинарный поиск по большому массиву значений, где длина массива равна 258000, я проверил мой код на линейном поиске, он также падает, когда он превышает максимальную глубину рекурсии, поэтому я использую двоичный файл. но двоичный файл также не работает на этом большом массиве, так как я тестирую свой код на маленьком массиве, он работает нормально, вот код: 

A = ['John', 'William', 'James', 'Charles', 'George', 'Frank']
names = sorted(A)
print(names)
n = len(names) - 1

low = 0
high = n
key = "James"

def binarysearch(a, l, h, k):

    if h < l:
        return l - 1
    mid = l + (h - l // 2)
    if k == names[mid]:
        return mid
    elif key < names[mid]:
        return binarysearch(a, l, mid-1, k)
    else:
        return binarysearch(a, mid+1, h, k)

index = binarysearch(names, low, high, key)

print("The given Name ", key, "is a Place ", index)

Я знаю, как увеличить sys.setrecursionlimit(), который я пробовал, но он все еще убивает, потому что он превысил предел ОЗУ, I have use bisect code of python and it works fine, но, поскольку я новичок в python, я хочу впитать углубленную концепцию алгоритма, а чем встроенные функции, если кто-то может помочь мне исправить этот код, я буду признателен, спасибо

Ответы [ 3 ]

0 голосов
/ 05 июля 2018

Вам не нужна рекурсия вообще. Вы можете сделать бинарный поиск итеративным способом. Однако даже с рекурсией вы не должны достигать максимальной глубины рекурсии с таким массивом. Причина, по которой вы нажимаете эту кнопку, заключается в том, что вы неправильно выполняете бинарный поиск. 

mid = l + (h - l // 2)

Это явно неправильно, поскольку l // 2 будет оцениваться первым. То, что вы хотите: 

mid = l + (h - l) // 2

Кроме того, я не получаю рациональное возвращение l - 1, когда h < l. Обычно вы должны возвращать -1, чтобы указать, что ключ не найден. l - 1 на каком-то рекурсивном шаге может предоставить действительный индекс для начального вызова.

И, наконец, если список не отсортирован, то нет смысла сначала сортировать его, а затем выполнять бинарный поиск, если только вы не выполняете много операций поиска по одному и тому же массиву, поскольку сортировка займет больше времени, чем простой линейный поиск.

0 голосов
/ 05 июля 2018

Если массив строк не будет изменяться в течение длительного времени или если он не будет изменяться очень часто, и поиск будет использоваться очень часто, тогда вы можете использовать структуру данных Trie, которая улучшит ваши временная сложность по стоимости космической сложности. Где худшее время сложность будет O(length of the longest string in that array)

0 голосов
/ 05 июля 2018

Это не огромный список, просто используйте list.index. 

x = [random.random() for _ in range(258000)] + [0.99]
%timeit x.index(0.99)
# 7.97 ms ± 703 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

Пример 

a = ['John', 'William', 'James', 'Charles', 'George', 'Frank']
a.index('James')  # --> 2
...