------art_8262_9451382.1201534452078
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

2008/1/27, Paolo Bonzini <bonzini / gnu.org>:
>
> Here is my second attempt:
>
> def make_change(a, list  25, 10, 5, 1])
>   # to pass testcases :-P
>   return nil if a < 0
>   return nil if a ! .floor
>
>   parents  rray.new(a + 1)
>   parents[0]  
>   worklist  0]
>   while parents[a].nil? && !worklist.empty? do
>     base  orklist.shift
>     list.each do |coin|
>       tot  ase + coin
>       if tot <  && parents[tot].nil?
>         parents[tot]  ase
>         worklist << tot
>       end
>     end
>   end
>
>   return nil if parents[a].nil?
>   result  ]
>   while a > 0 do
>     parent  arents[a]
>     result << a - parent
>     a  arent
>   end
>   result.sort!.reverse!
> end
>
> parents[a] is nil if the solution for amount "a" has not been found
> yet, and a-c if the solution is the same as the solution for amount "a-
> c" plus a coin of value "c".  The solution is reconstructed in the
> second while loop.
>
> My first solution used an 1.upto(a) loop to compute the optimal
> solution for make_change(1), then for make_change(2), etc.  This was a
> classic dynamic programming style where lower-cost solutions replace
> older ones as they are found.  In this solution, instead of computing
> subproblem solutions in order of amount, I compute solutions in order
> of cost: first all solutions of cost 1, then all solutions of cost 2,
> etc., until the solution is found for the requested amount (see the
> parents[a].nil? test).  It is interesting that in this way we don't
> even need to store the solutions' costs.
>
> The worst case is when there's no solution and it has cost O(a |
> list|).  I didn't make any attempt at optimizing it.
>
> The performance is good; vsv's testcases run in 10 seconds (compared
> to 30 for my 1.upto(a) solution).
>
> I tried running a similar program in GNU Smalltalk and the results
> were disappointing for Ruby 1.8: GNU Smalltalk was about 10 times
> faster for this solution, and 18 times faster for the slower
> solution.  The ratio goes down from 18 to 10 probably because variable-
> size collection in Smalltalk require an OrderedCollection, which is
> written in 100% Smalltalk (unlike Ruby's Arrays and Smalltalk's fixed-
> size Arrays).  I'd be very interested if people ran it under Ruby 1.9
> or Rubinius and gave times for it.
>
> Paolo
>
> these are the results of vsv's tests and your script with ruby 1.8.6 and
ruby 1.9.

paddor@pantoo ~ $ ruby --version
ruby 1.8.6 (2007-12-03 patchlevel 113) [x86_64-linux]
paddor@pantoo ~ $ ruby19 --version
ruby 1.9.0 (2008-01-28 revision 15294) [x86_64-linux]
paddor@pantoo ~ $ ruby -rbonzini vsv.rb
Loaded suite vsv
Started
.........
Finished in 0.87486 seconds.

9 tests, 631 assertions, 0 failures, 0 errors
paddor@pantoo ~ $ ruby19 -rbonzini vsv.rb
Loaded suite vsv
Started
.........
Finished in 0.245152151 seconds.

9 tests, 631 assertions, 0 failures, 0 errors

can i see the sources of your gnu smalltalk solution?

------art_8262_9451382.1201534452078--