Что является самым быстрым (для доступа) структуроподобным объектом в Python?

Question

Я оптимизирую некоторый код, основное узкое место которого выполняется, и доступ к очень большому списку структуроподобных объектов. В настоящее время я использую именованные кортежи для удобства чтения. Но некоторые быстрые сравнительные тесты с использованием «timeit» показывают, что это действительно неправильный путь, когда производительность является фактором:

Именованные кортежи с a, b, c:

>>> timeit("z = a.c", "from __main__ import a")
0.38655471766332994

Класс с использованием __slots__, с a, b, c:

>>> timeit("z = b.c", "from __main__ import b")
0.14527461047146062

Словарь с ключами a, b, c:

>>> timeit("z = c['c']", "from __main__ import c")
0.11588272541098377

Кортеж с тремя значениями, используя постоянный ключ:

>>> timeit("z = d[2]", "from __main__ import d")
0.11106188992948773

Список с тремя значениями с использованием константного ключа:

>>> timeit("z = e[2]", "from __main__ import e")
0.086038238242508669

Кортеж с тремя значениями, используя локальный ключ:

>>> timeit("z = d[key]", "from __main__ import d, key")
0.11187358437882722

Список с тремя значениями с использованием локального ключа:

>>> timeit("z = e[key]", "from __main__ import e, key")
0.088604143037173344

Прежде всего, есть ли что-нибудь в этих маленьких timeit тестах, которые сделали бы их недействительными? Я запускал каждый из них несколько раз, чтобы убедиться, что никакое случайное системное событие не отбросило их, и результаты были почти идентичны.

Похоже, словари обеспечивают лучший баланс между производительностью и удобочитаемостью, а занятия идут на втором месте. Это прискорбно, так как для моих целей мне также нужен объект, подобный последовательности; отсюда мой выбор именованных кортежей.

Списки значительно быстрее, но постоянные ключи не поддерживаются; Мне нужно создать группу констант индекса, то есть KEY_1 = 1, KEY_2 = 2 и т. Д., Что тоже не идеально.

Я застрял с этим выбором, или есть альтернатива, которую я пропустил?

Answer 1

Следует иметь в виду, что именованные кортежи оптимизированы для доступа в виде кортежей. Если вы измените свой метод доступа на a[2] вместо a.c, вы увидите производительность, аналогичную кортежам. Причина в том, что средства доступа к именам эффективно преобразуются в вызовы self [idx], поэтому платите за индексирование и цену поиска имени.

Если ваш шаблон использования таков, что доступ по имени является общим, а доступ как кортеж - нет, вы могли бы написать быстрый эквивалент namedtuple, который делает вещи противоположным образом: откладывает поиск индекса для доступа по имени. Тем не менее, вы будете платить цену за поиск индекса. Например, вот быстрая реализация:

def makestruct(name, fields):
    fields = fields.split()
    import textwrap
    template = textwrap.dedent("""\
    class {name}(object):
        __slots__ = {fields!r}
        def __init__(self, {args}):
            {self_fields} = {args}
        def __getitem__(self, idx): 
            return getattr(self, fields[idx])
    """).format(
        name=name,
        fields=fields,
        args=','.join(fields), 
        self_fields=','.join('self.' + f for f in fields))
    d = {'fields': fields}
    exec template in d
    return d[name]

Но время очень плохое, когда __getitem__ нужно назвать:

namedtuple.a  :  0.473686933517 
namedtuple[0] :  0.180409193039
struct.a      :  0.180846214294
struct[0]     :  1.32191514969

т. Е. Та же производительность, что и у класса __slots__ для доступа к атрибутам (неудивительно, что это так), но огромные штрафы из-за двойного поиска при доступе на основе индекса. (Примечательно, что __slots__ на самом деле не сильно помогает в скорости. Он экономит память, но время доступа примерно без них.)

Третьим вариантом будет дублирование данных, например. создайте подкласс из списка и сохраните значения как в атрибутах, так и в списках данных. Однако вы на самом деле не получаете список-эквивалентную производительность. Есть большая скорость, достигнутая только в подклассах (ввод проверок на перегрузки чистого Python). Таким образом, struct [0] все еще занимает около 0,5 с (по сравнению с 0,18 для необработанного списка) в этом случае, и вы удваиваете использование памяти, так что это может не стоить.

