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

Question

Я работаю над проблемой 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() 

Answer 1

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

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

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

Edit:

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

Answer 2

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

Edit: Похоже, модули сторонних не допускается,

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

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

Answer 3

[Отредактировано, чтобы отразить новые данные и проходящее код на SPOJ]

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

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

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

Answer 4

Для других читателей, here is the INTEST problem statement. Он предназначен для тестирования пропускной способности ввода-вывода.

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

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

Answer 5

Совсем недавно 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 причина была в том, что код внутри функции может быть оптимизирован.

Answer 6

Использование списков с помощью 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.