Временная сложность доступа к Python dict

Question

Я пишу простую программу на Python.

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

Значения, которые я хэширую, являются кортежами точек. Каждая точка: (x, y), 0 <= x, y <= 50 <br> Каждый ключ в словаре: кортеж из 2-5 точек: ((x1, y1), (x2, y2), (x3, y3), (x4, y4))

Ключи читаются во много раз чаще, чем пишутся.

Правильно ли я понимаю, что на таких входах python-диктат имеет линейное время доступа?

Насколько мне известно, наборы имеют гарантированное логарифмическое время доступа.
Как я могу имитировать дикты, используя наборы (или что-то подобное) в Python?

edit В соответствии с запросом (упрощенная) версия функции памятки:

def memoize(fun):
    memoized = {}
    def memo(*args):
        key = args
        if not key in memoized:
            memoized[key] = fun(*args)
        return memoized[key]
    return memo

Answer 1

См. Сложность времени . Диктофон python является хеш-картой, поэтому его наихудший случай - O (n), если хеш-функция неверна и приводит к множеству коллизий. Однако это очень редкий случай, когда каждый добавленный элемент имеет одинаковый хэш и поэтому добавляется в одну цепочку, что для крупной реализации Python было бы крайне маловероятным. Средняя сложность по времени, конечно, O (1).

Лучший способ - проверить и взглянуть на хэши объектов, которые вы используете. CPython Dict использует int PyObject_Hash (PyObject * o) , что эквивалентно hash(o).

После быстрой проверки мне пока не удалось найти два кортежа, которые хэшируют одно и то же значение, что указывало бы, что поиск равен O (1)

l = []
for x in range(0, 50):
    for y in range(0, 50):
        if hash((x,y)) in l:
            print "Fail: ", (x,y)
        l.append(hash((x,y)))
print "Test Finished"

CodePad (доступно в течение 24 часов)

Answer 2

Было бы проще сделать предложения, если вы предоставили пример кода и данные.

Доступ к словарю вряд ли будет проблемой, поскольку эта операция в среднем равна O (1), а наихудший случай O (N) . Возможно, что встроенные функции хеширования испытывают коллизии для ваших данных. Если у вас есть проблемы со встроенной функцией хеширования, вы можете предоставить свою собственную.

Реализация словаря Python уменьшает среднюю сложность поиск по словарю в O (1) требуя, чтобы ключевые объекты обеспечивали функция "хэш" Такая хеш-функция берет информацию в ключевом объекте и использует его для получения целого числа, называется хэш-значением. Это хэш-значение затем используется для определения того, какой "bucket" эта пара (ключ, значение) должна быть помещенным в.

Вы можете перезаписать метод __hash__ в своем классе, чтобы реализовать пользовательскую хеш-функцию, подобную этой:

def __hash__(self):    
    return hash(str(self))

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

Answer 3

Вы не правы. dict доступ вряд ли будет вашей проблемой здесь. Это почти наверняка O (1), если у вас нет очень странных входных данных или очень плохой функции хеширования. Вставьте пример кода из вашего приложения для лучшей диагностики.

Answer 4

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

Я использую словарь для запоминания значений. Это кажется узким местом.

Это свидетельствует об ошибке в вашем методе запоминания.

Answer 5

Чтобы ответить на ваши конкретные вопросы:

Q1: "" "Правильно ли я, что в Python-диктофоне время линейного доступа зависит от таких входов?" ""

A1: Если вы имеете в виду, что среднее время поиска равно O (N), где N - количество записей в диктовке, то весьма вероятно, что вы ошибаетесь. Если вы правы, сообщество Python очень хотело бы знать, при каких обстоятельствах вы правы, чтобы проблему можно было смягчить или хотя бы предупредить. Ни «примерный» код, ни «упрощенный» код не являются полезными. Пожалуйста, покажите фактический код и данные, которые воспроизводят проблему. Код должен быть снабжен такими вещами, как количество элементов dict и количество обращений к dict для каждого P, где P - количество точек в ключе (2 <= P <= 5) </p>

Q2: "" "Насколько мне известно, наборы имеют гарантированное логарифмическое время доступа. Как я могу имитировать дикты, используя наборы (или что-то подобное) в Python? "" "

A2: В каком контексте наборы имеют гарантированное логарифмическое время доступа? Нет такой гарантии для реализаций Python. В последних версиях CPython фактически используется сокращенная реализация dict (только ключи, без значений), поэтому ожидается среднее поведение O (1). Как вы можете моделировать дикты с помощью наборов или чего-то подобного на любом языке? Краткий ответ: с чрезвычайной трудностью, если вам нужна какая-либо функциональность, кроме dict.has_key(key).

Answer 6

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

Сколько кортежей вы запоминаете? Рассматривали ли вы объем памяти? Возможно, вы проводите все свое время в распределителе памяти или памяти подкачки.