itertools and amazing speed

[Pedroski55]

From the thread about getting random sets of image names we had 24 image names:

images = ['im1', 'im2', 'im3', 'im4', 'im5', 'im6', 'im7', 'im8',
'im9', 'im10', 'im11', 'im12', 'im13', 'im14', 'im15',
'im16', 'im17', 'im18','im19','im20','im21','im22','im23','im24']

Something funny is going on with itertools:

If I do this:

perm_set = itertools.permutations(images,9)

This completes in the time it takes to press and release the enter key.

There are n!/(n-r)! permutations for any given n and r.

Set n = 24, r = 9, we have 24!/15! = 474 467 051 520 permutations.

Has my computer really created nearly 500 trillion 9-string tuples in milliseconds? Seems unlikely!

I don't know what goes on behind the scenes in Python, I believe a lot of modules are written in C, but that still seems extremely fast!

My laptop is fast with 2 Ryzen R7 processors, but that beggars belief!

Has it really made 500 trillion tuples? Has itertools created a generator and nothing else??

[ndc85430]

Yes, per the documentation for the module, the functions return iterators.

[deanhystad]

perm_set is a permutations object, a generator like object that creates results on demand. To see how long this takes you could ask for a list. I doubt you have enough memory.

perm_set = list(itertools.permutations(images,9))

That an itertools.permutations object is a generator is mentioned in the documentation when they say permutations is "roughly equivalent to"

def permutations(iterable, r=None):
    # permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC
    # permutations(range(3)) --> 012 021 102 120 201 210
    pool = tuple(iterable)
    n = len(pool)
    r = n if r is None else r
    if r > n:
        return
    indices = list(range(n))
    cycles = list(range(n, n-r, -1))
    yield tuple(pool[i] for i in indices[:r])  # <------ The first tuple.
    while n:
        for i in reversed(range(r)):
            cycles[i] -= 1
            if cycles[i] == 0:
                indices[i:] = indices[i+1:] + indices[i:i+1]
                cycles[i] = n - i
            else:
                j = cycles[i]
                indices[i], indices[-j] = indices[-j], indices[i]
                yield tuple(pool[i] for i in indices[:r])   # <------ More tuples
                break
        else:
            return

[Pedroski55]

Thanks!

I didn't try to make a list of itertools.permutations(images,9), but I did run:

for i in perm_set:
    print(i)

After I'd had breakfast it still hadn't finished, so I did ctrl + c. I hadn't looked at how many permutations 9 from 24 gives!

So how much memory will an iterator or generator object like that occupy, can you give an indication?

@dean Thanks for the function. It will take me a while to digest!

[bowlofred]

So how much memory will an iterator or generator object like that occupy, can you give an indication?

The generator is code. Each time it is called, it runs code to create the next item. So it only needs enough memory to maintain the state where it needs to pick up the next time.

Unless you're storing all the output somewhere, this doesn't create any memory pressure. Previously calculated items are discarded.

Attempting to store all the output items in a list or similar (like myperms = list(perm_set)) is going to take a huge amount of memory.

[Pedroski55]

The number of permutations of 9 from 24 is enormous, but the number of combinations is much less. As a list, it is < 12MB.

com_set = itertools.combinations(images, 9)
# creates a list of tuples
mylist = list(com_set)
len(mylist) # 1307504
print(sys.getsizeof(mylist))

Output:
>>> type(com_set)
<class 'itertools.combinations'>
>>> print(sys.getsizeof(com_set))
144
>>> 

What I'm wondering is however:

Is there some way to interfere with the value of the next pointer in the class com_set?

Some way to pass it a random number as the stored value?

[Gribouillis]

Is there some way to interfere with the value of the next pointer in the class com_set?

This is a slightly different problem, but I implemented a Combinations class with random access, which allows to access directly the n-th element of the sequence, even with very large numbers. I wonder why this feature is not included in itertools.combinations()

[Pedroski55]

Impressive!

Thanks a lot, hope you don't mind me copying it.

I can't say I understand it yet, but I'll look at it until I do!

[Gribouillis]

Thanks a lot, hope you don't mind me copying it.

I added the MIT License, so that you can freely copy it and modify it.