Hi,
i’m trying to code an ‘option remember’ in Ruby.
This option should be used in order to save the result allready computed of
a function.
For exemple: fib=remember(:fib) transorm the fibonacci function in aO(n)
function.
I’ve tried a lot of things but nothing run, i’ve found nothing in the
progmatic programmer and ruby in a nutshell books.
Nothing in the RAA.
Regards.
–
Cedric Foll
mèl: cedric dot foll at laposte dot net
“Cédric Foll” cedric.foll@bigfoot.com writes:
Hi,
i’m trying to code an ‘option remember’ in Ruby.
This option should be used in order to save the result allready computed of
a function.
For exemple: fib=remember(:fib) transorm the fibonacci function in aO(n)
function.
I’ve tried a lot of things but nothing run, i’ve found nothing in the
progmatic programmer and ruby in a nutshell books.
We discuss the ‘once’ trick on page 251, but that doesn’t vary the
result depending on the parameter passed in. You could try extending
that, or you could have a look at Robert Feldt’s memoize package:
http://www.ce.chalmers.se/~feldt/ruby/extensions/memoize/
Cheers
Dave
Take at look at “Memoize” (which is the technical term for what you are
trying to do). Got this from RAA:
Homepage: http://www.ce.chalmers.se/~feldt/ruby/extensions/memoize/
“Cédric Foll” cedric.foll@bigfoot.com wrote in message
news:3d75dd69$0$575$626a54ce@news.free.fr…
Hi,
i’m trying to code an ‘option remember’ in Ruby.
This option should be used in order to save the result allready computed
of
a function.
For exemple: fib=remember(:fib) transorm the fibonacci function in aO(n)
function.I’ve tried a lot of things but nothing run, i’ve found nothing in the
progmatic programmer and ruby in a nutshell books.
Nothing in the RAA.Regards.
–
Cedric Foll
mèl: cedric dot foll at laposte dot net
Thanks for your answers but i don’t like the way used by the pragmatic prog
(but you did great job with this book, thanks a lot !!!). It’s ok but i
would like to find something more “natural”.
The memoise module is to big for me, i only want to understand how it’s
work. I’ve tried to read the module but i don’t understand all because of
his size.
In the “Introduction to Python” book i’d found something very simple
(overload of call for an instance of function class).
So I’ve tried to do something as simple.
I’ve wrote the folowing code and i don’t really understand why it doesn’t
work.
def fib(n) #a function with double recursion
if n < 2
1
else
fib(n-1)+fib(n-2)
end
end
$arg=[] #the table for allready computed variables
def remember(func)
p method(func).call(5) #it’s work
newfunc = Proc.new { |n|
$arg[n]=method(func).call(n) if $arg[n]==nil
return $arg[n]
}
return newfunc
end
Regards.
–
Cedric Foll
cedric dot foll at laposte dot net
Dave Thomas Dave@PragmaticProgrammer.com wrote in message news:m2u1l69bl6.fsf@zip.local.thomases.com…
We discuss the ‘once’ trick on page 251, but that doesn’t vary the
result depending on the parameter passed in. You could try extending
that, or you could have a look at Robert Feldt’s memoize package:
I’ve been having a tough time getting this to work. Can someone
tell me what I’m doing wrong? Here is an attempt to memoize a clumsy
recursion that screams for memoization (a recursive calculation of the
binomial coefficient “n choose k”).
irb(main):002:0> class Integer
irb(main):003:1> def choose(k)
irb(main):004:2> if (k==0 or k==self)
irb(main):005:3> 1
irb(main):006:3> else
(self-1).choose(k) + (self-1).choose(k-1)
irb(main):009:3> end
irb(main):010:2> end
irb(main):011:1> end
nil
irb(main):012:0> 15 .choose 7
6435
irb(main):013:0> class Integer
irb(main):014:1> memoize :choose
irb(main):015:1> end
[:choose]
irb(main):016:0> 15 .choose 7
57
Oops! I’m one confused piggy.
Regards, Bret
def remember(func)
p method(func).call(5) #it’s work
newfunc = Proc.new { |n|
$arg[n]=method(func).call(n) if $arg[n]==nil
return $arg[n]
}
return newfunc
end
return in a block returns from the function containing the block. The
return value of a block call is the value of the last statement. Just
erase the word “return” from your block.
Tobias
Try this:
def f(x)
x+1
end
$arg = []
def remember(func)
Proc.new { |n| $arg[n] ||= method(func).call(n) }
end
x = remember(:f)
puts (x.call(1))
puts (x.call(1))
irb(main):012:0> 15 .choose 7
6435
irb(main):013:0> class Integer
irb(main):014:1> memoize :choose
irb(main):015:1> end
[:choose]
irb(main):016:0> 15 .choose 7
57Oops! I’m one confused piggy.
I haven’t looked at it too carefully, but I’d guess that the problem has to do
with the fact that nCr is a function of two variables. Maybe Memoize can
only handle functions of one variable (in the general case).
Hi Bret,
in the memoize docs it says that only functions not depending on
internal state can be memoized, in other words the function result
should only depend on the function arguments. Clearly
15.choose 7
is different from
10.choose 7
although the arg list is the same. If you change the implementation
to something like
class Integer
def choose(k)
choose2(self,k)
end
private
def choose2(n,k)
if (k==0 or k==n)
1
else
choose2(n-1,k) + choose2(n-1,k-1)
end
end
memoize :choose2
end
it should work as you expected.
Regards,
Pit
On 5 Sep 2002, at 4:45, Bret Jolly wrote:
(…) You could try extending
that, or you could have a look at Robert Feldt’s memoize package:I’ve been having a tough time getting this to work. Can someone
tell me what I’m doing wrong? Here is an attempt to memoize a clumsy
recursion that screams for memoization (a recursive calculation of the
binomial coefficient “n choose k”).(…)
The general solution is not much more complicated:
$arg = {}
def remember(func)
m = method(func)
Proc.new { |n| ($arg[m.id]||=[])[n] ||= m.call(n) }
end
Well, I’m a Ruby Newbie, so this question should be interesting.
I somehow talked my professor at school to let me use Ruby instead of C++
for the algorithm class. Frankly, I find using Ruby much easier than C (and
it’s children). It just makes sense to me.
In a short amount of time, however, I will have a problem. Pointers will
very quickly become an integral part of our course study. To continue, I
would need to do some meaningful pointer work in Ruby. Does anyone know of
libraries to do such things, or are there other ways? If you could give some
assistance, I’d be greatly appreciated 
I’d like to stick with Ruby, but if the answer is no I’ll make do.
Thanks in advance!
Adam Baxter; AKA Peach
“Pit Capitain” pit@capitain.de wrote in message news:3D768F79.32454.1105AB32@localhost…
Hi Bret,
in the memoize docs it says that only functions not depending on
internal state can be memoized, in other words the function result
should only depend on the function arguments. Clearly
15.choose 7
is different from
10.choose 7
although the arg list is the same.
[good example of a fix deleted]
I understand now. Thanks! I was wondering about the memoize package
itself, but as the pragmatic programmers would say, “select isn’t broken”.
Regards, Bret
return in a block returns from the function containing the block. The
return value of a block call is the value of the last statement. Just
erase the word “return” from your block.
and
$arg =
def remember(func)
Proc.new { |n| $arg[n] ||= method(func).call(n) }
end
Ok, it work. Thanks.
But i’ve still have a problem.
When the function is recursive (like fibonnacci is) it doesn’t work has
expected.
Only the first value is memorized (if i call fib(10), only the value for
n=10 and not n<10).
The first call is the new function but the new function call the old one so
i’m still in O(2^n).
What is the solution ?
Regards
Ruby has no pointers. However, it has references, which are just as
good.
If I write:
a = ‘foo’
then a is a reference to a String object containing the text ‘foo’. You
can think of a reference in Ruby as a pointer with which you cannot do
pointer arithmetic (in C++, you can never modify a reference; Ruby lets
you reassign references, as long as their name doesn’t begin with a
capital letter).
It’s possible to write a linked list in pure Ruby, but it will be slow.
For example, if I want a singly-linked list that I can only append to
(not very useful), I might write:
class List
Node = Struct.new(“Node”, :next, :value)
def initialize
@head = nil
@tail = nil
end
def each(node = @head, &block)
return if node.nil?
yield node.value
each(node.next, &block)
end
def push(value)
if @tail then
@tail.next = Node.new(nil, value)
@tail = @tail.next
else
@head = @tail = Node.new(nil, value)
end
end
end
I’ll leave insertion into the beginning/middle, deletion from the list,
etc. as an exercise for the reader. 
Paul
On Thu, Sep 05, 2002 at 06:11:56AM +0900, Peach wrote:
Well, I’m a Ruby Newbie, so this question should be interesting.
I somehow talked my professor at school to let me use Ruby instead of C++
for the algorithm class. Frankly, I find using Ruby much easier than C (and
it’s children). It just makes sense to me.
In a short amount of time, however, I will have a problem. Pointers will
very quickly become an integral part of our course study. To continue, I
would need to do some meaningful pointer work in Ruby. Does anyone know of
libraries to do such things, or are there other ways? If you could give some
assistance, I’d be greatly appreciated
I’d like to stick with Ruby, but if the answer is no I’ll make do.
Pardon the pun but if the whole point of the next section is to learn
pointers then you might as well use C/C++ and learn how they work - it
won’t be wasted effort. However, it may be worthwhile to wrap your
assignment code with SWIG and unit test results with ruby.
On Thu, Sep 05, 2002 at 06:11:56AM +0900, Peach wrote:
…
In a short amount of time, however, I will have a problem. Pointers will
very quickly become an integral part of our course study. To continue, I
…
–
Alan Chen
Digikata LLC
http://digikata.com
Cédric Foll wrote:
return in a block returns from the function containing the block. The
return value of a block call is the value of the last statement. Just
erase the word “return” from your block.and
$arg =
def remember(func)
Proc.new { |n| $arg[n] ||= method(func).call(n) }
endOk, it work. Thanks.
But i’ve still have a problem.
When the function is recursive (like fibonnacci is) it doesn’t work has
expected.
Only the first value is memorized (if i call fib(10), only the value for
n=10 and not n<10).
The first call is the new function but the new function call the old one so
i’m still in O(2^n).What is the solution ?
Regards
You can redefine the original method, (But therefore you must alias the original one,
if you do it completely correctly, then you will arrive at the solution in the
pickaxe book)
As an illustration of the idea, see the following code snippet:
def f(x)
puts “f(#{x}) called”
if x>0
f(x-1)+1
else
0
end
end
def remember(func)
Proc.new { |n| ($arg||={})[n] ||= method(func).call(n) }
end
alias old_f f
$f_rem = remember :old_f
def f(*x)
$f_rem.call(*x)
end
puts(f(3))
puts(f(5))
The crux lies in the automatic (unique!!!) name generation of old_f and $f_rem,
in the general case.
Best Regards, Christian