Идиоматический способ сделать список / диктовать в Cython?

Question

Моя проблема: я обнаружил, что обработка больших наборов данных с помощью необработанного C ++ с использованием карты и вектора STL часто может быть значительно быстрее (и с меньшим объемом памяти), чем при использовании Cython.

Я полагаю, что эта потеря скорости связана с использованием списков и диктов Python, и что в Cython могут быть некоторые хитрости для использования менее обремененных структур данных. Например, на этой странице (http://wiki.cython.org/tutorials/numpy) показано, как очень быстро создавать пустые массивы в Cython, предварительно задав размер и типы массива ND.

Вопрос: есть ли способ сделать что-то подобное со списками / диктовками, например примерно указав, сколько элементов или пар (ключ, значение) вы ожидаете иметь в них? То есть, есть ли идиоматический способ преобразования списков / диктов в (быстрые) структуры данных в Cython?

Если нет, то мне просто нужно написать его на C ++ и обернуть в импорт Cython.

Answer 1

Cython теперь имеет поддержку шаблонов и поставляется с объявлениями для некоторых контейнеров STL.

См. http://docs.cython.org/src/userguide/wrapping_CPlusPlus.html#standard-library

Вот пример, который они дают:

from libcpp.vector cimport vector

cdef vector[int] vect
cdef int i
for i in range(10):
    vect.push_back(i)
for i in range(10):
    print vect[i]

Answer 2

Выполнение аналогичных операций в Python, как в C ++, часто может быть медленнее. list и dict на самом деле реализованы очень хорошо, но вы получаете много накладных расходов, используя объекты Python, которые являются более абстрактными, чем объекты C ++, и требуют гораздо большего поиска во время выполнения.

Кстати, std::vector реализован очень похоже на list. std::map, однако, фактически реализован таким образом, что многие операции выполняются медленнее, чем dict, так как его размер становится большим. Для достаточно больших примеров каждого из них dict преодолевает постоянный коэффициент, на который он медленнее, чем std::map, и фактически выполняет такие операции, как поиск, вставка и т. Д.

Если вы хотите использовать std::map и std::vector, вас ничто не остановит. Вам придется обернуть их самостоятельно, если вы хотите выставить их на Python. Не будьте шокированы, если эта упаковка занимает все или большую часть времени, которое вы надеялись сэкономить. Мне не известны какие-либо инструменты, которые делают это автоматически для вас.

Существуют вызовы C API для управления созданием объектов с некоторыми подробностями. Вы можете сказать «Создайте список по крайней мере с таким количеством элементов», но это не улучшит общую сложность вашей операции создания и заполнения списка. Конечно, это не сильно изменится позже, когда вы попытаетесь изменить свой список.

Мой общий совет:

• Если вам нужен массив фиксированного размера (вы говорите об указании размера списка), вы, возможно, захотите что-то вроде пустого массива.

• Я сомневаюсь, что вы получите какое-либо ускорение от использования std::vector сверх list для общей замены в вашем коде. Если вы хотите использовать его за кулисами, это может дать вам удовлетворительное улучшение размера и пространства (я, конечно, не знаю без измерений, как и вы;)).

• dict на самом деле делает свою работу очень хорошо. Я определенно не стал бы пытаться ввести новый тип общего назначения для использования в Python, основанный на std::map, который имеет худшую алгоритмическую сложность во времени для многих важных операций и - по крайней мере в некоторых реализациях - оставляет пользователю некоторые оптимизации, которые dict уже есть.

  Если бы я хотел что-то, что работало бы немного больше, например std::map, я бы, вероятно, использовал базу данных. Это обычно то, что я делаю, если вещи, которые я хочу хранить в dict (или, если на то пошло, вещи, которые я храню в list), становятся слишком большими для меня, чтобы чувствовать себя комфортно в памяти. Python имеет sqlite3 в stdlib и драйверы для всех остальных основных баз данных.

Answer 3

C ++ работает быстро не только из-за статических объявлений вектора и входящих в него элементов, но и из-за того, что при использовании шаблонов / шаблонов указывается, что вектор будет только содержать элементы определенного типа например, вектор с кортежами из трех элементов. Cython не может сделать это в последнюю очередь, и это звучит нетривиально - его нужно как-то применять во время компиляции (проверка типов во время выполнения - это то, что Python уже делает). Так что сейчас, когда вы вытаскиваете что-то из списка в Cython, невозможно заранее узнать, что это за тип, а помещение его в типизированную переменную только добавляет проверку типа, а не скорость. Это означает, что в этом отношении нет способа обойти интерпретатор Python, и мне кажется, что это наиболее важный недостаток Cython для нечисловых задач.

Ручной способ решения этой проблемы - создать подкласс списка python / dict (или, возможно, std :: vector) с классом cdef для определенного типа комбинации элемента или значения ключа. Это будет то же самое, что и код, который генерируют шаблоны. Пока вы используете результирующий класс в коде Cython, он должен обеспечить улучшение.

Использование баз данных или массивов просто решает другую проблему, потому что речь идет о помещении произвольных объектов (но с определенным типом, предпочтительно с классом cdef) в контейнеры.

И std :: map не следует сравнивать с dict; std :: map поддерживает ключи в отсортированном порядке, потому что это сбалансированное дерево, dict решает другую проблему. Лучшее сравнение было бы точным и хэш-таблицей Google.

Answer 4

Вы можете взглянуть на стандартный модуль array для Python, если это подходит для вашей настройки Cython. Я не уверен, так как я никогда не использовал Cython.

Answer 5

Нет способа получить нативные списки / диктанты Python до скорости карты / вектора C ++ или даже где-нибудь рядом. Это не имеет ничего общего с распределением или объявлением типа, а скорее с оплатой интерпретатора. Пример, который вы упоминаете (numpy), является расширением C и написан на C именно по этой причине.