Python: itertools.product consuming too much resources
Question: I've created a Python script that generates a list of words by permutation of
characters. I'm using `itertools.product` to generate my permutations. My char
list is composed by letters and numbers
**01234567890abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVXYZ**. Here is my
code:

    
    
    #!/usr/bin/python
    import itertools, hashlib, math
    
    class Words:
    
        chars = '01234567890abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVXYZ'
    
        def __init__(self, size):
            self.make(size)
    
        def getLenght(self, size):
            res = []
            for i in range(1, size+1):
                res.append(math.pow(len(self.chars), i))
            return sum(res)
    
        def getMD5(self, text):
            m = hashlib.md5()
            m.update(text.encode('utf-8'))
            return m.hexdigest()
    
        def make(self, size):
            file = open('res.txt', 'w+')
            res = []
            i = 1
            for i in range(1, size+1):
                prod = list(itertools.product(self.chars, repeat=i))
                res = res + prod
            j = 1
            for r in res:
                text = ''.join(r)
                md5 = self.getMD5(text)
                res = text+'\t'+md5
                print(res + ' %.3f%%' % (j/float(self.getLenght(size))*100))
                file.write(res+'\n')
                j = j + 1
            file.close()
    
    Words(3)
    

This script works fine for list of words with max 4 characters. If I try 5 or
6 characters, my computer consumes 100% of CPU, 100% of RAM and freezes.

Is there a way to restrict the use of those resources or optimize this heavy
processing?


Answer: Does this do what you want?

I've made all the changes in the make method:

    
    
    def make(self, size):
    
        with open('res.txt', 'w+') as file_: # file is a builtin function in python 2
            # also, use with statements for files used on only a small block, it handles file closure even if an error is raised.
            for i in range(1, size+1):
                prod = itertools.product(self.chars, repeat=i)
    
                for j, r in enumerate(prod):
                    text = ''.join(r)
                    md5 = self.getMD5(text)
                    res = text+'\t'+md5
                    print(res + ' %.3f%%' % ((j+1)/float(self.get_length(size))*100))
                    file_.write(res+'\n')
    

Be warned this will still chew up gigabytes of memory, but not virtual memory.

EDIT: As noted by Padraic, there is no **file** keyword in Python 3, and as it
is a "bad builtin", it's not too worrying to override it. Still, I'll name it
file_ here.

EDIT2:

To explain why this works so much faster and better than the previous,
original version, you need to know how **lazy** evaluation works.

Say we have a simple expression as follows (for Python 3) (use xrange for
Python 2):

    
    
    a = [i for i in range(1e12)]
    

This immediately evaluates 1 trillion elements into memory, overflowing your
memory.

So we can use a generator to solve this:

    
    
    a = (i for i in range(1e12))
    

Here, none of the values have been evaluated, just given the interpreter
instructions on how to evaluate it. We can then iterate through each item
**one by one** and do work on each separately, so almost nothing is in memory
at a given time (only 1 integer at a time). This makes the seemingly
impossible task very manageable.

The same is true with itertools: it allows you to do memory-efficient, fast
operations by using iterators rather than lists or arrays to do operations.

In your example, you have 62 characters and want to do the cartesian product
with 5 repeats, or 62**5 (nearly a billion elements, or over 30 gigabytes of
ram). This is prohibitively large."

In order to solve this, we can use iterators.

    
    
    chars = '01234567890abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVXYZ'
    for i in itertools.product(chars, repeat=5):
        print(i)
    

Here, only a single item from the cartesian product is in memory at a given
time, meaning it is very memory efficient.

However, if you evaluate the full iterator using list(), it then exhausts the
iterator and adds it to a list, meaning the nearly one billion combinations
are suddenly in memory again. We don't need all the elements in memory at
once: just 1. Which is the power of iterators.

Here are links to the [itertools
module](https://docs.python.org/2/library/itertools.html) and another
explanation on [iterators in Python 2](http://anandology.com/python-practice-
book/iterators.html) (mostly true for 3).

