Вопрос:

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

python hash dictionary complexity-theory

66288 просмотра

6 ответа

2770 Репутация автора

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

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

Значения, которые я хэширую, являются кортежами точек. Каждая точка: (x, y), 0 <= x, y <= 50.
Каждый ключ в словаре: кортеж из 2-5 точек: ((x1, y1), (x2, y2), (x3, у3), (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
Автор: x10 Источник Размещён: 26.12.2009 02:32

Ответы (6)


3 плюса

181040 Репутация автора

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

Автор: Eli Bendersky Размещён: 26.12.2009 02:35

49 плюса

46687 Репутация автора

Решение

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

Лучший способ - проверить и взглянуть на хэши объектов, которые вы используете. В CPython Dict использует Int PyObject_Hash (PyObject * о) , которая является эквивалентом 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 часов)

Автор: Yacoby Размещён: 26.12.2009 02:36

3 плюса

34886 Репутация автора

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

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

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

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

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

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

Автор: James Thompson Размещён: 26.12.2009 02:44

1 плюс

278852 Репутация автора

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

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

Автор: Ned Batchelder Размещён: 26.12.2009 03:20

2 плюса

76338 Репутация автора

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

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

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

Автор: Robert Rossney Размещён: 26.12.2009 07:00

1 плюс

68279 Репутация автора

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

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

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

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

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

Автор: John Machin Размещён: 26.12.2009 09:26
Вопросы из категории :
32x32