Как получить ДЕЙСТВИТЕЛЬНО быстрый Python через простой цикл

Я работаю над проблемой SPOJ, INTEST. Цель состоит в том, чтобы указать количество тестовых случаев (n) и делителя (k), а затем подать ваши n номера программ. Программа будет принимать каждое число в новой строке stdin и после получения n-го числа сообщит вам, сколько из них было делимым на k.

Единственная проблема в этой проблеме - заставить ваш код быть FAST, потому что k может быть любым размером до 10 ^ 7 и n может достигать 10 ^ 9.

Я пытаюсь написать его на Python и не могу ускорить его. Любые идеи?

Отредактируйте 2: я, наконец, получил это, чтобы пройти через 10.54 секунды. Я использовал почти все ваши ответы, чтобы добраться туда, и поэтому было трудно выбрать один из них как "правильный", но я считаю, что тот, который я выбрал, суммирует его как можно лучше. Спасибо вам всем. Конечный код прохождения ниже.

Изменить: я включил некоторые предлагаемые обновления во включенном коде.

Расширения и сторонние модули запрещены. Код также управляется судовой машиной SPOJ, поэтому у меня нет возможности сменить интерпретаторы.

import sys
import psyco
psyco.full()

def main():
    from sys import stdin, stdout
    first_in = stdin.readline()
    thing = first_in.split()
    n = int(thing[0])
    k = int(thing[1])
    total = 0

    list = stdin.readlines()
    for item in list:
        if int(item) % k == 0:
            total += 1

    stdout.write(str(total) + "\n")

if __name__ == "__main__":
    main()

Ответы

Ответ 1

Эй, мне нужно, чтобы это было в пределах срока. Я использовал следующее:

  • Psyco с Python 2.5.
  • простой цикл с переменной для учета в
  • мой код был в main() (кроме импорта psyco), который я вызывал.

Последнее, что изменило ситуацию. Я считаю, что это связано с переменной видимостью, но я не совсем уверен. Мое время было 10,81 секунды. Вы можете получить его быстрее со списком.

Edit:

Использование понимания списка привело мое время до 8,23 секунды. Приведение строки from sys import stdin, stdout внутри функции немного сбрито, чтобы сократить время до 8.12 секунд.

Ответ 2

[Отредактировано для отражения новых результатов и передачи кода на spoj]

Как правило, при использовании Python для spoj:

  • Не используйте "raw_input", используйте sys.stdin.readlines(). Это может повлиять на большой вход. Кроме того, если это возможно (и это для этой проблемы), прочитайте все сразу (sys.stdin. Readlines()) вместо чтения строки за строкой ( "для строки в sys.stdin..." ).
  • Аналогично, не используйте "print", используйте sys.stdout.write() - и не забывайте "\n". Конечно, это актуально только при печати несколько раз.
  • Как предложил С.Марк, используйте psyco. Он доступен как для python2.5, так и для python2.6, на spoj (протестировать его, там и легко заметить: решения, использующие psyco, обычно имеют смещение использования памяти 35 Мб). Это очень просто: просто добавьте после "import sys": import psyco; psyco.full()
  • Как предложил Джастин, добавьте свой код (кроме заклинания psyco) внутри функции и просто вызовите его в конце вашего кода.
  • Иногда создание списка и проверка его длины может быть быстрее, чем создание списка и добавление его компонентов.
  • Используйте списки списков (и, если возможно, выражения генератора) над "для" и "пока". Для некоторых конструкций map/reduce/filter также может ускорить ваш код.

Используя (некоторые) эти рекомендации, мне удалось передать INTEST. Тем не менее, альтернативы тестирования.

Ответ 3

Используйте psyco, это будет JIT ваш код, очень эффективный, когда есть большой цикл и вычисления.

Изменить. Похоже, что сторонние модули не разрешены,

Итак, вы можете попробовать преобразовать свой цикл в список понятий, он должен быть запущен на уровне C, поэтому он должен быть немного быстрее.

sum(1 if int(line) % k == 0 else 0 for line in sys.stdin)

Ответ 4

Совсем недавно Alex Martinelli сказал, что вызов кода внутри функции превосходит прогон кода в модуле (я не могу найти сообщение, хотя)

Итак, почему бы вам не попробовать:

import sys
import psyco

psyco.full1()

def main():

    first_in = raw_input()
    thing = first_in.split()
    n = int(thing[0])
    k = int(thing[1])
    total = 0
    i = 0

    total = sum(1 if int(line) % k == 0 else 0 for line in sys.stdin)

    print total
if __name__ == "__main__":
    main()

IIRC причина в том, что код внутри функции может быть оптимизирован.

Ответ 5

Использование списков с помощью psyco является результативным.

Этот код:

 count = 0
 for l in sys.stdin:
     count += not int(l)%k

выполняется в два раза быстрее, чем

count = sum(not int(l)%k for l in sys.stdin)

при использовании psyco.

Ответ 6

Для других читателей вот инструкция задачи INTEST. Он предназначен для проверки пропускной способности ввода-вывода.

В моей системе я смог сэкономить 15% от времени выполнения, заменив цикл следующим:

print sum(1 for line in sys.stdin if int(line) % k == 0)