python - Python Memory Error when generating pairs using itertools.combinations

Question

I have an int list with unspecified number. I would like to find the difference between two integers in the list that match a certain value.

from itertools import combinations

#Example of a list
intList = [3, 6, 2, 7, 1]
diffList = [abs(a -b) for a, b in combinations(intList, 2)]

#Given if difference = 2    
print diffList.count(2)

The code snippet worked but when a larger list is given, I am getting MemoryError. Can anyone tell me if there's something wrong with the codes or the error is due to my hardware limitation?

Answer 1

Exactly how large is "a larger list"? If len(intList) is n, len(diffList) will be n*(n-1)//2 (the number of combinations of n things taken 2 at a time). This will consume all your memory if n is large enough.

If you only care about the value 2,

print sum(abs(a-b) == 2 for a, b in combinations(intList, 2))

is one way to do it that consumes very little memory regardless of how large intList is. However, it will still take time proportional to the square of len(intList).

Answer 2

You can solve your problem using this code:

result = 0
for a, b in combinations(intList, 2):
    if abs(a - b) == 2:
        result += 1
print result

So your problem is not just your hardware limitations, it's your hardware limitations and bad code.

Answer 3

You created a list with a list comprehension, then called its count method. Instead, just create an iterator with a generator expression, then call an icount function that takes any iterable:

diffs = (abs(a -b) for a, b in combinations(intList, 2))
print icount(diffs, 2)

It's nearly identical to your original code, but it doesn't use any extra memory.

---

Of course that icount function doesn't exist, but you should be able to write it yourself.

def icount(iterable, value):
    result = 0
    for element in iterable:
        if element == value:
            result += 1
    return result

… or …</p>

def ilen(iterable):
    return sum(1 for _ in iterable)
def icount(iterable, value):
    filtered = (elem for elem in iterable if elem == value)
    return ilen(filtered)

… or …</p>

def icount(iterable, value):
    return sum(elem == value for elem in iterable)

… or (using itertools recipes) …</p>

def icount(iterable, value):
    return quantify(iterable, lambda elem: elem == value)

---

If you want, you can merge the expression into the icount function and do it all in one line, and then you have exactly Tim Peters' answer.