Performance in Hackerrank challenge "Sherlock and Queries"

I translated the solution by the author to his challenge from C++ to Python. It seems to be correct, but I get timeouts for the test cases 6, 9 and 12.

Here is the full challenge description:

Watson gives to Sherlock an array: $A_1, A_2, ..., A_N$. He also gives to Sherlock two other arrays: $B_1, B_2, ..., B_M$ and $C_1, C_2, ..., C_M$.

Then Watson asks Sherlock to perform the following program:

for i = 1 to M do
for j = 1 to N do
if j % B[i] == 0 then
A[j] = A[j] * C[i]
endif
end do
end do


Can you help Sherlock and tell him the resulting array A? You should print all the array elements modulo $(10^9 + 7)$.

Input Format

The first line contains two integer numbers $N$ and $M$. The next line contains $N$ integers, the elements of array A. The next two lines contains $M$ integers each, the elements of array B and C.

Output Format

Print $N$ integers, the elements of array A after performing the program modulo $(10^9 + 7)$.

Constraints

$1 ≤ N, M ≤ 10^5$
$1 ≤ B[i] ≤ N$
$1 ≤ A[i], C[i] ≤ 10^5$

Sample Input

4 3
1 2 3 4
1 2 3
13 29 71


Sample Output

13 754 2769 1508


And here is my code:

import fileinput
import collections

lines = [[int(x) for x in line.split()] for line in fileinput.input()]
[n, m], a, b, c = lines

def one():
return 1

factors = collections.defaultdict(one)
for i in range(0, m):
factors[b[i]] *= c[i] % 1000000007

for i, factor in factors.iteritems():
for j in range(1, n/i + 1):
idx = j*i-1
a[idx] *= factor
a[idx] %= 1000000007;

print ' '.join(map(str, a))


Any idea on how I could increase the performance of my solution?

This loop can be tuned in some ways:

for i, factor in factors.iteritems():
for j in range(1, n/i + 1):
idx = j*i-1
a[idx] *= factor
a[idx] %= 1000000007;

• Use the third argument of range (step size).
• Use xrange in Python 2.
• The in-place operators may actually slow you down vs. a single expression.

Modified:

for i, factor in factors.iteritems():
for idx in xrange(i-1, n, i):
a[idx] = a[idx] * factor % 1000000007


The fileinput module offers convenience for reading multiple files, but adds some overhead. If you are reading from standard input, use for line in sys.stdin directly.

As noted in comments, the above changes do not make much difference. However, I now found something that actually matters. There is a subtle bug in the translation from C++ to Python here:

factors[b[i]] *= c[i] % 1000000007


Written like this the modulo operator applies to c[i] while it is supposed to apply to the result of the multiplication. The programs still gives the correct result because you apply the modulo in the later loop, but in the meanwhile Python has to multiply much larger numbers. I get a 100-fold speed increase by changing the line to

factors[b[i]] = factors[b[i]] * c[i] % 1000000007

• Thanks, that looks more elegant, but on my machine it does not decrease the runtime (old: 8.112s new: 8.147s) for test case 6 (codepad.org/ufNYxZ3c/raw.txt). And on the hackerrank server it also still times out. Using sys.stdin instead of fileinput also did not help. Sep 16, 2014 at 11:55
• @Dobi That test case file seems to be only three lines. Sep 16, 2014 at 13:46
• Oh, codepad seems to have truncated the data. Here it is again: gist.github.com/Dobiasd/d6de8bf8f7550ae8b5b8 Sep 16, 2014 at 14:11