Это десятая часть из 14 серий нетрадиционного введения в Python, написанного с целью научиться эффективно использовать вычислительные методы. Ссылки на все части смотрите в первой статье.
Некоторые простые алгоритмы и структуры данных
Большинство из нас никогда не изобретает новый алгоритм. Вместо этого мы учимся сводить самые сложные аспекты проблем, с которыми мы сталкиваемся, к ранее решенным проблемам. Точнее, мы
- Развивать понимание присущей сложности проблемы, с которой мы сталкиваемся,
- Подумайте, как разбить эту проблему на подзадачи и
- Свяжите эти подзадачи с другими проблемами, для которых уже существуют эффективные алгоритмы.
Алгоритмы поиска
Алгоритм поиска – это метод поиска элемента или группы элементов с определенными свойствами в наборе элементов. Мы называем набор элементов областью поиска.
Линейный поиск и использование косвенного доступа к элементам
Python использует следующий алгоритм, чтобы определить, находится ли элемент в списке:
def search(L, e):
for i in range(len(L)):
if L[i] == e:
return True
return False
Если элемента e нет в списке, алгоритм выполнит O(len(L)) тестов, т. е. сложность в лучшем случае линейна по длине L.
Двоичный поиск и предположения об использовании
предположим, что мы знаем что-то о порядке хранения элементов, например, предположим, что мы знаем, что у нас есть список целых чисел, хранящихся в порядке возрастания. Мы могли бы изменить реализацию так, чтобы поиск останавливался, когда он достигает числа, превышающего искомое число
Здесь мы полагаемся на предположение, что список упорядочен.
Идея проста:
- Выберите индекс i, который делит список L примерно пополам.
- Спросите, если L[i] == e.
- Если нет, спросите, больше или меньше L[i] e.
- В зависимости от ответа найдите e в левой или правой половине буквы L.
сложность поиска O(log(len(L))).
Алгоритмы сортировки
Начнем с простого, но неэффективного алгоритма сортировка выбором.
Сортировка выбором работает, поддерживая инвариант цикла, который при разделении списка на префикс (L[0:i]) и суффикс (L[i+1:len(L)]) , префикс отсортирован, и ни один элемент в префиксе не превышает наименьший элемент в суффиксе.
Сложность всей функции составляет O(len(L)2 ). т. е. квадратичен по длине L.
Сортировка слиянием
К счастью, с помощью алгоритма «разделяй и властвуй» мы можем работать намного лучше, чем квадратичное время. Основная идея состоит в том, чтобы комбинировать решения более простых экземпляров исходной задачи. В целом алгоритм «разделяй и властвуй» характеризуется
- Пороговый размер входных данных, ниже которого задача не разбивается,
- Размер и количество подэкземпляров, на которые разбивается экземпляр, и
- Алгоритм, используемый для объединения подрешений.
Порог иногда называют рекурсивной базой.
Сортировка слиянием — это прототип алгоритма "разделяй и властвуй". Он был изобретен в 1945 году Джоном фон Нейманом и до сих пор широко используется. Как и многие алгоритмы «разделяй и властвуй», его проще всего описать рекурсивно.
- Если список имеет длину 0 или 1, он уже отсортирован.
- Если в списке более одного элемента, разделите список на два списка и используйте
- сортировка слиянием для сортировки каждого из них.
- Объедините результаты.
def merge(left,right,compare): '''Assume left and right are sorted lists and compare defines an ordering on the elements. Return a new sorted (by compare) list containing the same elements as (left + right) would contain.''' result = [] i,j = 0,0 while i<len(left) and j<len(right): if compare(left[i], right[j]): result.append(left[i]) i+=1 else: result.append(right[j]) j+=1 while(i<len(left)): result.append(left[i]) i+=1 while(j<len(right)): result.append(right[j]) j+=1 return result import operator def mergeSort(L,compare = operator.lt): '''Assumes L is a list, compare defines an ordering on elements of L Returns a new sorted list containing the same elements as L''' if len(L) < 2: return L[:] else: middle = len(L)//2 left = mergeSort(L[:middle],compare) right = mergeSort(L[middle:],compare) return merge(left, right,compare)
Сортировка в Python.
Алгоритм сортировки, используемый в большинстве реализаций Python, называется timsort. Основная идея состоит в том, чтобы воспользоваться тем фактом, что во многих наборах данных данные уже частично отсортированы. Производительность Timsort в худшем случае такая же, как и у сортировки слиянием, но в среднем она работает значительно лучше.
Хеш-таблицы
Основная идея хэш-таблицы проста. Мы преобразуем ключ в целое число, а затем используем это целое число для индексации в список, что можно сделать за постоянное время. В принципе, значения любого неизменяемого типа можно легко преобразовать в целое число. В конце концов, мы знаем, что внутреннее представление каждого объекта представляет собой последовательность битов, а любую последовательность битов можно рассматривать как представляющую целое число.
Хэш-функция сопоставляет большое пространство входных данных (например, все натуральные числа) с меньшим пространством выходных данных (например, натуральные числа от 0 до 5000). Хэш-функции можно использовать для преобразования большого пространства ключей в меньшее пространство целочисленных индексов.
Поскольку пространство возможных выходных данных меньше пространства возможных входных данных, хеш-функция представляет собой отображение «многие к одному», т. е. несколько различных входных данных могут быть сопоставлены с одним и тем же выходным сигналом. Когда два входа сопоставляются с одним и тем же выходом, это называется коллизией — тема, к которой мы вскоре вернемся. Хорошая хеш-функция обеспечивает равномерное распределение, т. е. все выходные данные в диапазоне равновероятны, что сводит к минимуму вероятность коллизий.
Все кредиты принадлежат профессору Джону Гуттагу, и все ссылки связаны с его вкладом в эту область.
Также спасибо моему другу, который считает, что «успех для меня заключается в том, что я оказал достаточное влияние, чтобы мир стал лучше», что мотивирует меня начать с нуля, чтобы в какой-то момент изменить ситуацию.
