Chapter 15: Поиск

Поиск - это важная и часто используемая операция, постоянно выполняемая компьютерами. Поиск используется каждый раз, когда пользователь нажмиает ctrl-f, использует ввод в поисковом поле для быстрого поиска элемента или когда интернет-сервер берёт информацию о клиенте для отображения ориентированной на пользователя страницы с его заказом.

Есть много способов поиска данных. Google владеет целой мульти-миллиардной компанией только для этих целей. Эта глава описывает два простых метода для поиска, линейный и бинарный поиски.

15.1 Считывание из файла

До обсуждения того, как искать, важно знать, как считывать данные из файла. Это поможет программе с лёгкостью искать большие объёмы данных.

Предположим, что нам нужно создать программу, которой нужно будет быстро найти имя суперзлодея. Начнём с того, что нашей программе нужна база данных суперзлодеев. Чтобы скачать этот набор данных, щёлкните правой кнопкой мыше по нижеприведённой ссылке:
Суперзлодеи
и скачайте файл example_sorted_names.txt. Это случайные имена, сгенерированные на сайте nine.frenchboys.net, который, к сожалению, на момент написания этой статьи, больше не работает.

Запомните директорию, в которой вы сохранили этот файл.

В той же самой директории, где хранится список имён, создайте, сохраните и запустите следующую программу:

file = open("example_sorted_names.txt")

for line in file:
    print(line)

В коде появилась новая команда. У Python есть встроенная функция open. Потому что это встроенная функция, не нужно использовать import. Полное описание это функции можно найти в документации Python, здесь, но на данный момент документация к этой команды настолько технична, что читать её может не быть смысла.

У вышеприведённой программы есть две проблемы, но она даёт простой пример считывания файла. Первая строка открывает файл и готовит его к чтению. Имя файла ставится между кавычек. Новая переменная file - объект, представляющий считываемый файл. Третья строка показывает, как нормальный цикл for может быть использован для прочтения файла, строка за строкой. Представьте, что file - это список строк, а новая переменная line будет указывать на каждую из этих строк вместе с прохождением программы через цикл.

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

Второй проблемой является то, что файл открывается, но не закрывается. Эта проблема не так очевидна как проблема с двумя переносами строки, но она также является очень важной. Операционная система Windows может открыть ограниченное количество файлов за раз. Также, только одна программа может обращаться к файлу в данный момент времени. Так что оставить файл открытым будет ограничивать возможности других программ для работы с этим файлом. Нужно закрывать файл для того, чтобы дать Windows знать, что программа больше не работает с файлом. В данном случае это не так важно, потому что когда программа закончила своё выполнение, Windows автоматически закроет оставшиеся незакрытыми файлы. Но, так как это является плохим тоном, нужно обновить код программы.

file = open("example_sorted_names.txt")

for line in file:
    line=line.strip()
    print(line)

file.close()	

Вышеприведённый код будет лучше работать. В нём было сделано два улучшения. На четвёртой строке метод strip, встроенный в каждую строку, удалит все пробелы и переносы строки, находящиеся в самом начале и конце. Метод не изменяет оригинальную строку, вместо этого он создаёт новую. Следующая строка кода работать не будет:

line.strip()

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

Второе дополнение будет на строке 7. Это закрывает файл так, чтобы операционной системе больше не пришлось "подчищать" за программой, закрывая открытые файлы после завершения работы программы.

15.2 Считывание в массив

Полезным было бы считать содержимое файла в массив так, чтобы программа смогла бы проводить обработку позже. Это может быть легко достигнуть в python с помощью следующего кода:

# Считать файл с диска и положить его в массив
file = open("example_sorted_names.txt")

name_list = []
for line in file:
    line=line.strip()
    name_list.append(line)

file.close()	

Это сочетает в себе новый формат считывания файла, а также выученный нами ранее способ создания пустого массива с последующим добавлением в него данных. Для того, чтобы убедиться, что файл был правильно считан в массив, программист может вывести длинну массива:

print( "There were",len(name_list),"names in the file.")

Или программист может вывести всё содержимое массива на экран:

for line in name_list:
    print(name)

15.3 Линейный поиск

Если у программы есть набор данных в массиве, как она может найти нужный элемент? Это можно сделать одним или двумя способами. Первый способ - использовать линейный поиск. Он начинает с первого элемента и продолжает сравнивать, пока не найдёт желаемый элемент или пока не пройдёт весь список элементов.

# Линейный поиск
i=0
while i < len(name_list) and name_list[i] != "Morgiana the Shrew":
    i += 1
	
if i == len(name_list):
	print( "Имя не было в списке." )
else:
	print( "Имя находится в ячейке",i)

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

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

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

Четвёртая строка просто двигается к следующему элементу в случае, если условия для продолжения поиска выполняются на третьей строке.

В конце цикла, программа проверяет, был ли достигнут конец списка на шестрой строке. Помните, список из n элементов нумеруется от 0 до n-1. Поэтому, если i равняется n (длине списка), то мы достигли самого конца.

15.3.1 Проверка пройденного

Ответьте на следующие вопросы, учитывая, что программа использует линейный поиск:

1. Если в списке n элементов, в лучшем случае, сколько элементов должно быть проверено, чтобы удостовериться, что мы нашли нужный элемент?
2. В списке из n элементов, в худшем случае, сколько элементов должно быть проверено, чтобы удостовериться, что мы нашли нужный элемент?
3. Если в списке n элементов, сколько элементов понадобится проверить для определения того, что нужный нам элемент не находится в списке?
4. Если в списке n элементов, каким будет среднее количество проверенных элементов до момента, пока компьютер не найдёт нужный нам элемент?
5. Возьмите пример с линейным поиском и разместите его в функции. Как параметры берите список, а так же элемент, который нужно найти. Возвращайте позицию элемента или -1, если тот не был найден.

