How to read input fast in python and transform into ints
Jan 1, 0001Недавно я решал задачу (UVa 10013 - Super long sums), и там я наткнулся на ситуацию, где нужно было максимально быстро читать входные данные.
Т.е о чем речь? Необходимо читать данные из стандартного потока ввода stdin и конвертировать в int/float или что-то еще.
В C
это делается c помощью стандартной функции scanf()
.
На Python
обычно я делаю так:
import sys
for line in sys.stdin:
a,b = map(int, line.split())
Проблема этого кода в том, что мы очень много раз вызываем функцию int
.
Далее я нашел похожий вопрос/ответ на SO: https://stackoverflow.com/questions/12784192/is-there-a-faster-way-to-get-input-in-python. В том же ответе на SO я нашел интересный трюк, который сильно ускоряет работу с цифрами, при условии, что мы работаем c ascii от 0 до 9.
Итак вместо того, чтобы вызывать функцию int
, давайте попробуем вызывать более быструю функцию ord
со сдвигом 48
,
что позволит нам найти искомое число из строки.
import sys
for line in sys.stdin:
x,y = [ord(x)-48 for x in line.split()]
Короткий бенчмарк:
import timeit
timeit.timeit('ord("1")-48')
# 0.0593524890136905
timeit.timeit('int("1")')
# 0.17183380699134432
=)