Манипулирование строками в Cython

Question

У меня есть код, который выполняет некоторые очень ресурсоемкие манипуляции со строками, и я искал способы повысить производительность.

(РЕДАКТИРОВАТЬ: я занимаюсь такими вещами, как нахождение самой длинной общей подстроки, запускаю множество регулярных выражений, которые могут быть лучше выражены как конечные автоматы в c, убираю комментарии из HTML, и тому подобное)

В настоящее время я пытаюсь перенести часть кода на Cython , услышав много хорошего об этом. Тем не менее, похоже, что основное внимание в Cython уделяется численным вычислениям, а работа со строками едва документирована.

Юникод также может быть большой проблемой.

Мои вопросы:

1. Должен ли я вообще беспокоиться о Cython для струнных вещей? Кто-нибудь имеет опыт работы с этим типом обработки в cython и может поделиться?
2. Я что-то упустил в документации по Cython? Кто-нибудь знает учебник / справочник / документацию по работе со строками в Cython?

Answer 1

Я проголосовал за ответ 'profile it', но хотел добавить следующее: по возможности лучшая оптимизация, которую вы можете сделать, - это использовать стандартные библиотеки Python или встроенные функции для выполнения нужных вам задач. Как правило, они реализованы на C и обеспечивают производительность, в целом эквивалентную любому расширению, включая расширения, написанные на Cython. Если ваши алгоритмы выполняют посимвольные циклы в Python, то это должно быть первым делом, если это возможно.

Но если у вас есть алгоритмы, которые не могут быть переработаны с точки зрения встроенных или других существующих стандартных библиотек, Cython кажется разумным подходом. Он просто компилирует псевдо-Python до нативного кода и в действительности подходит для строковых операций, как и любая другая операция. Но я не уверен, что использование Cython принесет большую пользу, если вы просто передадите идиоматический код Python. Максимальная выгода будет получена, если вы сможете переписать некоторые или все алгоритмы на C, чтобы операции низкого уровня не переводили переменные постоянно через барьер Python / C.

Наконец, Unicode - вы подразумевали, что это может быть «большой проблемой», но не указали, как вы его используете. Предполагается, что Cython создаст C-код, который вызывает соответствующие API-интерфейсы Python, которые обрабатывают Unicode, поэтому вряд ли функциональность будет ограничена. Однако обработка строк Unicode в C не является тривиальной и может означать, что идея переписать некоторые из ваших алгоритмов в C для лучшей производительности не стоит усилий. Многие классические строковые алгоритмы просто не будут работать на многих кодировках Unicode, которые не являются «строками» в традиционном смысле наличия 1 единицы памяти на символ.

Answer 2

Просто для полноты я просто написал (частично) код для работы со строками в C.

Как оказалось, до смешного легко начать писать расширения c для python. Строки Unicode - это просто массивы Py_UNICODE, который является целым или кратким в зависимости от сборки Python.

Я получил код преобразования x20, например

s = re.sub(r' +', ' ', s)

до ц. Я получил подобные улучшения с более сложными регулярными выражениями, но код c очень быстро становится безумно сложным.

В целом, моя производительность увеличилась на 20% после переписывания. Я сейчас ищу больше вещей, чтобы переписать ...

Answer 3

«Смешно легко» - очень относительный термин. «Начало работы» - это просто. Написание надежных расширений на C требует очень внимательного отношения к таким вещам, как подсчет ссылок, распределение / освобождение памяти и обработка ошибок. Cython делает многое для вас.

Не-юникодная строка в Cython - это либо объект Python str, либо массив char, как в C. Какая документация для Cython, по вашему мнению, вам нужна?

Я рекомендую вам попробовать Cython для себя. НО, прежде чем вы сделаете это, я настоятельно рекомендую вам проверить ваш код Python на предмет неэффективности. Иногда вы можете легко получить большие ускорения.

Например, сжатие пробелов в символах ... с использованием

re.sub(' +', ' ', s) # one space in pattern

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

re.sub('  +', ' ', s) # two spaces in pattern

дает точно такие же результаты и может работать быстрее ... посмотрим:

Длина всех пробегов 1: скорость в 3,4 раза выше. Не показано: чем длиннее строка ввода, тем лучше.

\python26\python -mtimeit -s"s='now is the winter of our discontent'; import re; x = re.compile(' +').sub" "x(' ', s)"
100000 loops, best of 3: 8.26 usec per loop

\python26\python -mtimeit -s"s='now is the winter of our discontent'; import re; x = re.compile('  +').sub" "x(' ', s)"
100000 loops, best of 3: 2.41 usec per loop

В случае одного прогона длиной 2 передаточное число составляет 2,5. Для всех трасс длиной 2 коэффициент скорости равен 1,2. Учитывая все обстоятельства, неплохая окупаемость инвестиций в 1 нажатие клавиши.

Answer 4

Я недавно познакомился с Cython и добился большого успеха, оборачивая большие библиотеки C и C ++ для использования в значимых проектах. Некоторые из сгенерированных расширений Python уже работают в нашей производственной среде. Итак, во-первых, Cython, безусловно, хороший выбор.

При этом вам следует подумать, действительно ли вы хотите написать весь свой код на Cython или хотите писать код на C / C ++ и просто сделать эти функции доступными из Cython. Очевидно, что это будет частично зависеть от вашего уровня комфорта с C и / или C ++.

Поскольку вы работаете со строками, вы, вероятно, могли бы упростить свою жизнь, используя std::string из C ++, а не char*. Он может быть легко импортирован в cython с помощью from libcpp.string cimport string, затем переменные могут быть объявлены с помощью строкового типа через стандартный cython cdef string ...

Answer 5

Это очень интересный вопрос. По своей сути Cython - это инструмент для интеграции Python с типами данных C. Он не предоставляет никаких функций, помогающих работать со строками, возможно потому, что на это не так много спроса, как на конкретные функции Numpy.

Сказав это, вы вполне можете использовать Cython для взаимодействия с существующими библиотеками C / C ++, предназначенными для обработки типов проблем, которые вы описываете. Для обработки HTML / XML вы можете посмотреть libxml , например. Однако (конечно) готовые привязки Python уже доступны для этого. Я широко использовал lxml для обработки HTML, и он делает все, что мне нужно, и делает это быстро , плюс он очень хорошо обрабатывает юникод.

В вашем случае я бы предположил, что комбинация lxml и пользовательских функций C была бы лучшей. Например, вы могли бы «легко» создать быструю функцию для поиска самых длинных подстрок в C, как это можно сделать на уровне байтов (напомним, что строка в C - это просто char *, который является массивом байтов). Затем вы можете отобразить их обратно на python (который Cython сделает для вас очень простым) и продолжить работу на небосклоне абстрагирования от Unicode :). Конечно, это не тривиально, но может стоить усилий, если от этого зависит производительность вашего приложения.

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

Answer 6

Обратите внимание, что Cython фактически поддерживает тип Py_UNICODE CPython, поэтому, например, вы можете напрямую перебирать строки Юникода или сравнивать символы на скорости Си. См

http://docs.cython.org/src/tutorial/strings.html