15.4 Бинарный поиск

Более быстрым способом поиска в списке будет бинарный поиск. Процесс бинарного поиска может быть описан с помощью классической игры “угадай число от 1 до 100”. Для облегчения понимания процесса, изменим игру на “угадай число между 1 и 128” Границы включены, значит как 1, так и 128, могут быть возможными ответами.

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

Угадайте число от 1 до 128: 1
Слишком маленькое.
Угадайте число от 1 до 128: 2
Слишком маленькое.
Угадайте число от 1 до 128: 3
Слишком маленькое.
....
Угадайте число от 1 до 128: 93
Слишком маленькое.
Угадайте число от 1 до 128: 94
Верно!

Большинство людей будут пользоваться бинарным поиском для поиска числа. Вот пример игры с использованием бинарного поиска:

Угадайте число от 1 до 128: 64
Слишком маленькое.
Угадайте число от 1 до 128: 96
Слишком большое.
Угадайте число от 1 до 128: 80
Слишком маленькое.
Угадайте число от 1 до 128: 88
Слишком маленькое.
Угадайте число от 1 до 128: 92
Слишком маленькое.
Угадайте число от 1 до 128: 94
Верно!

С каждым новой попыткой, угадывающий может исключить половину возможных вариантов ответа, получая “большое” или “маленькое” как результат своей догадки.

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

Нижная граница 1, верхняя граница 128, средняя точка $(1+128)/2 = 64.5$.

Угадайте число от 1 до 128: 64
Слишком маленькое.

Нижняя граница 65, верхняя граница 128, средняя точка $(65+128)/2 = 96.5$.

Угадайте число от 1 до 128: 96
Слишком большое.

Нижняя граница 65, верхняя граница 95, средняя точка $(65+95)/2 = 80$.

Угадайте число от 1 до 128: 80
Слишком маленькое.

Нижняя граница 81, верхняя граница 95, средняя точка $(81+95)/2 = 88$.

Угадайте число от 1 до 128: 88
Слишком маленькое.

Нижняя граница 89, верхняя граница 95, средняя точка $(89+95)/2 = 92$.

Угадайте число от 1 до 128: 92
Слишком маленькое.

Нижняя граница 93, верхняя граница 95, средняя точка $(93+95)/2 = 94$.

Угадайте число от 1 до 128: 94
Верно!

Бинарный поиск требует меньшего количества попыток. В худшем случае, он угадает число между 1 и 128 за 7 попыток. Ещё одна попытка увеличит лимит до 256. 9 попыток позволят угадать любое число между 1 и 512. Всего лишь за 32 попытки, человек сможет угадать число между 1 и 4.2 миллиардами.

Код бинарного поиска более сложный, чем код линейного поиска:

# Бинарный поиск
desired_element = "Morgiana the Shrew";
lower_bound = 0
upper_bound = len(name_list)-1
found = False
while lower_bound < upper_bound and found == False:
    middle_pos = (int) ((lower_bound+upper_bound) / 2)
    if name_list[middle_pos] < desired_element:
	    lower_bound = middle_pos+1
    elif name_list[middle_pos] > desired_element:
	    upper_bound = middle_pos
    else:
        found = True

if found:
    print( "Имя находится в ячейке",middle_pos)
else:
    print( "Имя не было найдено в списке." )

Так как списки начинаются с нулевого элемента, третья строка приравнивает нижнюю границу к нулю. Четвёртая строка задаёт верхнюю границу равно длине списка минус один. Так что список из 100 элементов будет иметь нижнюю границу 0 и верхнюю границу 99.

Булевая переменная на строке 5 будет использована для оповещения цикла о том, что элемент был найден.

Строка 6 проверяет, был ли найден элемент или закончились ли у нас элементы для проверки. Если все элементы закончились, то нижняя граница будет равна верхней границе.

Строка 7 находит среднюю позицию. Возможно, что средняя позиция будет чем-то вроде 64.5. Нельзя проверить 64.5. (Хотя J.K. Rowling была достаточно остроумна для придумывания Платформы $9\frac{3}{4}$.) Так что нужно конвертировать результат в целое число с помощью (int).

Альтернативным способом достигнуть этого будет использование оператора //. Он схож с оператором /, однако он возвращает только целочисленные результаты. Например 11 // 2 будет равен 5, а не 5.5.

    middle_pos = (lower_bound+upper_bound) // 2

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

15.4.1 Проверка пройденного

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

1. Если в списке n элементов, в лучшем случае, сколько элементов нужно будет проверить компьютеру для нахождения нужного элемента?
2. Если в списке n элементов, в худшем случае, сколько элементов нужно будет проверить компьютеру для нахождения нужного элемента?
3. Если в списке n элементов, сколько элементов нужно будет проверить, чтобы определить, что нужный нам элемент не находится в списке?
4. Если в списке n элементов, сколько элементов в среднем потребуется проверить компьютеру для нахождения нужного элемента?
5. Возьмите пример кода с бинарным поиском и поместите его в функцию. Как аргументы принимайте список элементов, а также элемент, который требуется найти. Возвращайте позицию элемента или -1, если он не был найден.

You are not logged in. Log in here and track your progress.