[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.ruby

Memoization, files and Marshal?

Daniel Berger

1/1/2006 12:22:00 AM

Hi all,

Inspired by a recent blog entry by Mauricio Fernandez, I decided to try
to add a method to the memoize package that would allow users to
memoize using a file based approach rather than memory, either to
conserve memory or for persistance.

However, I'm not sure it's possible. If it is, I'd love to know how.
If it's not, well, pstore it is.

Here's what I tried:

def memoize_to_file(name, file)
meth = method(name)
cache = Hash.new.update(Marshal.load(File.read(file))) rescue nil
cache ||= {}
(class << self; self; end).class_eval do
define_method(name) do |*args|
if cache.has_key?(args)
cache[args]
else
cache[args] ||= meth.call(*args)
File.open(file, "wb+"){ |f| Marshal.dump(cache, f) }
end
end
end
cache
end

# Code snippet
include Memoize
def fib(n)
return n if n < 2
fib(n-1) + fib(n-2)
end
memoize_to_file(:fib, "temp.txt")
fib(10)

However, running that gives me this error: in `fib': undefined method
`+' for #<File:temp.txt (closed)> (NoMethodError)

Any ideas?

Thanks,

Dan
7 Answers

Ara.T.Howard

1/1/2006 1:28:00 AM

0

Daniel Berger

1/1/2006 1:53:00 AM

0

ara.t.howard@noaa.gov wrote:
> On Sun, 1 Jan 2006, Daniel Berger wrote:

<snip>

> harp:~ > cat a.rb
> def memoize_to_file(name, file)
> cache = Hash.new.update(Marshal.load(File.read(file))) rescue {}
> (class << self; self; end).class_eval do
> define_method(name) do |*args|
> unless cache.has_key?(args)
> cache[args] = method(name).call(*args)
> File.open(file, "wb+"){|f| Marshal.dump(cache, f) }
> end
> cache[args]
> end
> end
> end
>
> def fib(n)
> return n if n < 2
> fib(n-1) + fib(n-2)
> end
>
> memoize_to_file "fib", "fib.cache"
> n = fib 10
> p n

As is, I get a stack level too deep error on Windows. If I change the
"cache[args] =" to "cache[args] ||=", I always get back nil.

I'm probably being thick here, but any help is appreciated.

Thanks,

Dan

Ara.T.Howard

1/1/2006 3:33:00 AM

0

Daniel Berger

1/1/2006 12:28:00 PM

0

ara.t.howard@noaa.gov wrote:
> On Sun, 1 Jan 2006, Daniel Berger wrote:
>
> > ara.t.howard@noaa.gov wrote:
> >> On Sun, 1 Jan 2006, Daniel Berger wrote:
> >
> > <snip>
> >
> >> harp:~ > cat a.rb
> >> def memoize_to_file(name, file)
> >> cache = Hash.new.update(Marshal.load(File.read(file))) rescue {}
> >> (class << self; self; end).class_eval do
> >> define_method(name) do |*args|
> >> unless cache.has_key?(args)
> >> cache[args] = method(name).call(*args)
> >> File.open(file, "wb+"){|f| Marshal.dump(cache, f) }
> >> end
> >> cache[args]
> >> end
> >> end
> >> end
> >>
> >> def fib(n)
> >> return n if n < 2
> >> fib(n-1) + fib(n-2)
> >> end
> >>
> >> memoize_to_file "fib", "fib.cache"
> >> n = fib 10
> >> p n
> >
> > As is, I get a stack level too deep error on Windows. If I change the
> > "cache[args] =" to "cache[args] ||=", I always get back nil.
> >
> > I'm probably being thick here, but any help is appreciated.
>
> sorry, don't know how that's running on linux in the first place... you need:
>
> --- a.rb 2005-12-31 20:30:59.000000000 -0700
> +++ b.rb 2005-12-31 20:31:10.000000000 -0700
> @@ -1,9 +1,10 @@
> def memoize_to_file(name, file)
> + meth = method(name)
> cache = Hash.new.update(Marshal.load(File.read(file))) rescue {}
> (class << self; self; end).class_eval do
> define_method(name) do |*args|
> unless cache.has_key?(args)
> - cache[args] = method(name).call(*args)
> + cache[args] = meth.call(*args)
> File.open(file, "wb+"){|f| Marshal.dump(cache, f) }
> end
> cache[args]
>
> with that it works for me on linux and windows.
>
> cheers.
>
> -a
> --
>

Thanks, that did the trick nicely. It's now part of memoize 1.2.0. :)

Regards,

Dan

Ara.T.Howard

1/2/2006 5:25:00 PM

0

Daniel Berger

1/2/2006 7:28:00 PM

0

ara.t.howard@noaa.gov wrote:
> This message is in MIME format. The first part should be readable text,
> while the remaining parts are likely unreadable without MIME-aware tools.
>
> On Mon, 2 Jan 2006, Mauricio Fernandez wrote:
>
> >
> > Dumping the cache on every miss seems expensive.
> > I changed the code to save it once every N misses, and made the cache update
> > atomic to prevent problems with:
> > * concurrent executions of the memoized method (processes and threads)
> > * no HD space being left (the previous cache state is preserved)
> >
> > I also applied those changes to memoize.rb 1.2.0 and generalized it to work
> > with instance methods, see the patch after memo.rb.
>
> nice idea.

Looks interesting but I get this with windows xp using his sample code:

>ruby memoize.rb
Rehearsal ----------------------------------------------
period 1 memoize.rb:39:in `has_key?': stack level too deep
(SystemStackError)
from memoize.rb:39:in `fib'
from memoize.rb:56:in `fib'
from memoize.rb:40:in `fib'
from memoize.rb:56:in `fib'
from memoize.rb:40:in `fib'
from memoize.rb:56:in `fib'
from memoize.rb:40:in `fib'
from memoize.rb:56:in `fib'
... 539 levels...
from c:/ruby184/lib/ruby/1.8/benchmark.rb:293:in `measure'
from c:/ruby184/lib/ruby/1.8/benchmark.rb:261:in `bmbm'
from c:/ruby184/lib/ruby/1.8/benchmark.rb:259:in `bmbm'
from memoize.rb:97

Regards,

Dan

Mauricio Fernández

1/2/2006 8:51:00 PM

0

On Tue, Jan 03, 2006 at 04:32:57AM +0900, Daniel Berger wrote:
> > > I also applied those changes to memoize.rb 1.2.0 and generalized it to work
> > > with instance methods, see the patch after memo.rb.
>
> Looks interesting but I get this with windows xp using his sample code:
>
> >ruby memoize.rb
> Rehearsal ----------------------------------------------
> period 1 memoize.rb:39:in `has_key?': stack level too deep
> (SystemStackError)
> from memoize.rb:39:in `fib'
> from memoize.rb:56:in `fib'
> from memoize.rb:40:in `fib'
> from memoize.rb:56:in `fib'
> from memoize.rb:40:in `fib'
> from memoize.rb:56:in `fib'
> from memoize.rb:40:in `fib'
> from memoize.rb:56:in `fib'
> ... 539 levels...

Your stack is too small; fib(500) goes 1000 levels deep. Change
those examples to fib(100) etc.:

batsman@tux-chan:/tmp$ ruby memoize.rb
Rehearsal ---------------------------------------------
period 1 memoize.rb:54:in `fib': let's see how deep we get (RuntimeError)
from memoize.rb:39:in `fib'
from memoize.rb:55:in `fib'
from memoize.rb:39:in `fib'
from memoize.rb:55:in `fib'
from memoize.rb:39:in `fib'
from memoize.rb:55:in `fib'
from memoize.rb:39:in `fib'
from memoize.rb:55:in `fib'
... 993 levels...
from /home/batsman/usr/lib/ruby/1.8/benchmark.rb:293:in `measure'
from /home/batsman/usr/lib/ruby/1.8/benchmark.rb:261:in `bmbm'
from /home/batsman/usr/lib/ruby/1.8/benchmark.rb:259:in `bmbm'
from memoize.rb:96

given

batsman@tux-chan:/tmp$ diff -u memoize.rb.mod memoize.rb
--- memoize.rb.mod 2006-01-02 21:38:18.000000000 +0100
+++ memoize.rb 2006-01-02 21:46:10.000000000 +0100
@@ -51,7 +51,7 @@

if __FILE__ == $0
def fib(n)
- return n if n < 2
+ raise "let's see how deep we get" if n < 2
fib(n-1) + fib(n-2)
end

@@ -97,10 +97,10 @@
dummy1 = Dummy1.new
dummy2 = Dummy2.new
bm.report("period 1") { runs.times{ fib 500 } }
- bm.report("period 10"){ runs.times{ fib3 500 } }
- bm.report("at_exit") { runs.times{ fib2 500 } }
- bm.report("at_exit''") { runs.times{ dummy1.fib 500 } }
- bm.report("at_exit'''") { runs.times{ dummy2.fib 500 }; runs = 100000}
+ #bm.report("period 10"){ runs.times{ fib3 500 } }
+ #bm.report("at_exit") { runs.times{ fib2 500 } }
+ #bm.report("at_exit''") { runs.times{ dummy1.fib 500 } }
+ #bm.report("at_exit'''") { runs.times{ dummy2.fib 500 }; runs = 100000}
end

end

--
Mauricio Fernandez