Python3: using generator to process a very large list of integers

Question

This is from a leetcode question I am working on. The problem is the following:

create an algorithm that works in the the following fashion:

arr = [1,3,4,8], queries = [[0,1],[1,2],[0,3],[3,3]]

the output is: [2,7,14,8]

by applying the following series of operations: The XOR values for queries are:

[0,1] = 1 xor 3 = 2

[1,2] = 3 xor 4 = 7

[0,3] = 1 xor 3 xor 4 xor 8 = 14

[3,3] = 8

The input is a very large list for arr and an even longer list for queries. The output has to be a list and I have tried this several ways.

first attempt: (building a gigantic list in memory and returning it using append() )

def XORsubqueries(array, queries):
    result = []
    for pair in queries:
        value = array[pair[0]]
        i = pair[0]
        while i < pair[1]:
            if pair[0] == pair[1]:
                result.append(array[pair[i]] ^ array[pair[i]])
                break
            else:
                i += 1
                value ^= array[i]
        result.append(value)
    return result

As you can imagine this takes FOREVER (53 seconds on my i5 dual core). I then remembered about generator expressions for lazily building values and thought they might come in handy just for this kind of thing.

def XORsubqueries(array, queries):
    
    result = [0] * len(array)
    def XOR(array, queries):     
        for pair in queries:
            value = array[pair[0]]
            i = pair[0]
            while i < pair[1]:
                i += 1
                value ^= array[i]
                yield value
    return list(XOR(array, queries))

If i remove the list off that return statement it figures it out in like 0.0001 seconds ! But I have to return it as a list. Is there a way I can rewrite my algorithm to do what I am trying to do with this generator or did I paint myself into a corner ?

Answer 1

I would guess the biggest slowdowns are the append and list functions. In your second example, you attempt to pre-create a list, which is a good idea, but a) you use the wrong size, and b) you never use the created list. Here's an example using a pre-made list:

def xor_subqueries(array, queries):
    result = [0] * len(queries)
    for i,q in enumerate(queries):
        val = array[q[0]]
        for j in range(q[0]+1, q[1]+1):
            val ^= array[j]
        result[i] = val
    return result

Pretty straight forward. I'm not so sure this task calls for a generator function, but here's an example of using one:

def xor_subqueries(array, queries):
    def genx():
        for q in queries:
            val = array[q[0]]
            for j in range(q[0]+1, q[1]+1):
                val ^= array[j]
            yield val

    result = [0] * len(queries)
    for i,q in enumerate(genx()):
        result[i] = q
    return result

However, I have read that list comprehension is faster. You could easily re-write the above function using list comprehension (return [x for x in genx()]), but here is an example using the built-in functions reduce and xor which stand-in for your generator function.

from functools import reduce
from operator import xor

def xor_subqueries(array, queries):
    return [reduce(xor, array[q[0]:q[1]+1], 0) for q in queries]

It calls reduce on the sub-list array[q[0]:q[1]+1]). reduce calls xor on each element of the sub-list with the previously calculated value and an initial value of 0.

Answer 2

results of benchmarking various solutions from slowest to fastest using timeit():

building a list and appending to it: (52-55 seconds)

def XORsubqueries(array, queries):
result = []
for pair in queries:
    value = array[pair[0]]
    i = pair[0]
    while i < pair[1]:
        if pair[0] == pair[1]:
            result.append(array[pair[i]] ^ array[pair[i]])
            break
        else:
            i += 1
            value ^= array[i]
    result.append(value)
return result   

homespun generator : (49 - 53 seconds) slightly faster using list() incidentally

def XORsubqueries(array, queries):

#result = [0] * len(array)
def XOR(array, queries):     
    for pair in queries:
        value = array[pair[0]]
        i = pair[0]
        while i < pair[1]:
            i += 1
            value ^= array[i]
            yield value

return [x for x in XOR(array, queries)] # 53 seconds
return list(XOR(array, queries)) # 49 seconds

using reduce (thanks @Johnny Mopp ) 13 seconds

from functools import reduce
from operator import xor

def xor_subqueries(array, queries):
    return [reduce(xor, array[q[0]:q[1]+1], 0) for q in queries]

using accumulate (thanks @StefanPochmann from leetcode) holy crap 0.009 seconds !

def xorQueries(self, arr, queries):
    x = [0, *itertools.accumulate(arr, operator.xor)]
    return [x[i] ^ x[j+1] for i, j in queries]

I am curious to know why this last one is SO MUCH faster than the reduce. I am guessing it has to do with using accumulate as an iterator to build the output lazily and then a list comprehension for the output as opposed to building a list comprehension (?)