Python3: using generator to process a very large list of integers 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 &lt; 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 &lt; 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 ?
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.