search

TeXitoi / benchmarksgame-rs

The Computer Language Benchmarks Game: Rust implementations
Other
70 stars 19 forks source link

binary_trees: simplify item_check #56

Closed cristicbz closed 7 years ago

cristicbz commented 7 years ago

Rewrite item_check as an explicit loop rather than tail recursive calls, making the implementation much shorter with the same performance characteristic.

Also flips the allocation order of left and right children to match the traversal order of the new method (which does the right branch depth-first on every iteration).

This doesn't affect performance at all on my machine, and Isaac didn't like the previous implementation.

cristicbz commented 7 years ago

cc @mbrubeck what do you think?

cristicbz commented 7 years ago

@TeXitoi when you get a chance, could you please update your submission with this? I think Isaac is losing his patience a little bit with us (maybe justifiably so :) ).

mbrubeck commented 7 years ago

Looks good to me.

cristicbz commented 7 years ago

So I actually changed the implementation to match the one in Haskell more closely and submitted it at: https://alioth.debian.org/tracker/index.php?func=detail&aid=315639&group_id=100815&atid=413122

mbrubeck commented 7 years ago

Unless Isaac changes his mind, it sounds like Rust will not be allowed to use tail recursion at all and we'll need to revert back to the plain recursive item_check.

cristicbz commented 7 years ago

I created another submission with a vanilla recursive item_check.

cristicbz commented 7 years ago

I'll make a PR if Issac decides it's OK