Словари

19.1. Словарь как набор счетчиков

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

Есть несколько способов, чтобы это сделать:

Каждый из этих вариантов выполняет одинаковые вычисления, но каждый из них реализует разные способы вычислений.

Реализация (implementation) - это способ выполнения вычислений, некоторые реализации лучше остальных. Например, преимущество реализации через словарь в том, что мы не должны знать заранее, какие буквы появятся в строке, у нас есть только свободное место для букв, которые появятся.

Код может выглядеть следующим образом:

def histogram(s):
       d = dict()
       for c in s:
           if c not in d:
                 d[c] = 1
           else:
                 d[c] = d[c] + 1
       return d

Имя функции - гистограмма, т.к. это статистический термин для множества счетчиков (или частот).

Первая строка функции создает пустой словарь. Цикл for обходит строку. Всякий раз в цикле, если символ с не встречается в словаре, мы создаем новую запись с ключом с и присваиваем начальное значение 1 (т.к. мы встретили эту букву один раз). Если с уже есть в словаре, то мы инкрементируем d[c].

Так это работает:

>>> h = histogram('brontosaurus')
>>> print h
{'a': 1, 'b': 1, 'o': 2, 'n': 1, 's': 2, 'r': 2, 'u': 2, 't': 1}

19.2. Словари и файлы

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

http://shakespeare.mit.edu/Tragedy/romeoandjuliet/romeo_juliet.2.2.html

В первом множестве примеров мы будем использовать сокращенную и упрощенную версию текста без знаков препинания. Позже мы будем работать с текстом сцены, включающим знаки препинания.

But soft what light through yonder window breaks
It is the east and Juliet is the sun
Arise fair sun and kill the envious moon
Who is already sick and pale with grief

Мы напишем программу на Python, которая читает строки файла, разбивает каждую строку на список слов, затем проходит в цикле через каждое слово в строке и с использованием словаря подсчитывает слова.

Вы увидите, что получится два цикла for. Внешний цикл для строк файла и внутренний цикл для каждого слова в отдельной строке. Это пример шаблона, который называется вложенные циклы (nested loops), т.к. один из циклов внешний (outer), а второй - внутренний (inner).

Комбинация из двух вложенных циклов гарантирует, что мы будем считать каждое слово в каждой строке входного файла.

fname = raw_input('Enter the file name: ')
try:
       fhand = open(fname)
except:
       print 'File cannot be opened:', fname
       exit()
       
counts = dict()
for line in fhand:
       words = line.split()
       for word in words:
           if word not in counts:
                 counts[word] = 1
           else:
                 counts[word] += 1
print counts

Когда мы запускаем программу, мы видим сырой дамп (raw dump) всех счетчиков в неотсортированном хэш порядке (файл romeo.txt file доступен по адресу: http://pycode.ru/files/python/romeo.txt))

Enter the file name: romeo.txt
{'and': 3, 'envious': 1, 'already': 1, 'fair': 1, 'is': 3, 
'through': 1, 'pale': 1, 

'yonder': 1, 'what': 1, 'sun': 2, 'Who': 1, 'But': 1, 'moon': 1, 
'window': 1, 

'sick': 1, 'east': 1, 'breaks': 1, 'grief': 1, 'with': 1, 
'light': 1, 'It': 1, 

'Arise': 1, 'kill': 1, 'the': 3, 'soft': 1, 'Juliet': 1}

Немного неудобно просматривать словарь в поисках наиболее употребительных слов и их количества, поэтому нам нужно добавить еще несколько строк кода, чтобы получить более полезный результат на выходе.

19.3. Циклы и словари

Если вы используете словарь как последовательность (sequence) в операторе for, происходит обход ключей словаря. Например, print_hist выводит на экран каждый ключ и соответствующее ему значение:

def print_hist(h):
       for c in h:
           print c, h[c]

Результат имеет следующий вид:

>>> h = histogram('parrot')
>>> print_hist h
a 1
p 1
r 2
t 1
o 1

Снова ключи не имеют порядка.

Если вы хотите вывести на экран ключи в алфавитном порядке, сначала составьте список ключей в словаре с помощью метода словаря keys, затем отсортируйте этот список и в цикле, просматривая каждый ключ, выводите на экран пару ключ/значение, как показано далее:

def print_sorted_hist(h):
       lst = h.keys()
       lst.sort()
       for c in lst:
             print c, h[c]

Результат будет следующий:

>>> h = histogram('parrot')
>>> print_sorted_hist(h)
a 1
o 1
p 1
r 2
t 1

Теперь ключи отсортированы в алфавитном порядке.

9.6. Словарь

dictionary: A mapping from a set of keys to their corresponding values.

hashtable: The algorithm used to implement Python dictionaries.

hash function: A function used by a hashtable to compute the location for a key.

histogram: A set of counters.

implementation: A way of performing a computation.

item: Another name for a key-value pair.

key: An object that appears in a dictionary as the first part of a key-value pair.

key-value pair: The representation of the mapping from a key to a value.

lookup: A dictionary operation that takes a key and finds the corresponding value.

nested loops: When there is one or more loops "inside" of another loop. The inner loop runs to completion each time the outer loop runs once.

value: An object that appears in a dictionary as the second part of a key-value pair.

This is more specific than our previous use of the word "value."