Временная сложность доступа к Python dict
Я пишу простую программу Python.
Моя программа, кажется, страдает от линейного доступа до словарей, его время выполнения растет экспоненциально даже при том, что алгоритм квадратичен.
Я использую словарь для значений memoize. Это, кажется, узкое место.
Значения, которые я хеширую, являются кортежами точек. Каждая точка: (x, y), 0 <= x, y <= 50
Каждый ключ в словаре: кортеж 2-5 точек: ((x1, y1), (x2, y2), (x3, y3), (x4, y4))
Ключи читаются много раз чаще, чем они записаны.
Я корректен, который Python dicts переносит с линейных времен доступа с такими исходными данными?
Насколько я знаю, наборы гарантировали логарифмические времена доступа.
Как я могу моделировать dicts использующие наборы (или что-то подобное) в Python?
редактирование Согласно запросу, вот (упрощенная) версия функции memoization:
def memoize(fun):
memoized = {}
def memo(*args):
key = args
if not key in memoized:
memoized[key] = fun(*args)
return memoized[key]
return memo
6 ответов
См. Сложность времени . Python dict - это хеш-карта, поэтому его худший случай - O (n), если хеш-функция плохая и приводит к множеству коллизий. Однако это очень редкий случай, когда каждый добавленный элемент имеет один и тот же хэш и поэтому добавляется в одну и ту же цепочку, что для основной реализации Python было бы крайне маловероятным. Средняя временная сложность, конечно же, O (1).
Лучшим методом будет проверка и просмотр хешей объектов, которые вы используете. CPython Dict использует int PyObject_Hash (PyObject * o) , который эквивалентен hash (o) .
После быстрой проверки я не но удалось найти два кортежа, которые имеют одно и то же значение,
Вы ошиблись. dict доступ вряд ли будет здесь вашей проблемой. Это почти наверняка O (1), если только у вас нет очень странных входных данных или очень плохой функции хеширования. Вставьте образец кода из своего приложения для лучшей диагностики.
dict доступ вряд ли будет вашей проблемой здесь. Это почти наверняка O (1), если только у вас нет очень странных входных данных или очень плохой функции хеширования. Вставьте образец кода из своего приложения для лучшей диагностики. dict доступ вряд ли будет здесь вашей проблемой. Это почти наверняка O (1), если только у вас нет очень странных входных данных или очень плохой функции хеширования. Вставьте образец кода из своего приложения для лучшей диагностики. Было бы легче делать предложения, если бы вы предоставили пример кода и данных.
Доступ к словарю вряд ли станет проблемой, поскольку эта операция составляет O (1) в среднем, а в худшем случае O (N) амортизируется . Возможно, встроенные функции хеширования сталкиваются с конфликтами ваших данных. Если у вас возникли проблемы со встроенной функцией хеширования, вы можете предоставить свою.
Реализация словаря Python снижает среднюю сложность поиск по словарю до O (1) по требуя, чтобы ключевые объекты обеспечивали «хеш-функция». Такая хеш-функция берет информацию в ключевом объекте и использует его для получения целого числа, называется хеш-значением. Это хеш-значение затем используется для определения "ведро" эта пара (ключ, значение) должна быть помещенным в.
Вы можете перезаписать метод __hash__ в своем классе, чтобы реализовать пользовательскую хэш-функцию следующим образом:
def __hash__(self):
return hash(str(self))
В зависимости от того, как на самом деле выглядят ваши данные, вы можете придумать более быструю хеш-функцию с меньшим количеством конфликтов, чем стандартная функция. Однако это маловероятно. См. страницу Python Wiki на ключах словаря для получения дополнительной информации.
Как отмечали другие, доступ к dicts в Python выполняется быстро. С учетом их центральной роли, они, вероятно, являются самой отлаженной структурой данных на языке. Проблема в другом.
Сколько кортежей вы запоминаете? Вы учли объем памяти? Возможно, вы все свое время проводите в распределителе памяти или подкачке памяти.
Чтобы ответить на Ваши конкретные вопросы:
Q1: "" "Правильно ли я понимаю, что питоновые диктограммы страдают от линейных времен доступа с такими входами?""
A1: Если Вы имеете в виду, что среднее время поиска - O(N), где N - это количество записей в диктограмме, то, скорее всего, Вы ошибаетесь. Если Вы правы, то сообщество Python очень хочет знать, при каких обстоятельствах Вы правы, так что проблему можно смягчить или, по крайней мере, предупредить. Ни "примерный", ни "упрощённый" код не полезны. Пожалуйста, покажите реальный код и данные, которые воспроизводят проблему. Код должен быть инструментирован такими вещами, как количество элементов dict и количество обращений к диктату для каждого P, где P - это количество точек в ключе (2 <= P <= 5)
Q2: "" "Насколько я знаю, множества имеют гарантированное логарифмическое время доступа. Как я могу имитировать диктаты, используя множества(или что-то подобное) на Python?""
A2: Множества имеют гарантированное логарифмическое время доступа в каком контексте? Для реализаций на Python такой гарантии нет. Последние версии CPython на самом деле используют усеченную реализацию dict (только ключи, без значений), так что ожидание - это среднее поведение O(1). Как можно имитировать диктаты с помощью сетов или чего-то подобного на любом языке? Краткий ответ: с большим трудом, если вам нужна функциональность, выходящая за рамки dict.has_key(key).
Моя программа, кажется, страдает от линейного доступа к словарям, время ее выполнения растет в геометрической прогрессии, несмотря на то, что алгоритм квадратичный.
Я использую словарь для запоминания значений. Похоже, что это узкое место.
Это свидетельствует об ошибке в вашем методе запоминания.
.