Python-сообщество

Возможно ли ускорить работу программы, чтобы уложиться в ограничение по времени 2 с, пользуясь только стандартной либой Python'а?

import sys
#sys.stdin, sys.stdout = open("aplusb.in", "r"), open("aplusb.out", "w")
MOD = 10**9+7
#c = map(int, raw_input())[::-1]
c = [9]*10000
n = len(c)
s = [[[[0 for p in xrange(2)] for j in xrange(10)] for i in xrange(10)] for k in xrange(n)]
for i in xrange(c[0]+1):
    s[0][i][c[0]-i][0] = 1
for i in xrange(c[0]+1, 10):
    s[0][i][10+c[0]-i][1] = 1
def f1():
    return sum([
        s[k-1][x][y][0] \
        for x in xrange(10) if x != i \
        for y in xrange(10) if y != j \
        if s[k-1][x][y][0]])%MOD
def f2():
    return sum([
        s[k-1][x][y][1] \
        for x in xrange(10) if x != i \
        for y in xrange(10) if y != j \
        if s[k-1][x][y][1]])%MOD
for k in xrange(1, n):
    for i in xrange(10):
        for j in xrange(10):
            for p in xrange(2):
                s[k][i][j][p] = f1() if i+j == 10*p+c[k] else \
                                f2() if i+j == 10*p+c[k]-1 else 0
print sum([s[n-1][i][j][0] for i in xrange(1, 10) for j in xrange(1, 10) if s[n-1][i][j][0]])%MOD

насчет 2 сек врядли, но ради спортивного интереса, попробуй списки заменить массивами

а почему сторонние модули нельзя?

для таких задач numpy вроде в самый раз

bismigalis
а почему сторонние модули нельзя?для таких задач numpy вроде в самый раз

In : %%timeit
…: for i in xrange(10000):
…: for j in xrange(10):
…: for k in xrange(10):
…: for p in xrange(2):
…: pass
…:
1 loops, best of 3: 2.05 s per loop

In : r10000, r10, r2 = range(10000), range(10), range(2)

In : %%timeit
…: for i in r10000:
…: for j in r10:
…: for k in r10:
…: for p in r2:
…: pass
…:
1 loops, best of 3: 777 ms per loop

Отредактировано Arsegg (Июль 31, 2013 17:59:07)

могу только предложить использовать один массив и вычислять смещение

from array import array
d1 = 2
d2 = 10 * d1
d3 = 10 * d2
a = array("I", [0]*d3*10000)
k = 9999
i = 9
j = 9
p = 1
a[k*d3 + i*d2 + j*d1 + p] = 1
print a

Arsegg
Вообще ужас! Пустой цикл 2 секунды…

У меня ваши циклы за 0,3 сек отрабатывают, вы случайно не в режиме дебага запускаете?

$ cat 1.py 
for i in xrange(10000):
  for j in xrange(10):
    for k in xrange(10):
      for p in xrange(2):
        pass

$ time python 1.py 
real    0m0.358s
user    0m0.356s
sys     0m0.000s

Arsegg
36(!) с лишним секунд

Отредактировано bismigalis (Авг. 1, 2013 13:51:07)

Arsegg насчет одного массива я прогнал.
я не до конца с твоим алгоритмом разобрался, мне кажется можно сделать такие оптимизации(только из спортивного интереса, ибо на питоне такие числодробления не делаются)

основная единица вычислений у тебя матрица 10x10, её можно заменить на массив из 100 элементов, их вложить в список по два, потом в список по 10000. т.е начало будет таким

import sys
from array import array
MOD = 10**9+7
c = [9]*10000
n = len(c)
a = array("f", [0]*100)
s = [[a for p in xrange(2)]
        for k in xrange(n)]
for i in xrange(c[0]+1):
    s[0][0][i*10 + (c[0]-i)] = 1
for i in xrange(c[0]+1, 10):
    s[0][1][i*10 + (10+c[0]-i)] = 1

Arsegg
Поэтому дело не в алгоритме, а в чем-то другом…

Отредактировано bismigalis (Авг. 2, 2013 11:04:15)

Arsegg
Списки чуть быстрее генераторов, но этого недостаточно

Отредактировано bismigalis (Авг. 2, 2013 11:03:42)