Пост создан для рассмотрения небольшого примера возможностей языка python. Мы не станем углубляться в сложные темы языка, например, такие как объектно-ориентированное программирование и связанные с ним классы. Да, они являются мощным инструментом для создания сложных приложений, но нам этого пока не требуется.
Цель: создать англо-русский, русско-английский словарь с возможностью вносить в него новые, пользовательские значения. Первое, что приходи на ум — словари языка python.
Словарь в питоне — неупорядоченная последовательность пар ключ — значение. Что, собственно, и требовалось, верно?
Пример первый
Итак, первый файл должен содержать сам словарь с некоторыми значениями.
Создадим его. Назовём words.py
# words.py words=’word’: ‘мир’, ‘earth’:’земля’, ‘you’: ‘ты’, ‘I’:’я’, ‘We’:’мы’, ‘probably’:’вероятно’, ‘piece’:’кусок’, ‘tired’:’усталый’, ‘should’:’должен’, ‘be able’:’быть в состоянии’, ‘not enough’:’не хватает’, ‘enough’:’достаточно’, ‘should’:’должен’, ‘represent’:’представлять’, ‘sequence’:’последовательность’>
Теперь нужно как-то спросить у пользователя, перевод какого именно слова он хотел бы найти и вывести значение на экран. Кроме того, не стоит забывать, что наш словарь работает в двух направлениях: он должен не только переводить с английского на русский, но и наоборот!
Python с нуля | Словари в Python | Методы словарей, перебор словарей в Python
Создадим стартовый файл с функциями, запускающими в зависимости от предпочтений пользователя тот или иной вариант перевода.
# mydictionary.py #!/usr/bin/env python # -*- coding:utf-8 -*- from words import words def eng(): eng_words=dict([[v, k] for k,v in words.items()]) find_word=input(‘Enter word ‘ ») print(eng_words.get(find_word) or print(‘No such key’)) def rus(): key=input(‘Введите слово ‘ ») print (words.get(key) or ‘Искомое слово не найдено’) if __name__ == ‘__main__’: x=input(‘Найти перевод английского слова? ‘ ») if x == ‘y’: rus() elif x == ‘n’: eng() else: print(‘Увидимся позже’)
Отлично! Разберём построчно:
from words import words — импортируем из файла words.py сам словарь — words
Пишем две функции: eng и rus без параметров.
eng_words=dict([[v, k] for k,v in words.items()]) — это словарь «наоборот» для перевода русских слов на английские, теперь ключи стали значениями, а значения — ключами!
find_word=input(‘Enter word ‘ ») — просим пользователя ввести искомое слово
print(eng_words.get(find_word) or print(‘No such key’)) — выводим на экран ответ с помощью функции print , получаем значение ( get ). В противном случае, отвечаем, что не смогли отыскать нужное слово.
Функция rus() работает так же, но без инвертирования словаря.
Вы уже догадались: наш словарь «наоборот» нужен для того, чтобы не приходилось писать два словаря — мы просто меняем ключи и значения местами.
Попробуйте запустить mydictionary.py и насладитесь результатом.
Что сейчас делает наша программа?
Спрашивает искомое слово, выводит ответ. Но осталось ощущение, что всё слишком просто и чего-то не хватает. Давайте немного усложним задачу: создадим базу данных для словаря и дадим пользователю возможность добавлять свои значения.
Создание программы «Словарь» на Python.
Пример второй
Создание базы данных. Файл words_db.py
# words_db.py #!/usr/bin/env python # -*- coding:utf-8 -*- import shelve db = shelve.open(‘db_file’) db[‘earth’]=’земля’ db[‘word’]=’слово’ db[‘catch’]=’ловить’ db[‘find’]=’искать’ db.close()
База данных создаётся при помощи модуля shelve , импортируем его. Далее укажем входной файл: db_file , он открывается, в него записываются данные — теперь именно это наш словарь. Файл words.py , используемый в первом примере, нам больше не нужен.
После записи значений, базу данных нужно закрыть — db.close() . Создайте нашу базу данных — db_file :
$ python words_db.py
Восстановление базы данных из файла db_file
# dump_words_db.py #!/usr/bin/env python # -*- coding:utf-8 -*- import shelve db=shelve.open(‘db_file’) print(‘Yes’)
Путь к мастерству: создаём приложение-словарь на Python
Хотите стать мастером в Python? Тогда изучайте язык на практике. В этом материале рассказываем, как создать словарь на Python.
Интернет, с одной стороны, открывает доступ к большому объёму информации, но с другой, тормозит развитие. Согласитесь, изучая что-то новое, допустим, язык программирования Python, поиск ценных ресурсов занимает много сил и времени.
Из-за этого новички часто сдаются, переходят к чему-то более простому. Прежде чем мы пойдём дальше, нужно понять, что это не очередная статья из разряда «Как научиться программированию на Python с нуля», а нечто более ценное.
За этим материалом последует ещё несколько, в каждом из которых мы покажем, как создаются Python-приложения, параллельно разбираясь с полезными для разработки и анализа данных навыками и инструментами.
Первое приложение, которое мы сделаем − интерактивный словарь на Python. Кажется, что это просто, но не заблуждайтесь.
Что будет делать наш словарь на Python?
Его задача состоит в том, чтобы выводить на экран определение слова, которое задаст пользователь. В дополнение к этому, если пользователь сделает опечатку при вводе слова, программа предложит наиболее близкое слово, как обычно делает Google − «Вы имели в виду это вместо этого?». Ну а если у слова будет несколько определений, то программа выдаст все. Уже не так просто, правда?
Важно! Помимо изучения процесса создания приложения, обратите особое внимание на структуру кода.
Шаг №1 − Данные
Чтобы понимать принцип работы словаря, нужно определить, какие данные он будет использовать для выполнения действий − они представлены в формате JSON. Если вы уже знаете, что такое JSON, не бойтесь пропустить следующие несколько строк. Если же вы впервые услышали это слово или не уверены в своих знаниях, сейчас всё быстро объясним. Рекомендуем взглянуть вот на эти данные, потом мы их и будем использовать − раз и два.
Интересный факт: Каждую секунду генерируется примерно 2 500 000 000 000 000 000 байт данных
JSON, или JavaScript Object Notation, − это формат обмена данными, удобный как компьютерам, так и людям. Обычно он состоит из двух вещей − key и value. Представим, что key − это заброшенная территория, некто вынес постановление о том, что его нельзя использовать для строительства, например, вот это постановление примем за value. Если хотите вникнуть более серьёзно, посмотрите этот материал.
«заброшенный промышленный участок»: [«Площадка не может быть использована для строительства».]
Теперь перейдём к коду. Сначала мы импортируем библиотеку JSON, а затем используем метод загрузки этой библиотеки для работы с нашими данными в формате .json. Важно понимать, что мы загружаем данные из .json формата, но храниться они будут в переменной «data» в виде dict — словаря Python. Если вы незнакомы с dict, можете представить их как хранилище данных.
def retrive_definition(word):
return data[word]
word_user = input(«Enter a word: «)
Как только данные будут загружены, создадим функцию, которая будет принимать слово и искать определение этого слова в данных. Достаточно просто.
Шаг №2 − Проверка на существование слова
Использование оператора if-else поможет вам проверить существует слово или нет. Если слово отсутствует в данных, просто сообщите об этом пользователю − в нашем случае, будет напечатано «Такого слова не существует, пожалуйста, проверьте, не ошиблись ли вы при вводе».
def retrive_definition(word):
if word in data:
return data[word]
else:
return («The word doesn’t exist, please double check it.»)
word_user = input(«Enter a word: «)
Шаг №3 — Учёт регистра
Каждый пользователь пишет по-своему. Одни пишут только строчными, другие используют ещё и заглавные. Для нас важно сделать так, чтобы результат для всех был одинаковым. Например, результаты по запросам «Rain» и «rain» будут идентичны. Чтобы сделать это, мы собираемся преобразовать слово, введенное пользователем, в строчную запись буквы, потому что наши данные имеют одинаковый формат.
Сделать это можно с помощью метода lower() в Python.
Ситуация №1: Чтобы убедиться, что программа возвращает определение слов, начинающихся с заглавной буквы (например, Дели, Техас), мы также проверим наличие заглавных букв в условии else-if.
Ситуация №2: Чтобы убедиться, что программа возвращает определение аббревиатур (например, США, НАТО), мы также проверим прописные буквы.
def retrive_definition(word):
word = word.lower()
if word in data:
return data[word]
elif word.title() in data:
return data[word.title()]
elif word.upper() in data:
return data[word.upper()]
word_user = input(«Enter a word: «)
Теперь словарь на Python может выполнять свою основную функцию − выдавать определение. Идём дальше, поможем пользователю найти слово, если он допустил ошибку при вводе.
Шаг №4 − Поиск близкого слова
Теперь, если пользователь сделал опечатку при вводе слова, вы можете предложить наиболее близкое слово и спросить, имел ли он его в виду. Мы можем сделать это с помощью библиотеки Python difflib. Для этого существует два метода, объясним, как работают оба, а чем пользоваться, выбирайте сами.
Метод 1 − Соответствие последовательности
Сначала мы импортируем библиотеку и извлекаем из нее метод. Функция SequenceMatcher() принимает всего 3 параметра. Первый − junk, что означает, что если в слове есть пробелы или пустые строки, в нашем случае это не так. Второй и третий параметры − это слова, между которыми вы хотите найти сходство. А последний метод выдаст вероятность того, что слово подобрано правильно.
import difflib
from difflib import SequenceMatcher
value = SequenceMatcher(None, «rainn», «rain»).ratio()
Как видите, сходство между словами «rainn» и «rain» составляет 0,89 или 89%. Это один из способов найти нужное слово. Но в той же библиотеке есть другой метод, который выбирает точное совпадение со словом напрямую, без определения вероятности.
Метод 2 − Получение близких совпадений
Метод работает следующим образом: первый параметр − это слово, для которого вы хотите найти близкие совпадения. Второй параметр − это список слов для сравнения. Третий указывает, сколько совпадений вы хотите в качестве вывода. Вы помните, что мы получили вероятность 0,89 в предыдущем методе?
Последний метод использует это число, чтобы узнать, когда прекратить рассматривать слово как близкое совпадение (0,99 — самое близкое к слову). Эту цифру, порог, можно установить самостоятельно.
import difflib
from difflib import get_close_matches
output = get_close_matches(«rain», [«help»,»mate»,»rainy»], n=1, cutoff = 0.75)
Самое близкое слово из всех трех − rainy [rainy].
Шаг №5 — Возможно, вы имели в виду это?
Для удобства чтения я просто добавил часть кода if-else. Вы знакомы с первыми двумя утверждениями else-if, теперь разберемся с третьим. Сначала проверяется длина полученных близких совпадений. Функция получения близких совпадений принимает слово, введенное пользователем, в качестве первого параметра, и весь наш набор данных сопоставляется с этим словом.
Здесь key − это слова в наших данных, а value − это их определение. [0] в операторе указывает на самое близкое среди всех совпадений.
if word in data:
return data[word]
elif word.title() in data:
return data[word.title()]
elif word.upper() in data:
return data[word.upper()]
elif len(get_close_matches(word, data.keys())) > 0:
return («Did you mean %s instead?» % get_close_matches(word, data.keys())[0])
Да, об этом мы и говорили. Что теперь? Если это то слово, которое имел в виду пользователь, вы должны получить определение этого слова. Об этом далее
Шаг №6 − Получение определения
Ещё один if-else, и вот оно − определение нужного слова.
elif len(get_close_matches(word, data.keys())) > 0:
action = input(«Did you mean %s instead? [y or n]: » % get_close_matches(word, data.keys())[0])
if (action == «y»):
return data[get_close_matches(word, data.keys())[0]]
elif (action == «n»):
return («The word doesn’t exist, yet.»)
else:
return («We don’t understand your entry. Apologies.»)
Шаг №7 − Вишенка на торте
Конечно, это дает нам определение слова «rain», но есть квадратные скобки и выглядит это не очень хорошо. Давайте удалим их и сделаем вид более чистым. Слово «rain» имеет более одного определения, вы заметили? Мы будем повторять вывод таких слов, имеющих более одного определения.
if type(output) == list:
for item in output:
print(«-«,item)
else:
print(«-«,output)
Выглядит намного лучше, не так ли? Ниже прикрепили весь код для справки. Не стесняйтесь изменять и обновлять его по своему усмотрению.
Итого
import json
from difflib import get_close_matches
def retrive_definition(word):
word = word.lower()
if word in data:
return data[word]
elif word.title() in data:
return data[word.title()]
elif word.upper() in data:
return data[word.upper()]
elif len(get_close_matches(word, data.keys())) > 0:
action = input(«Did you mean %s instead? [y or n]: » % get_close_matches(word, data.keys())[0])
if (action == «y»):
return data[get_close_matches(word, data.keys())[0]]
elif (action == «n»):
return («The word doesn’t exist, yet.»)
else: return («We don’t understand your entry. Apologies.»)
word_user = input(«Enter a word: «)
if type(output) == list:
for item in output:
print(«-«,item)
else:
print(«-«,output)
Заключение
Вот мы и закончили создавать словарь на Python. Изучая одно, вы параллельно изучаете другие вещи, о которых даже не думали. Этот материал научил работе с данными JSON, основными функциями Python, библиотекой difflib и тому, как писать чистый код. Теперь попробуйте создать собственное приложение, с опорой на информацию из этого текста. Как закончите, переходите к новому материалу из цикла.
Источник: proglib.io
Реализация словаря в Python
Всем привет, 30 апреля в ОТУС стартует курс «Алгоритмы для разработчиков», именно к этому приурочена публикация сегодняшнего материала. Начнём.
В этой статье вы узнаете, как в Python реализованы словари.
Словари индексируются с помощью ключей, и они могут рассматриваться в качестве ассоциированных массивов. Давайте добавим 3 пары ключ/значение (key/value) в словарь:
>>> d = >>> d[‘c’] = 3 >>> d
К значениями можно получить доступ следующим образом:
>>> d[‘a’] 1 >>> d[‘b’] 2 >>> d[‘c’] 3 >>> d[‘d’] Traceback (most recent call last): File «», line 1, in KeyError: ‘d’
Ключа “d” не существует, поэтому появится ошибка KeyError.
Словари в Python реализуются с помощью хэш-таблиц. Они представляют собой массивы, индексы которых вычисляются с помощью хэш-функций. Цель хэш-функции – равномерно распределить ключи в массиве. Хорошая хэш-функция минимизирует количество коллизий, т.е. вероятность того, что разные ключи будут иметь один хэш. В Python нет такого рода хэш-функций. Его наиболее важные хэш-функции (для строк и целочисленных значений) выдают похожие значения в общих случаях:
>>> map(hash, (0, 1, 2, 3)) [0, 1, 2, 3] >>> map(hash, («namea», «nameb», «namec», «named»)) [-1658398457, -1658398460, -1658398459, -1658398462]
Будем предполагать, что до конца этой статьи мы будем использовать строки в качестве ключей. Хэш-функция в Python для строк определяется следующим образом:
arguments: string object returns: hash function string_hash: if hash cached: return it set len to string’s length initialize var p pointing to 1st char of string object set x to value pointed by p left shifted by 7 bits while len >= 0: set var x to (1000003 * x) xor value pointed by p increment pointer p set x to x xor length of string object cache x as the hash so we don’t need to calculate it again return x as the hash
Если выполнить hash(‘a’) в Python, то отработает string_hash() и вернет 12416037344 . Здесь мы по умолчанию используем 64-х разрядную машину.
Если для хранения пар значение/ключ используется массив размера Х , то для вычисления индекса ячейки пары в массиве будет использована маска, которая вычисляется как Х-1 . Такой подход делает вычисление индексов ячеек быстрым. Вероятность найти пустую ячейку достаточно высока из-за механизма изменения размера, который описан ниже. Это означает, что простое вычисление имеет смысл в большинстве случаев. Размер массива равен 8, индекс для ‘a’ будет равен: hash(‘a’) perturb >>= PERTURB_SHIFT; use j % 2**i as the next table index;
Рекурсия в (5*j)+1 быстро увеличивает большие различия в битах, которые не повлияли на изначальный индекс. Переменная «perturb» при этом принимает в себя другие биты хэш-кода.
Давайте из любопытства посмотрим, чтобы произойдет, если у нас будет последовательность пробирования с размером таблицы 32 и j=3.
3 -> 11 -> 19 -> 29 -> 5 -> 6 -> 16 -> 31 -> 28 -> 13 -> 2…
Вы можете узнать больше об этой последовательности пробирования, обратившись к исходному коду dictobject.c. Детальное объяснение работы механизма пробирования можно найти в верхней части файла.
Давайте с этим примером обратимся к исходному коду Python.
Структуры словаря С
Для хранения записи в словаре используется следующая структура C: пара ключ/значение. Хранятся хэш, ключ и значение. PyObject является базовым классом для объектов в Python.
typedef struct < Py_ssize_t me_hash; PyObject *me_key; PyObject *me_value; >PyDictEntry;
Следующая структура представляет собой словарь. ma_fill – это суммарное количество используемых и неактивных ячеек. Ячейка (slot) считается неактивной, когда удаляется ключевая пара. ma_used – это количество используемых (активных) ячеек. ma_mask равняется размеру массива -1 и используется для расчета индекса ячейки. ma_table – это массив, а ma_smalltable – изначальный массив размера 8.
typedef struct _dictobject PyDictObject; struct _dictobject < PyObject_HEAD Py_ssize_t ma_fill; Py_ssize_t ma_used; Py_ssize_t ma_mask; PyDictEntry *ma_table; PyDictEntry *(*ma_lookup)(PyDictObject *mp, PyObject *key, long hash); PyDictEntry ma_smalltable[PyDict_MINSIZE]; >;
Инициализация словаря
Когда вы только создаете словарь, вызывается функция PyDict_New() . Я удалил некоторые строки и преобразовал код на C в псевдокод, чтобы сосредоточиться на ключевых понятиях.
- Возвращает объект-словарь;
- Аллоцирует новый объект-словарь;
- Очищает таблицу словаря;
- Устанавливает количество используемых ячеек словаря и неиспользуемых ячеек ( ma_fill ) в 0;
- Устанавливает количество активных ячеек ( ma_used ) в 0;
- Устанавливает маску словаря ( ma_value ) в значение равное размеру словаря – 1 = 7;
- Устанавливает функцией поиска по словарю lookdict_string ;
- Возвращает аллоцированный объект-словарь.
Когда добавляется новая пара ключ/значение, вызывается PyDict_SetItem() . Эта функция принимает на вход указатель на объект-словарь и пару ключ/значение. Она проверяет, является ли ключ строкой и вычисляет хэш или повторно использует закэшированный, если такой существует. insertdict() вызывается для добавления новой пары ключ/значение и размер словаря меняется, если количество используемых и неиспользуемых ячеек больше 2/3 размера массива.
Почему именно 2/3? Это необходимо, чтобы убедиться, что последовательность пробирования сможет найти свободные ячейки достаточно быстро. Позже мы рассмотрим функцию для изменения размера.
arguments: dictionary, key, value returns: 0 if OK or -1 function PyDict_SetItem: if key’s hash cached: use hash else: calculate hash call insertdict with dictionary object, key, hash and value if key/value pair added successfully and capacity over 2/3: call dictresize to resize dictionary’s table
inserdict() использует функцию поиска lookdict_string() , чтобы найти свободную ячейку. Эта же функция используется для поиска ключа.
lookdict_string() вычисляет индекс ячейки, используя хэш и значения маски. Если она не может найти ключ по значению индекс ячейки = хэш mask), она начинает пробирование, используя цикл, описанный выше, пока не найдет свободную ячейку. При первой попытке пробирования, если ключ равен null , она возвращает неиспользуемую ячейку, если он найден во время первого поиска. Таким образом обеспечивается приоритет для повторного использования ранее удаленных ячеек.
Мы хотим добавить следующие пары ключ/значение: . Вот что произойдет:
Структура словаря аллоцируется с размером таблицы равным 8.
- PyDict_SetItem: key = ‘a’, value = 1
- hash = hash(‘a’) = 12416037344
- insertdict
- lookdict_string
- slot index = hash 7 = 0
- slot 0 не используется, возвращаем эту ячейку
- hash = hash(‘b’) = 12544037731
- insertdict
- lookdict_string
- slot index = hash 7 = 3
- slot 3 не используется, возвращаем эту ячейку
- hash = hash(‘z’) = 15616046971
- insertdict
- lookdict_string
- slot index = hash 7 = 3
- slot 3 используется, пробуем другую ячейку: 5 свободна
- hash = hash(‘y’) = 15488046584
- insertdict
- lookdict_string
- slot index = hash 7 = 0
- slot 0 используется, пробуем другую ячейку: 1 свободна
- hash = hash(‘c’) = 12672038114
- insertdict
- lookdict_string
- slot index = hash 7 = 2
- slot 2 не используется, возвращаем эту ячейку
- hash = hash(‘x’) = 15360046201
- insertdict
- lookdict_string
- slot index = hash 7 = 1
- slot 1 используется, пробуем другую ячейку: 7 свободна
Сейчас используется 6 ячеек из 8, занято более 2/3 емкости массива. dictresize() вызывается для аллоцирования большего массива. Эта функция также занимается копированием записей из старой таблицы в новую.
dictresize () вызывается с minused = 24 в нашем случае, где 4 * ma_used . 2 * ma_used используется, когда количество используемых ячеек очень велико (больше 50000). Почему в 4 раза больше ячеек? Это уменьшает количество шагов для реализации изменения размера и увеличивает разреженность.
Новый размер таблицы должен быть больше 24, он рассчитывается путем смещения текущего размера на 1 бит влево до тех пор, пока размер таблицы не станет больше 24. В итоге он будет равен 32, например, 8 -> 16 -> 32.
Вот что происходит с нашей таблицей во время изменения размера: выделяется новая таблица размером 32. Старые записи таблицы вставляются в новую таблицу с использованием нового значения маски, равного 31. В итоге получается следующее:
Удаление элементов
PyDict_DelItem() вызывается для удаления записей. Для ключа записи вычисляется хэш, далее вызывается функция поиска, чтобы вернуть запись. Теперь ячейка пустая.