2.4 Пользователи также довольно часто создают новые учетные записи на Facebook. Предположим, вы решили использовать массив для хранения списка пользователей. Какими недостатками обладает массив для выполнения вставки? Допустим, вы используете бинарный поиск для нахождения учетных данных. Что произойдет при добавлении новых пользователей в массив?
2.5 В действительности Facebook не использует ни массив, ни связанный список для хранения информации о пользователях. Рассмотрим гибридную структуру данных: массив связанных списков. Имеется массив из 26 элементов. Каждый элемент содержит ссылку на связанный список. Например, первый элемент массива указывает на связанный список всех имен пользователей, начинающихся на букву «A». Второй элемент указывает на связанный список всех имен пользователей, начинающихся на букву «B», и т.д.
Предположим, пользователь с именем «Adit B» регистрируется на Facebook и вы хотите добавить его в список. Вы обращаетесь к элементу 1 массива, находите связанный список элемента 1 и добавляете «Adit B» в конец списка. Теперь предположим, что зарегистрировать нужно пользователя «Zakhir H». Вы обращаетесь к элементу 26, который содержит связанный список всех имен, начинающихся с «Z», и проверяете, присутствует ли «Zakhir H» в этом списке.
Теперь сравните эту гибридную структуру данных с массивами и связанными списками. Будет ли она быстрее или медленнее каждой исходной структуры при поиске и вставке? Приводить «O-большое» не нужно, просто выберите одно из двух: быстрее или медленнее.
Сортировка выбором
А теперь объединим все, что вы узнали, во втором алгоритме: сортировке выбором. Чтобы освоить этот алгоритм, вы должны понимать, как работают массивы и списки и «O-большое». Допустим, у вас на компьютере записана музыка и для каждого исполнителя хранится счетчик воспроизведений.
Вы хотите отсортировать список по убыванию счетчика воспроизведений, чтобы самые любимые исполнители стояли на первых местах. Как это сделать?
Одно из возможных решений — пройти по списку и найти исполнителя с наибольшим количеством воспроизведений. Этот исполнитель добавляется в новый список.
Потом то же самое происходит со следующим по количеству воспроизведений исполнителем.
Продолжая действовать так, мы получаем отсортированный список.
А теперь попробуем оценить происходящее с точки зрения теории вычислений и посмотрим, сколько времени будут занимать операции. Напомним, что время O(n) означает, что вы по одному разу обращаетесь к каждому элементу списка. Например, при простом поиске по списку исполнителей каждый исполнитель будет проверен один раз.
Чтобы найти исполнителя с наибольшим значением счетчика воспроизведения, необходимо проверить каждый элемент в списке. Ка
к вы уже видели, это делается за время O(n). Итак, имеется операция, выполняемая за время O(n), и ее необходимо выполнить n раз:
Уменьшение количества проверяемых элементов
Возникает закономерный вопрос: при каждом выполнении операций количество элементов, которые нужно проверить, сокращается. Со временем все сведется к проверке всего одного элемента. Почему же время выполнения все равно оценивается как O(n2)? Это хороший вопрос, и ответ на него связан с ролью констант в «O-большом». Тема будет более подробно рассмотрена в главе 4, но я кратко объясню суть. Вы правы, вам действительно не нужно каждый раз проверять весь список из n элементов. Сначала проверяются n элементов, потом n – 1, n – 2 … 2, 1. В среднем проверяется список из ½ × n элементов. Его время выполнения составит O(n × ½ × n). Однако константы (такие как ½) в «O-большом» игнорируются (еще раз: за полным обсуждением обращайтесь к главе 4), поэтому мы просто используем O(n × n), или O(n2).
Все это требует времени O(n × n), или O(n2).
Алгоритмы сортировки очень полезны. Например, теперь вы можете отсортировать:
• имена в телефонной книге;
• даты путешествий;
• сообщения электронной почты (от новых к старым).
Алгоритм сортировки выбором легко объясняется, но медленно работает. Быстрая сортировка — эффективный алгоритм сортировки, который выполняется за время O(n log n). Но мы займемся этой темой в следующей главе!
Пример кода
Мы не будем приводить код сортировки музыкального списка, но написанный ниже код делает нечто очень похожее: он выполняет сортировку массива по возрастанию. Напишем функцию для поиска наименьшего элемента массива:
def findSmallest(arr):
smallest = arr[0] Для хранения наименьшего значения
smallest_index = 0 Для хранения индекса наименьшего значения
for i in range(1, len(arr)):
if arr[i] < smallest:
smallest = arr[i]
smallest_index = i
return smallest_index
Теперь на основе этой функции можно написать функцию сортировки выбором:
def selectionSort(arr): Сортирует массив
newArr = []
for i in range(len(arr)):
smallest = findSmallest(arr) Находит наименьший элемент в массиве и добавляет его в новый массив
newArr.append(arr.pop(smallest))
return newArr
print selectionSort([5, 3, 6, 2, 10])
Шпаргалка
• Память компьютера напоминает огромный шкаф с ящиками.
• Если вам потребуется сохранить набор элементов, воспользуйтесь массивом или списком.
• В массиве все элементы хранятся в памяти рядом друг с другом.
• В списке элементы распределяются в произвольных местах памяти, при этом в одном элементе хранится адрес следующего элемента.
• Массивы обеспечивают быстрое чтение.
• Списки обеспечивают быструю вставку и выполнение.
• Все элементы массива должны быть однотипными (только целые числа, только вещественные числа и т.д.).
3. Рекурсия
В этой главе
• Вы узнаете, что такое рекурсия — метод программирования, используемый во многих алгоритмах. Это важная концепция для понимания дальнейших глав книги.
• Вы научитесь разбивать задачи на базовый и рекурсивный случай. В стратегии «разделяй и властвуй» (глава 4) эта простая концепция используется для решения более сложных задач.
Эта глава мне самому очень нравится, потому что в ней рассматривается рекурсия — элегантный метод решения задач. Рекурсия относится к числу моих любимых тем, но вызывает у людей противоречивые чувства. Они либо обожают ее, либо ненавидят, либо ненавидят, пока не полюбят через пару-тройку лет. Лично я отношусь к третьему лагерю. Чтобы вам было проще освоить эту тему, я дам несколько советов:
• Глава содержит множество примеров кода. Самостоятельно выполните этот код и посмотрите, как он работает.
• Мы будем рассматривать рекурсивные функции. Хотя бы один раз возьмите бумагу и карандаш и разберите, как работает рекурсивная функция: «Так, я передаю функции factorial значение 5, потом возвращаю управление и передаю значение 4 функции factorial, которая…» и т.д. Такой разбор поможет вам понять, как работает рекурсивная функция.
В этой главе также приводится большое количество псевдокода. Псевдокод представляет собой высокоуровневое описание решаемой задачи. Он записывается в форме, похожей на программный код, но в большей степени напоминает естественный язык.
Рекурсия
Допустим, вы разбираете чулан своей бабушки и натыкаетесь на загадочный запертый чемодан.
Бабушка говорит, что ключ к чемодану, скорее всего, лежит в коробке.
В коробке лежат другие коробки, а в них лежат маленькие коробочки. Ключ находится где-то там. Какой алгоритм поиска ключа предложите вы? Подумайте над алгоритмом, прежде чем продолжить чтение.
Одно из решений может выглядеть так:
1. Сложить все коробки в кучу.
2. Взять коробку и открыть.
3. Если внутри лежит коробка, добавить ее в кучу для последующего поиска.
4. Если внутри лежит ключ, поиск закончен!
5. Повторить.
Есть и альтернативное решение.
1. Просмотреть содержимое коробки.
2. Если вы найдете коробку, вернуться к шагу 1.
3. Если вы найдете ключ, поиск закончен!
Какое решение кажется вам более простым? Первое решение можно построить на цикле while. Пока куча коробок не пуста, взять очередную коробку и проверить ее содержимое:
def look_for_key(main_box):
pile = main_box.make_a_pile_to_look_through()
while pile is not empty:
box = pile.grab_a_box()
for item in box:
if item.is_a_box():
pile.append(item)
elif item.is_a_key():
print "found the key!"
Второй способ основан на рекурсии. Рекурсией называется вызов функцией самой себя. Второе решение на псевдокоде может выглядеть так:
def look_for_key(b ox):
for item in box:
if item.is_a_box():
look_for_key(item) Рекурсия!
elif item.is_a_key():
print "found the key!"
Оба решения делают одно и то же, но второе решение кажется мне более понятным. Рекурсия применяется тогда, когда решение становится более понятным. Применение рекурсии не ускоряет работу программы: более того, решение с циклами иногда работает быстрее. Мне нравится одна цитата Ли Колдуэлла с сайта Stack Overlow: «Циклы могут ускорить работу программы. Рекурсия может ускорить работу программиста. Выбирайте, что важнее в вашей ситуации!»[2]
Рекурсия используется во многих нужных алгоритмах, поэтому важно понимать эту концепцию.