[Haskell-beginners] Red-black tree performance

Adrien Haxaire adrien at haxaire.org
Tue Mar 20 18:05:15 CET 2012


On Tue, Mar 20, 2012 at 04:27:08PM +0000, Lorenzo Bolla wrote:
> Your scripts stack-overflows on my box.
> 
> I've made 2 little changes, to ensure strictness. I believe your
> "insertList" is building up a huge list of thunks.
> 
> import Data.Foldable (foldr')
> <snip>
> main :: IO ()
> main = putStrLn $ show $ maxTree $ foldr' insert Empty toInsert
> 
> Better?
> L.

Yes definitely, thank you. That was someting obvious that I didn't see. 

Now I have 0.64 seconds for C++ and 3.95 for Haskell. That's better!

The ratio 3.95/0.64 is 6.171875, which is more in the range I expected. That's twice better from what I had before. 

I am still looking at the balance function, maybe there is some things I can optimize there as well.

-- 
Adrien Haxaire 
www.adrienhaxaire.org | @adrienhaxaire



More information about the Beginners mailing list