deque vs list: performance notes

[Remco Gerlich]

Michael Hudson wrote in comp.lang.python:
> david_ullrich at my-deja.com writes:
> 
> >      You sure about that "n!"? Seems more like n^2 to me.
> > (Of course n^2 is big, but n! would be much worse. It's
> > a theorem that n! is bigger than anything.)
> 
> n^n is worse than n!, if you're after really bad algorithmic
> performance.

There exists some mathematical proof, by Ronald L. Graham, about an upper
bound to a certain question of Ramsey theory (I don't know more about this,
this is from some web page I saved once). It uses a rather large number.

Really large numbers come in Knuth notation, like 3^3 or 3^^7 or 7^^^4.
Defined by the following Python function:

def knuth(num, power, arrownum):
   if not arrownum:
      return num*power
   answer = num
   for i in range(power-1):
      answer = knuth(num, answer, arrownum - 1)
   return answer
   
So 2^4 = 2 ** 4 = 16.

3^^4 = 3^(3^(3^3))

7^^^3 = 7^^(7^^7)

3^3 = 3*3*3 = 27. Easy.

3^^3 = 3^(3^3) = 3^27 = 7,625,597,484,987. "So small I can actually type it".
Still a number you can visualize somewhat, ie the gross national product.

3^^^3 = 3^^(3^^3) = 3^3^3^3^3^3^3^3^3^.....^3^3 (7 trillion threes).
Too big to understand. After the first few terms you're already far above
small numbers like the number of particles in the universe. But at least you
can store that expression (3^3^3^3...) in eight terabytes of memory.

3^^^^3 = 3^^^(3^^^3) = 3^^(3^^(3^^(3^^..... (repeat by the amount of the
previous number...)))).
There are no words for this number.


To get Graham's number, you take x = 3^^^^3. Next, you set x to 3^^^...(x
^'s)...^^^3. Repeat 63 times.

x = 4
for i in range(64):
   x = knuth(3,3,x)


Now *that's* a large number.


Of course, most finite numbers are much larger than that ;-).



i-know-no-algorithm-that's-this-bad-but-i-wanted-a-silly-math-post-ly-y'rs,
Remco
-- 
Remco Gerlich,  scarblac at pino.selwerd.nl
  Murphy's Rules, "Does Dr. McCoy know?":
   FASA's Star Trek: The Role-Playing Game describes the Klingon Agonizer
   as hand-held device 'applied to the left shoulder just above where the
   ear is located in humans.'