Алгоритмы поиска

Мы постоянно что-то ищем с помощью компьютера — номера телефонов, свободные номера в гостиницах, товары в интернет-магазинах, квартиры в аренду. За каждым из этих поисков скрываются разные алгоритмы. Среди них — поиск подстроки, поиск по ключевым словам, префиксный поиск. Мы познакомимся с двумя алгоритмами: методом перебора и бинарным поиском

Метод перебора

• Он же линейный (последовательный) поиск — проверка всех значений в списке с начала и до нужного атрибута. Выделяют два алгоритма перебора — поиск по списку и поиск по ключу

Поиск по списку: если нам нужно найти слово в списке слов — мы последовательно будем проверять все слова, пока не найдём нужное

Поиск по ключу:

• Допустим у нас есть список городов с датами основания. Мы знаем год основания города и хотим найти его название. Так, мы знаем один атрибут города — год основания, а хотим найти другой атрибут — название города. Известный нам атрибут называется ключом, по которому мы проводим поиск

Список городов с датами основания

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

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

some_cities = ["Ереван", "Киев", "Минск", "Рига", "Вильнюс", "Астана", "Москва", "Баку", "Душанбе", "Хельсинки", "Ашхабад", "Ташкент"]

def is_city(some_cities, candidate):
    for i in range(len(some_cities)):
        if some_cities[i] == candidate:
            return True
    return False

• Представим, что по такому методу работает проверка логина и пароля в Facebook. Массив с логинами-паролями всех пользователей содержит около трех миллиардов элементов и даже на самых быстрых серверах этот процесс занял бы несколько минут

Как ускорить алгоритм перебора

Самый простой способ — упорядочить данные, т.е. отсортировать их. Представьте, если бы в телефонном справочнике имена и фамилии не были бы отсортированы, сколько бы занял поиск номера. А если они отсортированы по алфавиту, мы сразу можем "отсечь" часть списка, в котором искомой фамилии точно нет.

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

Это метод поиска, при котором алгоритм ищет элементы в ограниченной области поиска, причем с каждым шагом область поиска делится на две части.

Механизм работы:

• Бинарный поиск начинается со среднего элемента и на первом шаге идёт по всему массиву

• На каждом шаге область поиска делится пополам, при этом границы поиска задаются первым и последним элементом

• Алгоритм завершается, когда область поиска сужается до одного элемента

Необходимое условие для применения бинарного поиска — массив должен быть отсортирован.

Отсортируем массив городов по алфавиту:

some_cities = ['Астана',
               'Ашхабад',
               'Баку',
               'Вильнюс',
               'Душанбе',
               'Ереван',
               'Киев',
               'Минск',
               'Москва',
               'Рига',
               'Ташкент',
               'Хельсинки']

• Изначально область поиска — весь массив.

• Делим его пополам, в середине элемент "Киев", сравниваем его с искомым — таким образом сужаем область поиска до половины массива. И далее делим пополам уже оставшуюся область поиска.

Практика:

• Составьте псевдокод для программы поиска города в списке городов из примера выше.

Посмотрим на реализацию в коде:

some_cities = ['Астана', 'Ашхабад', 'Баку', 'Вильнюс', 'Душанбе', 'Ереван', 'Киев', 'Минск', 'Москва', 'Рига', 'Ташкент', 'Хельсинки']

def is_some_city(some_cities, candidate):
    # индекс первого элемента области поиска
    first = 0
    # индекс последнего элемента области поиска
    last = len(some_cities) - 1

    while (first <= last):
        # индекс среднего элемента области поиска
        middle = (first + last) // 2

        if candidate == some_cities[middle]:
            # если нашли слово-кандидат, поиск завершается удачно
            return True

        if candidate < some_cities[middle]:
            # если кандидат меньше, отбрасываем правую половину
            last = middle - 1
        else:
            # если кандидат больше, отбрасываем левую половину
            first = middle + 1

    return False

Недостатки бинарного поиска

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

• Бинарный поиск сложнее в реализации. Если у нас массив более 100 элементов имеет смысл воспользоваться бинарным поиском, если массив небольшой — достаточно метода перебора, он будет работать со сравнимой скоростью или даже быстрее

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

• Существуют данные, которые невозможно упорядочить (например, цвета или пары чисел — координаты: широта и долгота)

Преимущества бинарного поиска

Бинарный поиск быстрее линейного, но насколько? Как это измерить?

• Мы можем измерить время работы программ. Но это время сильно зависит от конкретной машины и условий (фоновые задачи и т.п.), а поэтому не является объективным.

• Оценим скорость теоретически — быстрее тот алгоритм, в котором совершается меньше операций. В обоих алгоритмах операции проходят в цикле и для объективности будем считать среднее количество циклов

Сравнение средней скорости алгоритмов поиска

Заключение

• Мы рассмотрели два алгоритма: метод перебора и бинарный поиск

• У метода перебора есть два варианта:

  • Простой перебор, чтобы проверить, есть ли элемент в списке

  • Поиск по ключу, если нужно найти элемент по одному атрибуту

• Бинарный поиск позволяет искать элементы в упорядоченном списке. На каждом шаге алгоритма область поиска делится на две части.

• Бинарный поиск гораздо быстрее обычного поиска, но при этом сложнее в реализации

Практика

• Поиск максимального элемента: Дан массив чисел. Найдите максимальный элемент в этом массиве, используя линейный поиск.

• Поиск первого вхождения элемента: Дан массив строк и ключевое слово. Найдите индекс первого вхождения ключевого слова в массиве, используя линейный поиск.

• Поиск элемента в отсортированном массиве: Дан отсортированный массив чисел и элемент этого массива. Найдите индекс элемента, используя бинарный поиск.

Вычислительная сложность

Как понять, насколько быстро работает алгоритм?

• Попробуем рассчитать время выполнения алгоритма. Допустим, время выполнения одной операции составляет 1 мс. Одной операцией для поиска является одно прохождение по массиву. Для линейного поиска в массиве из 100 элементов время составит 100 мс (в худшем случае). Для бинарного поиска — 7 мс. Посчитайте, сколько времени понадобится для линейного и бинарного поиска в массиве из 1000 элементов

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

• Таким образом, для линейного поиска по массиву длиной N элементов нужно в худшем случае нужно произвести N операций. Для бинарного поиска — log N операций — степень числа 2, в которую нужно её возвести, чтобы получить N

• Для того, чтобы понимать, насколько быстро или медленно работают алгоритмы используют нотацию O ("О-большое"). С её использованием формулировка будет выглядеть так — скорость работы алгоритма линейного поиска составляет O(n), а скорость работы бинарного поиска составляет O(log n)

• О-большое позволяет сравнить количество операций — именно так принято сравнивать скорость работы алгоритмов. Чаще всего используют худший случай, т.е. максимальное возможное количество операций для алгоритма, но иногда учитывают и среднее время выполнения

• Типичные примеры О-большого:

  • O(log n), или логарифмическое время. Пример: бинарный поиск.

  • O(n), или линейное время. Пример: простой поиск.

  • O(n*log n). Пример: эффективные алгоритмы сортировки

  • O(n2). Пример: медленные алгоритмы сортировки

  • O(n!). Пример: очень медленные алгоритмы (задача о коммивояжёре)

Практика:

Приведите время выполнения "О-большое" для каждого из следующих сценариев:

• Известная фамилия, нужно найти номер в телефонной книге

• Известен номер, нужно найти фамилию в телефонной книге