Daniel Bastos wrote: > def make_sequence_non_recursive(N, x0 = 2, c = -1): > "What's wrong with this function? It's very slow." > last = x0 > def sequence(): > nonlocal last > next = last > last = last**2 + c > return next % N > return sequence > > It crawls pretty soon. Please advise? Thank you.
Let's change your code a bit to get a feel for the size of the numbers you are dealing with: >>> def make_sequence_non_recursive(N, x0 = 2, c = -1): ... "What's wrong with this function? It's very slow." ... last = x0 ... def sequence(): ... nonlocal last ... next = last ... last = last**2 + c ... return next % N ... def get_last(): return last ... return sequence, get_last ... >>> f, get_last = make_sequence_non_recursive(1032) >>> for i in range(100): print(i, f()) ... 0 2 1 3 2 8 3 63 4 872 5 831 6 152 7 399 8 272 9 711 10 872 11 831 12 152 13 399 14 272 15 711 16 872 17 831 18 152 19 399 20 272 21 711 22 872 23 831 ^CTraceback (most recent call last): File "<stdin>", line 1, in <module> File "<stdin>", line 7, in sequence KeyboardInterrupt >>> x = get_last() I'd rather not show the actual number, but >>> x.bit_length() 12534884 So at this point it alreay would take 1.5 MB to store the number in binary. The actual format requires even a bit more memory: >>> import sys >>> sys.getsizeof(x) 1671344 So for every operation you have to touch a lot of memory -- and that takes time. Now let's apply Ben's modification: >>> f, get_last = make_sequence_non_recursive(1032) >>> for i in range(24): f() ... 2 8 872 152 272 872 152 272 872 152 272 872 152 272 872 152 272 872 152 272 872 152 272 872 >>> get_last().bit_length() 8 OK. I dare to have that one printed: >>> get_last() 152 I did not time it, but in general less memory touched will translate into faster execution. Expect a huge speed-up... -- https://mail.python.org/mailman/listinfo/python-list
