[plt-scheme] Effect of caching using hash-tables vs vectors

Hi Eli and Jens Axel,
Thanks for your responses. The idea of copying a vector into a larger one is straight forward. But when looking for the maximum cycle for the numbers 1 to 1e7, the size of the vector will grow beyond practical limits. Even when storing the cycles of odd numbers only, computing the maximum cycle for the numbers 1 up to but not including 1e7 would require a vector of length (/ (sub1 20114203639877) 2) = 10057101819938 = about 1e13. I managed to compute this by memorizing the cycles of odd numbers <= 250000001 in a vector and hashing the others (requiring 107176 hash-table entries). The vector gives a hit/lookup rate of about 56%. The hash-table is not very effective, for it provides a hit/lookup rate of about 0.3%. Indeed, without the hash, the computation takes about the same amount of time. It was a nice exercise.
Jos 

(((((lambda(x)((((((((x x)x)x)x)x)x)x)x))
    (lambda(x)(lambda(y)(x(x y)))))
   (lambda(x)(x)x))
  (lambda()(printf "Greetings, Jos~n"))))
  ----- Original Message ----- 
  From: Eli Barzilay 
  To: jos koot 
  Cc: Daniel Yoo ; plt-scheme at list.cs.brown.edu 
  Sent: Sunday, March 18, 2007 10:33 PM
  Subject: Re: [plt-scheme] Effect of caching using hash-tables vs vectors


  On Mar 18, jos koot wrote:
  > Hi Eli,
  > I am interested in how you solved the problem using a vector while
  > not knowing beforehand the maximum number that will be generated
  > while cycling.

  My code does not use vectors...  (But a standard approach is to wrap
  vector access by a layer that copies the vector to one that is twice
  the size whenever a larger index is used.)

  -- 
            ((lambda (x) (x x)) (lambda (x) (x x)))          Eli Barzilay:
                    http://www.barzilay.org/                 Maze is Life!
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20070319/7ead0cc3/attachment.html>