|
СЧЕТЧИК 60С- 40 ~ ПРОИЗВЕДЕНИЯ
RADIOHEAD
|
156
|
KISHORE KUMAR
|
141
|
THE SLACK KEYS
|
35
|
NEUTRAL MILK HOTEL
|
94
|
SECK
|
|
THE STROKES
|
61
|
UILCO
|
111
|
Вы хотите отсортировать список по убыванию счетчика воспроизведений, чтобы самые любимые исполнители стояли на первых местах. Как это сделать?
Одно из возможных решений — пройти по списку и найти исполнителя с наибольшим количеством воспроизведений. Этот исполнитель добавляется в новый список.
1
СЧЕТЧИК ВОСПРОИЗВЕДЕНИЙ
1СПИС0КЛ
|
ПРОИЗВЕДЕНИЙ
|
RADIOHEAP
|
156
|
KISHORE KUMAR
|
141
|
THE BLACK KEYS
|
35
|
NEUTRAL MILK HOTEL
|
94
|
BECK
|
2.8
|
THE STROKES
|
61
|
VJILCO
|
111
|
1. У RADIOHEAD
|
|
БОЛЬШЕ ВСЕГО
|
|
СЧЕТЧИК ВОС-
ВОСПРОИЗ В ЕЛЕН Ий-
RADIOHEAD
56
ДОБАВЛЯЕМ RADIOHEAD В НОВЫЙ СПИСОК
Потом то же самое происходит со следующим по количеству воспроизведений исполнителем.
KISHORE KUMAR
СЧЕТЧИК ВОСПРОИЗВЕДЕНИЙ
г список
141
THE BLACK KEYS
NEUTRAL MILK HOTEL
25
BECK
П
THE STROKES UlLCcT
МСПОЛННТЕ-Л
6i
TTT
l.
СЧЕТЧИК вос-
RADIOHEAD
|
156
|
KISHORE KUMAR
|
141
|
|
|
|
|
|
|
|
|
поэтому он о*; OIRCOR
|
|
Сортировка выбором 55
Продолжая действовать так, мы получаем отсортированный список.
'Л*
СЧЕТЧИК eoc- ПР0И36ЕДЕНИК
R.ADIOKEAD
156
KISHORE KUMAR
HI
VJlLCO
111
NEUTRAL MILK HOTEL
54
ЬЕСК
THE STROKES
61
THE bLACK KEYS
35
А теперь попробуем оценить происходящее с точки зрения теории вычислений и посмотрим, сколько времени будут занимать операции. Напомним, что время 0(п) означает, что вы по одному разу обращаетесь к каждому элементу списка. Например, при простом поиске по списку исполнителей каждый исполнитель будет проверен один раз.
RADIOHEAD Л
KISHORE KUMAR \
THE bLACK KEYS '
NEUTRAL MILK HOTEL
ЬЕСК
THE STROKES
?. V/ILCO J
n
элементов
Чтобы найти исполнителя с наибольшим значением счетчика воспроизведения, необходимо проверить каждый элемент в списке. Как вы уже видели, это делается за время 0(п). Итак, имеется операция, выполняемая за время 0(п), и ее необходимо выполнить п раз:
RADIOHEAD г. KISHORE KUMAR
THE SLACK KEYS
NEUTRAL MILK HOTEL
ЬЕСК
THE STROKES 1. WILCO
KISHORE KUMAR Z. THE SLACK KEYS
NEUTRAL MILK HOTEL
ЬЕСК
THE STROKES
1. THE STROKES
4
УМЕНЬШЕНИЕ КОЛИЧЕСТВА ПРОВЕРЯЕМЫХ ЭЛЕМЕНТОВ
Возникает закономерный вопрос: при каждом выполнении операций количество элементов, которые нужно проверить, сокращается. Со временем все сведется к проверке всего одного элемента. Почему же время выполнения все равно оценивается как 0(п2)? Это хороший вопрос, и ответ на него связан с ролью констант в «О-большом». Тема будет более подробно рассмотрена в главе 4, но я кратко объясню суть. Вы правы, вам действительно не нужно каждый раз проверять весь список из я элементов. Сначала проверяются п элементов, потом и - 1. я-2...2,1. В среднем проверяется список из Уг * я элементов. Его время выполнения составит 0(п х Уг > я). Однако константы (такие как Уг) в «О-большом» игнорируются (еще раз: за полным обсуждением обращайтесь к главе 4). поэтому мы просто используем 0(я X п), или Ош").
Все это требует времени 0(п х я), или 0(п2).
Алгоритмы сортировки очень полезны. Например, теперь вы можете отсортировать:
имена в телефонной книге;
даты путешествий;
сообщения электронной почты (от новых к старым).
Алгоритм сортировки выбором легко объясняется, но медленно работает. Быстрая сортировка — эффективный алгоритм сортировки, который выполняется за время 0(п log п). Но мы займемся этой темой в следующей главе!
Пример кода
Мы не будем приводить код сортировки музыкального списка, но написанный ниже код делает нечто очень похожее: он выполняет сортировку массива по возрастанию. Напишем функцию для поиска наименьшего элемента массива:
def find Smallest(a г г):
smallest = агг[0] < Для хранения наименьшего значения
smallest_index = 0 < Для хранения индекса наименьшего значения
for i in range(l, len(arr)): if arr[i] < smallest: smallest = arr[i] smallestindex = i return smallest index
Теперь на основе этой функции можно написать функцию сортировки выбором:
def selectionSort(arr): < Сортирует массив
newArr = []
for i in range(len(arr)):
smallest = indSmallest(arr) -< Находит наименьший элемент в массиве
newArr. append(arr.pop( smallest)) и добавляет его в новый массив
return newArr
print selectionSort([Б, 3, 6, 2, 10])
Шпаргалка
Память компьютера напоминает огромный шкаф с ящиками.
Если вам потребуется сохранить набор элементов, воспользуйтесь массивом или списком.
В массиве все элементы хранятся в памяти рядом друг с другом.
В списке элементы распределяются в произвольных местах памяти, при этом в одном элементе хранится адрес следующего элемента.
Массивы обеспечивают быстрое чтение.
Списки обеспечивают быструю вставку и выполнение.
Все элементы массива должны быть однотипными (только целые числа, только вещественные числа и т. д.).
Рекурсия
В этой главе
✓ Вы узнаете, что такое рекурсия — метод программирования, используемый во многих алгоритмах. Это важная концепция для понимания дальнейших глав книги.
v Вы научитесь разбивать задачи на базовый и рекурсивный случай. В стратегии «разделяй и властвуй» (глава 4) эта простая концепция используется для решения более сложных задач.
Эта глава мне самому очень нравится, потому что в ней рассматривается рекурсия — элегантный метод решения задач. Рекурсия относится к числу моих любимых тем, но вызывает у людей противоречивые чувства. Они либо обожают ее, либо ненавидят, либо ненавидят, пока не полюбят через пару-тройку лет. Лично я отношусь к третьему лагерю. Чтобы вам было проще освоить эту тему, я дам несколько советов:
Глава содержит множество примеров кода. Самостоятельно выполните этот код и посмотрите, как он работает.
Мы будем рассматривать рекурсивные функции. Хотя бы один раз возьмите бумагу и карандаш и разберите, как работает рекурсивная функция: «Так, я передаю функции factorial значение 5, потом возвращаю
управление и передаю значение 4 функции factorial, которая...» и т. д. Такой разбор поможет вам понять, как работает рекурсивная функция.
В этой главе также приводится большое количество псевдокода. Псевдокод представляет собой высокоуровневое описание решаемой задачи. Он записывается в форме, похожей на программный код, но в большей степени напоминает естественный язык.
Рекурсия
Допустим, вы разбираете чулан своей бабушки и натыкаетесь на загадочный запертый чемодан.
Бабушка говорит, что ключ к чемодану, скорее всего, лежит в коробке.
БОЛЬШАЯ
КОРОБКА
В коробке лежат другие коробки, а в них лежат маленькие коробочки. Ключ находится где-то там. Какой алгоритм поиска ключа предложите вы? Подумайте над алгоритмом, прежде чем продолжить чтение.
О
СЛОЖИТЬ
6СЕ КОРОБКИ
6 КУЧУ
дно из решений может выглядеть так:
П
Do'stlaringiz bilan baham: |