Answer 2

Этот вопрос довольно старый (интернет-время), поэтому я подумал, что попробую сегодня повторить ваш тест, как с обычным CPython (2.7.6), так и с pypy (2.2.1) и посмотреть, как различные методы по сравнению. (Я также добавил в индексированном поиске именованный кортеж.)

Это небольшой микропроцессор, так что YMMV, но pypy, похоже, ускорил доступ к именованным кортежам в 30 раз по сравнению с CPython (тогда как доступ к словарям ускорился только в 3 раза).

from collections import namedtuple

STest = namedtuple("TEST", "a b c")
a = STest(a=1,b=2,c=3)

class Test(object):
    __slots__ = ["a","b","c"]

    a=1
    b=2
    c=3

b = Test()

c = {'a':1, 'b':2, 'c':3}

d = (1,2,3)
e = [1,2,3]
f = (1,2,3)
g = [1,2,3]
key = 2

if __name__ == '__main__':
    from timeit import timeit

    print("Named tuple with a, b, c:")
    print(timeit("z = a.c", "from __main__ import a"))

    print("Named tuple, using index:")
    print(timeit("z = a[2]", "from __main__ import a"))

    print("Class using __slots__, with a, b, c:")
    print(timeit("z = b.c", "from __main__ import b"))

    print("Dictionary with keys a, b, c:")
    print(timeit("z = c['c']", "from __main__ import c"))

    print("Tuple with three values, using a constant key:")    
    print(timeit("z = d[2]", "from __main__ import d"))

    print("List with three values, using a constant key:")
    print(timeit("z = e[2]", "from __main__ import e"))

    print("Tuple with three values, using a local key:")
    print(timeit("z = d[key]", "from __main__ import d, key"))

    print("List with three values, using a local key:")
    print(timeit("z = e[key]", "from __main__ import e, key"))

Python Результаты:

Named tuple with a, b, c:
0.124072679784
Named tuple, using index:
0.0447055962367
Class using __slots__, with a, b, c:
0.0409136944224
Dictionary with keys a, b, c:
0.0412045334915
Tuple with three values, using a constant key:
0.0449477955531
List with three values, using a constant key:
0.0331083467148
Tuple with three values, using a local key:
0.0453569025139
List with three values, using a local key:
0.033030056702

PyPy Результаты:

Named tuple with a, b, c:
0.00444889068604
Named tuple, using index:
0.00265598297119
Class using __slots__, with a, b, c:
0.00208616256714
Dictionary with keys a, b, c:
0.013897895813
Tuple with three values, using a constant key:
0.00275301933289
List with three values, using a constant key:
0.002760887146
Tuple with three values, using a local key:
0.002769947052
List with three values, using a local key:
0.00278806686401

Answer 3

Пара баллов и идей:

1) Вы рассчитываете время доступа к одному и тому же индексу много раз подряд. Ваша настоящая программа, вероятно, использует произвольный или линейный доступ, который будет иметь другое поведение. В частности, будет больше промахов кэша ЦП. Вы можете получить немного другие результаты, если будете использовать реальную программу.

2) OrderedDictionary записывается в качестве оболочки около dict, поэтому он будет медленнее, чем dict. Это не решение.

3) Вы пробовали и новые, и старые классы? (классы нового стиля наследуются от object; классы старого стиля не наследуют)

4) Вы пытались использовать psyco или Unladen Swallow ?

5) Ваш внутренний цикл изменяет данные или просто обращается к ним? Перед входом в цикл может оказаться возможным преобразовать данные в максимально эффективную форму, но используйте наиболее удобную форму в другом месте программы.

Answer 4

Я хотел бы либо (а) изобрести какое-то кэширование, специфичное для рабочей нагрузки, и переложить хранение и извлечение моих данных в процесс, напоминающий memcachedb, для улучшения масштабируемости, а не только производительности, либо (б) переписать как Расширение C, с собственным хранилищем данных. Тип упорядоченного словаря возможно.

Вы можете начать с этого: http://www.xs4all.nl/~anthon/Python/ordereddict/

Answer 5

Вы можете создать последовательность ваших классов, например, добавив методы __iter__ и __getitem__, чтобы они стали такими же (индексируемые и итерируемые).

Будет ли OrderedDict работать? Доступно несколько реализаций, и оно включено в модуль Python31 collections.