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

 From: jos koot (jos.koot at telefonica.net) Date: Mon Mar 19 06:56:34 EDT 2007 Previous message: [plt-scheme] Effect of caching using hash-tables vs vectors Next message: [plt-scheme] Effect of caching using hash-tables vs vectors Messages sorted by: [date] [thread] [subject] [author]

```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...