[Octave-bug-tracker] [bug #60860] Implementation of memoize

[anonymous]

Follow-up Comment #3, bug #60860 (project octave):

Hello Guillaume,

Thank you for this feature addition. I tried it and unfortunately it seemed to
slow down the execution by roughly 15 times. Please tell me if I am misusing
it.

Here is how I set it up, using anonymous functions for both the memoized and
nonmemoized versions:

octave:1> addpath ("memoize")
octave:2> nonmemo = @(f) bitcountnaive(f)
nonmemo =

@(f) bitcountnaive (f)

octave:3> memo = memoize (@(g) bitcountnaive(g))
memo =

  matlab.lang.MemoizedFunction m_object with properties:

      CacheSize: [1x1 double]
        Enabled: 1
       Function: [1x1 function_handle]



Test without memoization:

octave:4> NN = 255; x = zeros(1,NN); tic; for i = 1:NN, x(i) = nonmemo(i);
end; toc
Elapsed time is 0.01684 seconds.
octave:6> NN = 1023; x = zeros(1,NN); tic; for i = 1:NN, x(i) = nonmemo(i);
end; toc
Elapsed time is 0.084712 seconds.


Test with memoization:

octave:5> NN = 255; x = zeros(1,NN); tic; for i = 1:NN, x(i) = memo(i); end;
toc
Elapsed time is 0.327858 seconds.
octave:7> NN = 1023; x = zeros(1,NN); tic; for i = 1:NN, x(i) = memo(i); end;
toc
Elapsed time is 1.31426 seconds.


The test function bitcountnaive is deliberately chosen to be something that
could benefit from memoization because most of its internal calls have
identical substructures, so the thinking is that subsequent calls of the same
value will make use of the memoization lookup table instead of calling the
recursive function:


function retval = bitcountnaive (n)
  if (n <= 0)
    retval = 0;
  elseif (mod(n,2) == 1) # odd
    retval = 1 + bitcountnaive (floor(n/2));
  else # even
    retval = bitcountnaive (floor(n/2));
  end
endfunction


What am I doing wrong?

    _______________________________________________________

Reply to this item at:

  <https://savannah.gnu.org/bugs/?60860>

_______________________________________________
  Message sent via Savannah
  https://savannah.gnu.org/