-3

I'm working through a programming challenge involving quick processing and large data. I'm trying to generate a list of possible permutations of a number range and then search through them.

Code:

def generate_list(numA, numB):
    combo = list(range(0, numB))
    permutation_list = list(itertools.permutations(combo, numA))
    print("initial dictionary length: " + len(permutation_list))

The problem is that when A is 6 and B is 25, my program slows down immensely and takes up a huge amount of RAM. It peeked at around 13 gigs. The length of the listis around 127 mil and each object is of length 6. That should put the usage at around 750 megs of memory, not 13 gigs. What's going on?

Edit: The data is just numbers. So [[0,1,2,3,4,5],[0,1,2,3,4,6],...]

7
  • Which challenge is it? Any way to access the description and the data?
    – ppasler
    Jan 10, 2017 at 13:09
  • The data is just numbers. So [[0,1,2,3,4,5],[0,1,2,3,4,6],...]
    – Smipims
    Jan 10, 2017 at 13:13
  • I made an error. I meant list wherever I typed dictionary
    – Smipims
    Jan 10, 2017 at 13:14
  • I would guess the challenge here is to avoid creation of so many objects in the first place - you should rethink an exhaustive creation of your permutations.
    – jeremycg
    Jan 10, 2017 at 13:15
  • Is there a way to add a filter to the permutations function or would it likely just be easier to rewrite the function?
    – Smipims
    Jan 10, 2017 at 13:16

2 Answers 2

2

Each element of a list or a tuple is a pointer. And has a size of either 4 or 8 bytes. The following assumes the latter. Just counting the pointers in the list and tuples accounts for half of the space used. The rest is likely the object header which is about 48 bytes. This yields the formula:

(48+8+(8*6)) * 127000000 == 13208000000 

which is about your 13 gigabytes.

I would suggest doing anything possible to avoid generating that complete permutation.

1
  • Thank you! I figured I had to do it another way, but it's always good to know why I was failing, not just that I failed.
    – Smipims
    Jan 10, 2017 at 13:37
-1

An example of how you might output the entire list of permutations might be as follows:

import itertools

def combo(b):
    for combination in range(0, b):
        yield combination

def generate_list(numA, numB):
    for l in itertools.permutations(combo(numB), numA):
        yield list(l), len(l)

if __name__ == '__main__':
    total_length = int()
    with open('permutations', 'w+') as f:
        f.write('[')
        for permutation in generate_list(6, 25):
            data, length = permutation
            total_length += length
            f.write(str(data) + ', ')
        f.write(']\n')
    print("initial dictionary length: " + str(total_length))

I've turned your code into two separate generators. One that gives the combination, another that gives the permutation.

You can calculate the entire thing without a MemoryError and write them to a file. A very large file. Or you could just print it to stdout, up to you.

It will also tell you the length at the end, without requiring massive amounts of memory to do so.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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