On 02/10/2017 14:54, Peter Otten wrote:
bartc wrote:
On 02/10/2017 08:41, Peter Otten wrote:
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
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.
If it recalculates 'last' once for each of those couple of dozen printed
lines, that I doubt accessing a few MB of memory is the issue. More
doing such a big calculation.
You are probably right that the calculation requires a significant amount of
the total time here, but it's not just "a few MB". If you look at
last = last**2 + c
the required memory doubles on every iteration. You will soon run into the
problem even under the (overly optimistic) assumption that the calculation
requires time proportional to memory.
On my machine, the iterations whizzed up the screen until I noticed it
pausing on the 21st iteration, when the memory size of last was 0.5MB.
When I started last as "A", and multiplied by 2 at each step, it started
to pause at the 27th iteration when the size of last was 268MB.
I would estimate then another 9 steps of the original (30th iteration)
before memory usage has the same effect. Although it would probably
already have ground to a halt long before then.
--
bartc
--
https://mail.python.org/mailman/listinfo/python-list
