Option remember

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

fib2=remember(:fib)
p fib2.call(10)

i get a "in `call’: return from proc-closure (LocalJumpError)"
C:\ruby>ruby -v
ruby 1.6.5 (2001-09-19) [i386-cygwin]

  1. Why it doens’t work ?
    I think that the solution should be the use of ‘binding’, i’ve read the
    paragraph “Calling Methods Dynamically” in prag prog but i don’t understand.
  2. Why fib.type (or self.fib.type) doesn’t work? I’ve understood (even if i
    don’t like) the python way where there is a class “function”, but i don’t
    understand the ruby way.
    I’ve read that the difference between a function and a method is only from
    where u call it (method from outside, function inside the class). I’m right
    ? How access to functions ?
    I would like to read something clear about the difference between proc,
    method and there use. An article about that exists ?
    Especially the use of ‘:’, ‘&’, the class Symbol, Proc, Method, Block,
    Binding.

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

oinkoink+unet@rexx.com
http://www.rexx.com/~oinkoink

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
57

Oops! 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 :slight_smile:
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

http://www.rexx.com/~oinkoink/

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. :slight_smile:

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 :slight_smile:
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

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) }
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

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