Welcome, guest | Sign In | My Account | Store | Cart

This is an example of how functional ideas of infinite lists can be used in python to optimize memory usage of certain problems.

Python, 68 lines
 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68``` ```from itertools import * from collections import deque # First a naive approach. At each generation we pop the first element and append # it to the back. This is highly memmory deficient. def rotations(it): """ rotations([0,1,2]) --> [[0, 1, 2], [1, 2, 0], [2, 0, 1]] """ l = list(it) for i in range(len(l)): yield iter(l) l = l[1:]+[l[0]] # A much better approach would seam to be using a deque, which rotates in O(1), # However this does have the negative effect, that generating the next rotation # before the current has been iterated through, will result in a RuntimeError # because the deque has mutated during iteration. def rotations(it): """ rotations([0,1,2]) --> [[0, 1, 2], [1, 2, 0], [2, 0, 1]] """ l = deque(it) for i in range(len(l)): yield iter(l) l.rotate() # The trick is to use subsets of infinite lists. First we define the function tails, # which is standard in many functal languages. # Because of the way tee is implemented in itertools, the below implementation will # use memory only propertional to the offset difference between the generated # iterators. def tails(it): """ tails([1,2,3,4,5]) --> [[1,2,3,4,5], [2,3,4,5], [3,4,5], [4,5], [5], []] """ while True: tail, it = tee(it) yield tail next(it) # We can now define two new rotations functions. # The first one is very similar to the above, but since we never keep all list # elements, we need an extra length parameter. def rotations(it, N): """ rotations([0,1,2]) --> [[0, 1, 2], [1, 2, 0], [2, 0, 1]] """ return (islice(rot,N) for rot in islice(tails(cycle(it)),N)) # The above works fine for things like: # >>> for rot in rotations(range(4), 4): # ... print (list(rot)) # ... # [0, 1, 2, 3] # [1, 2, 3, 0] # [2, 3, 0, 1] # [3, 0, 1, 2] # # But that is not really where it shines, since the lists are iterated one after # another, and so the tails memory usage becomes linear. # # In many cases tails and infinite lists lets us get away with an even simpler # rotaions function: def rotations(it, N): """ rotations([0,1,2]) --> [[0, 1, 2], [1, 2, 0], [2, 0, 1]] """ return islice(tails(cycle(it)),N) # This one works great for instances where we are topcut anyway: # >>> for rot in rotations(range(4), 4): # ... print (list(zip(range(4), rot))) # ... # [(0, 0), (1, 1), (2, 2), (3, 3)] # [(0, 1), (1, 2), (2, 3), (3, 0)] # [(0, 2), (1, 3), (2, 0), (3, 1)] # [(0, 3), (1, 0), (2, 1), (3, 2)] ```

In particular the above suggests an optimized tails function to be placed in the itertools library.

 Created by Thomas Ahle on Sun, 13 Feb 2011 (GPL3)