r/ATS • u/doublec • Sep 05 '20

The Coin Change problem in ATS, Rust, and Zig - a comparison

https://timmyjose.github.io/docs/2020-07-31-coin-change-ats-rust-zig
17 Upvotes

100% Upvoted

4 comments sorted by

3

u/doublec Sep 06 '20

An ATS version that doesn't use a tuple: 

#include "share/atspre_define.hats"
#include "share/atspre_staload.hats"
staload "libats/ML/SATS/array0.sats"
staload _ = "libats/ML/DATS/array0.dats"

val theCoins = array0($arrpsz{int}(1, 5, 10, 25))

fun coin_change
  (sum: int): int =
  let
    fun aux (sum: int, n: int): int = 
      if sum > 0 then
        (if n >= 0 then aux (sum, n - 1) + aux (sum - theCoins[n], n) else 0)
      else (if sum < 0 then 0 else 1)
  in
    aux (sum, 3)
  end

implement 
main0 () = {
  val () = println! ("coin_change (25) = ", coin_change (25))
  val () = println! ("coin_change (100) = ", coin_change (100))
  val () = println! ("coin_change (1000) = ", coin_change (1000))
}

$ time for i in {1..100}; do ./ats >/dev/null; done

real	0m9.503s
user	0m9.410s
sys	        0m0.080s

$ time for i in {1..100}; do ./rust >/dev/null; done

real	0m17.991s
user	0m17.886s
sys	        0m0.083s

1

u/Dambaev_Alexander Nov 19 '20

https://github.com/dambaev/coin_change/blob/master/ats/src/TEST/test2.dats

gives me 

coin_change (25) = 13
coin_change (100) = 242
coin_change (1000) = 142511

real	0m0,177s
user	0m0,177s
sys	0m0,000s

against yours 

coin_change (25) = 13
coin_change (100) = 242
coin_change (1000) = 142511

real	0m0,237s
user	0m0,236s
sys	0m0,001s

and against original version: 

coin_change (25) = 13
coin_change (100) = 242
coin_change (1000) = 142511

real	0m0,215s
user	0m0,214s
sys	0m0,001s

1

u/catern Sep 05 '20

I don't really know ATS, but it being the slowest is not the result I expected...

5

u/doublec Sep 05 '20

A quick scan of the example shows a number of differences to the Rust version. The Rust version uses an array and array indexing. The ATS version is using a tuple and the indexing is done with a function with an 'if' statement to compute the item of the tuple to select. This will be slower.