6
\$\begingroup\$

In preparing a solution for the CodeChef "Will India Win" challenge, I am trying to find out the xor of list of numbers.

The first line of input contains the number of test cases, 1 ≤ T ≤ 106.
Subsequent lines contain fifteen space-delimited numbers (each between 1 and 231), to be XORed together.

def main():
    t = int(raw_input())
    for i in range(t):

        input_list = [int(j) for j in raw_input().split()]
        res = input_list[0]
        for n in range(len(input_list)-1):
            res = res^input_list[n+1]
        print res



if __name__ == '__main__':
    main()

Here is my second code by implementing a 2D array through a dictionary:

def main():
    t = int(raw_input())
    for i in range(t):
        input_str = [ int(j) for j in raw_input().split()]
        d = {}
        for j in range(15):
            d[j] = bin(input_str[j])[2:].zfill(32)

        l = []#contains the final output
        for j in range(32):
            temp = 0
            for k in range(15):
                if d[k][j] == '1':
                    temp += 1

            if temp%2 == 0:
                l.append(0)
            else:
                l.append(1)
if  __name__ == '__main__':
    name()

But it turns out that both code are not optimal because I am getting time constraint problems. How can I optimize the code?

\$\endgroup\$
  • \$\begingroup\$ What do you mean by "in binary format"? \$\endgroup\$ – 200_success Jan 26 '15 at 17:32
  • \$\begingroup\$ Could you say more about the time constraints? How long is your input list, what is the desired running time, and how long do these solutions take? \$\endgroup\$ – 200_success Jan 26 '15 at 17:33
  • \$\begingroup\$ my input constraint is 32 bit input ... so binary I meant 1 - '00000000000000000000000000000001' \$\endgroup\$ – lazarus Jan 26 '15 at 17:36
  • \$\begingroup\$ I still don't understand. Could you edit the question to include a concrete example of what the input and output should look like? \$\endgroup\$ – 200_success Jan 26 '15 at 17:38
  • 1
    \$\begingroup\$ It's a horribly written challenge. "In binary format" is contradicted by the example input, which shows decimal numbers. Jercy [sic] numbers up to 2^31 are also not realistic. \$\endgroup\$ – 200_success Jan 26 '15 at 23:42
6
\$\begingroup\$

As the input size is 10**6 and you're using Python 2 the first issue in that you're creating an unnecessary list of 10**6 integers just to do a loop.

Instead of that you should use xrange() which yields integers lazily:

>>> %timeit for _ in range(10**6): pass
10 loops, best of 3: 24.1 ms per loop
>>> %timeit for _ in xrange(10**6): pass
f100 loops, best of 3: 8.92 ms per loop

Another slight micro-optimization that you can do here is to use itertools.repeat with None. None is a singleton, so, only a single None ever exists in memory and it is the smallest object in CPython on the other hand creating 10**6 integers is expensive(well CPython caches some of them, but still they are unnecessary here)

>>> %timeit for _ in repeat(None, 10**6): pass
100 loops, best of 3: 7 ms per loop

As we're using the functions like raw_input, int multiple times in our code it's better to cache them as local variables, because otherwise we're looking for them at least 10**6 times in global dictionary. One way to cache them is to use them as default values to function attributes:

>>> def f_simple(n):
    for _ in xrange(n):
        foo = [int('1') for _ in xrange(15)]
...         
>>> def f_cached(n, int=int):
    for _ in xrange(n):
        foo = [int('1') for _ in xrange(15)]
...         
>>> %timeit f_simple(10**6)
1 loops, best of 3: 3.7 s per loop
>>> %timeit f_cached(10**6)
1 loops, best of 3: 3.52 s per loop

Instead of starting the result value with input_list[0] we can simply start with 0 and we can also prevent creation of that simple 15 items list:

result = 0
for x in raw_input().split():
    result ^= int(x)

Currently your first solution takes around 7.44 seconds on my system and my solution takes around 5.6 seconds, not a huge improvement.:

from itertools import islice
from functools import partial
import sys

def main5(int=int):
    t = int(raw_input())
    # Take a slice of sys.stdin of size (10**6)*2
    lines = islice(sys.stdin, t*2)
    # Now lines is an iterator which is going to yield one
    # line at a time, but we're also going to read the next line(to get X)
    # with each input, so instead of doing `next(lines)` each time in
    # the loop we can create a partial function. 
    next_line = partial(next, lines)

    for line in lines:
        result = 0
        for x in line.split():
            result ^= int(x)
        if format(result, 'b').zfill(32).count('1') > int(next_line()):
            print 'YES'
        else:
            print 'NO'

Note that in the above solution we are writing to the stdout instantly, if we can store the output temporarily in a list(say 1000 items) and them write them at once then the above solution takes 5.52 seconds:

from itertools import islice
from functools import partial
import sys

def main6(int=int, len=len):
    t = int(raw_input())
    # store a reference sys.stdout.write to prevent 2 attribute lookups
    stdout_write = sys.stdout.write
    lines = islice(sys.stdin, t*2)
    next_line = partial(next, lines)
    out = []
    # Cache out.append to prevent attribute lookup
    out_append = out.append
    for line in lines:
        result = 0
        for x in line.split():
            result ^= int(x)
        if format(result, 'b').zfill(32).count('1') > int(next_line()):
            result = 'YES'
        else:
            result = 'NO'

        out_append(result)
        if len(out) == 1000:
            stdout_write('\n'.join(out))
            # empty out list; use list.clear() in Python 3
            del out[:]
    if out:
        stdout_write('\n'.join(out))
\$\endgroup\$
  • \$\begingroup\$ You can skip the zfill because only 1's count. \$\endgroup\$ – Janne Karila Jan 27 '15 at 6:25
  • \$\begingroup\$ Doesn't partial actually slow things down by wrapping the function call behind another function call, cf. Python functools partial efficiency? \$\endgroup\$ – Janne Karila Jan 27 '15 at 6:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.