Быстрое преобразование строки в целое в Python

Question

Действительно простая проблема: у вас есть один миллиард (1e + 9) 32-разрядных целых чисел без знака, которые хранятся в виде десятичных строк ASCII в файле TSV (значения, разделенные табуляцией). Преобразование с использованием int() ужасно медленное по сравнению с другими инструментами, работающими с тем же набором данных. Зачем? И что еще важнее: как сделать это быстрее?

Поэтому вопрос: какой самый быстрый способ преобразовать строку в целое число в Python?

То, о чем я на самом деле думаю, - это некоторая полузакрытая функциональность Python, которая (ab) может использоваться для этой цели, мало чем отличается от использования Гвидо array.array в его «Оптимизационном анекдоте» .

Пример данных (с расширенными до пробелов табуляциями)

38262904        "pfv"              2002-11-15T00:37:20+00:00
12311231        "tnealzref"        2008-01-21T20:46:51+00:00
26783384        "hayb"             2004-02-14T20:43:45+00:00
812874          "qevzasdfvnp"      2005-01-11T00:29:46+00:00
22312733        "bdumtddyasb"      2009-01-17T20:41:04+00:00

Время, затрачиваемое на чтение данных, здесь неактуально, обработка данных является узким местом.

Microbenchmarks

Все перечисленные ниже языки являются интерпретированными. На хосте установлена ​​64-битная версия Linux.

Python 2.6.2 с IPython 0.9.1, ~ 214 тыс. Преобразований в секунду (100%):

In [1]: strings = map(str, range(int(1e7)))

In [2]: %timeit map(int, strings);
10 loops, best of 3: 4.68 s per loop

REBOL 3.0 Версия 2.100.76.4.2, ~ 231 кбит / с (108%):

>> strings: array n: to-integer 1e7 repeat i n [poke strings i mold (i - 1)]
== "9999999"

>> delta-time [map str strings [to integer! str]]
== 0:00:04.328675

REBOL 2.7.6.4.2 (15 марта 2008 г.), ~ 523 кбит / с (261%):

Как отметил Джон в комментариях, эта версия не создает список преобразованных целых чисел, поэтому приведенное соотношение скоростей относительно времени выполнения Python 4,99 for str in strings: int(str).

>> delta-time: func [c /local t] [t: now/time/precise do c now/time/precise - t]

>> strings: array n: to-integer 1e7 repeat i n [poke strings i mold (i - 1)]
== "9999999"

>> delta-time [foreach str strings [to integer! str]]
== 0:00:01.913193

KDB + 2,6 т 2009.04.15, ~ 2016 кбит / с (944%):

q)strings:string til "i"$1e7

q)\t "I"$strings
496

Answer 1

Следующее наиболее упрощенное расширение C уже значительно улучшено во встроенной системе, способное преобразовывать в три раза больше строк в секунду (650kcps против 214kcps):

static PyObject *fastint_int(PyObject *self, PyObject *args) {
    char *s; unsigned r = 0;
    if (!PyArg_ParseTuple(args, "s", &s)) return NULL;
    for (r = 0; *s; r = r * 10 + *s++ - '0');
    return Py_BuildValue("i", r);
}

Это, очевидно, не учитывает целые числа произвольной длины и различные другие особые случаи, но в нашем сценарии это не проблема.

Answer 2

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

Вам действительно нужны все миллиарды чисел в памяти всегда. Подумайте об использовании некоторых итераторов, чтобы получить только несколько значений за раз. Миллиард чисел займет немного памяти. Добавление их в список по одному потребует нескольких больших перераспределений.

Получите ваш цикл из Python полностью, если это возможно. Функция карты здесь может быть вашим другом. Я не уверен, как хранятся ваши данные. Если это одно число в строке, вы можете уменьшить код до

values = map(int, open("numberfile.txt"))

Если в строке есть несколько значений, разделенных пробелами, покопайтесь в itertools, чтобы не допустить циклический код из Python. Эта версия имеет дополнительное преимущество, заключающееся в создании числового итератора, так что вы можете помещать в файл только одно или несколько чисел за раз вместо одного миллиарда за один раз.

numfile = open("numberfile.txt")
valIter = itertools.imap(int, itertools.chain(itertools.imap(str.split, numfile)))

Answer 3

Могу предположить, что для чистой скорости Python не является подходящим инструментом для этой задачи. Реализация на C, написанная вручную, легко победит Python.

Answer 4

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

Вы можете прочитать больше о Cython и посмотреть, поможет ли это.

Еще один вопрос, который приходит на ум ... что вы собираетесь делать с этими миллиардами целых чисел? Возможно ли, что вы можете загружать их как строки, искать их как строки и выполнять ленивое преобразование по мере необходимости? Или вы могли бы распараллелить преобразование и другие вычисления, используя threading или multiprocessing модули и очереди? (Иметь один или несколько потоков / процессов, выполняющих преобразование и передающих в очередь, из которой ваш процессор обрабатывает их). Другими словами, дизайн производителя / потребителя облегчит проблему?

Answer 5

Согласен с Грегом; Python как интерпретируемый язык, как правило, медленный. Вы можете попробовать скомпилировать исходный код на лету с помощью библиотеки Psyco или написать приложение на языке более низкого уровня, таком как C / C ++.

Answer 6

Это то, что numpy делает очень хорошо:

np.fromstring (строка, dtype = np.float, sep = "")

Answer 7

Возможно, это не вариант для вас, но я бы очень старался использовать бинарный файл, а не текстовый. Это часто меняется? Если нет, вы можете предварительно обработать его.