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

count = 0

for char in fruit: if char == 'a': count += 1

print count

Первым шагом будет замена fruit на list и char на num. Это не изменит программу, просто приблизит ее к контексту нашей задачи.

Следующим шагом будет изменение критерия проверки. Нас не интересуют буквы. Нам надо видеть, попал ли num в заданный диапазон между low и high.

Параметрами функции являются список значений и границы диапазона low и high. def inBucket(list, low, high):

count = 0

for num in list:

if low < num < high: count += 1

return count

Как видите, копируя и модифицируя существующую программу можно быстро реализовать нужную функциональность и не тратить много времени на разработку алгоритма. Такие заготовки называют паттернами (от англ. pattern – пример, образец). Если вам придется решать задачу, которую вы уже решали, просто используйте ранее полученное решение.

§9.7. Анализ выборки

Теперь применим полученную функцию для анализа количества случайных величин попадающий в каждую из «ячеек» диапазона. По мере роста количества «ячеек» использование inBucket() становится немного громоздким. С двумя ячейками еще

неплохо:

bucket1 = inBucket(a, 0.0, 0.5) bucket2 = inBucket(a, 0.5, 1)

Но с четырьмя запись становится неуклюжей:

97

bucket1 = inBucket(a, 0.0, 0.25) bucket2 = inBucket(a, 0.25, 0.5) bucket3 = inBucket(a, 0.5, 0.75) bucket4 = inBucket(a, 0.75, 1.0)

Встают две задачи. Первая заключается в том, что нам надо создавать новые имена переменных для каждого нового результата, при этом хотелось бы иметь возможность подбирать количество «ячеек» выборок различного размера. Вторая заключается в том, что приходится вычислять диапазон для каждой ячейки.

Сначала решим вторую проблему. Если количество ячеек numBuckets, то ширина каждой ячейки равна 1.0/numBuckets.

Воспользуемся циклом для вычисления диапазона каждой ячейки. Переменная цикла i меняется от 0 до numBucket - 1:

bucketWidth = 1.0/numBuckets

high = low

for i in range(numBuckets): print i

low = high

high += bucketWidth print low, "to", high

Для вычисления нижней границы каждой ячейки умножим переменную цикла на ширину ячейки. Верхняя граница находится на расстоянии bucketWidth.

С numBuckets = 8 вывод следующий:

0.0 to 0.125

0.125 to 0.25

0.25 to 0.375

0.375 to 0.5

0.5 to 0.625

0.625 to 0.75

0.75 to 0.875

0.875 to 1.0

Легко убедиться, что каждая ячейка имеет одинаковую ширину, что они не перекрывают друг друга и покрывают весь диапазон от 0.0 до 1.0.

Теперь вернемся к первой задаче. Требуется способ хранения восьми целых чисел с использованием переменной цикла для выбора только одного числа. Наверняка вам уже пришла в голову идея: «Список!»

Необходимо создавать список ячеек вне цикла, поскольку сделать это нужно только один раз. Внутри цикла мы будем вызывать функцию inBucket() и обновлять значение i-го элемента:

98

Со списком из 1000 значений эта программа будет выдавать примерно такой список:

[138, 124, 128, 118, 130, 117, 114, 131]

Все эти значения близки к 1000 / 8 = 125. таким образом можно сделать вывод, что все значения из используемого диапазона более или менее равновероятны.

Упражнение. Модифицируйте программу так, чтобы она сохраняла в списке пары значений (кортежи с двумя элементами): количество элементов, попавших в диапазон, и отклонение суммы от ожидаемой (len(list) / numBuckets).

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

§9.8. Более эффективное решение

Хотя эта программа работает, она не такая эффективная, какой могла бы быть. При каждом вызове inBucket() она просматривает весь список. По мере роста количества ячеек

и размера списка, возрастает количество проходов, а, следовательно, и затраты на вычисления.

Попробуем найти другое решение, для чего нам нужно устранить главное «тонкое место» в нашем алгоритме: повторяющие проходы по элементам списка для каждой «ячейки». Как избавиться от функции inBucket()?

Поскольку bucketWidth = 1.0 / numBuckets, деление на bucketWidth

равнозначно умножению на numBuckets. Если умножить число из диапазона от 0.0 до 1.0 на numBuckets, то получится число из диапазона от 0.0 до numBuckets. Если это число округлить в меньшую сторону, то получится как раз искомая величина – номер ячейки:

numBuckets = 8

buckets = [0] * numBuckets for i in list:

index = int(i * numBuckets) buckets[index] = buckets[index] + 1

Для преобразования действительного числа к целому мы применили функцию int(),которая отбрасывает дробную часть.

99

Упражнение. Проверьте работоспособность этой программ. Может ли она выдать индекс за пределами диапазона (отрицательный или больше, чем len(buckets)-1)?

Объясните свой ответ.

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

Упражнение. Напишите функцию histogram(), которая принимает в качестве

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

100