Add benchmarks

Question

Add benchmarks

chshersh opened this issue 5 years ago · 4 comments

chshersh commented 5 years ago

Compare with fingertree package:

http://hackage.haskell.org/package/fingertree

Answer 1 · 2019-06-01T11:47:50.000Z

Hello @chshersh.

Can you test your TREAP implementation (if possible) on real problems bellow?

https://www.spoj.com/problems/SDITSBST/
https://www.spoj.com/problems/SDITSAVL/
https://www.spoj.com/problems/ALLIN1/

It would be great for Haskell (and not only, I coded Treap in Pascal) community.

Thanks.

Best regards.
Julian (julkas[at]spoj[dot]com).

Answer 2 · 2019-06-02T08:12:31.000Z

@JulStrat Thanks for the idea. I don't have capacity at the moment for solving problems on a particular platform. And this probably won't be that straightforward because problem-solving platforms usually don't support all libraries from Hackage.

But I'm happy to help if somebody is willing to test my implementation!

Answer 3 · 2019-06-02T10:20:26.000Z

Hello @chshersh.

I don't have capacity at the moment for solving problems on a particular platform.

It's OK!

What about relative test (benchmark) your Treap vs Standard Haskell Set implementation on random 64-bit integers (100000, 1000000 random 64-bit keys)?

Regards.
Julian.

Answer 4 · 2019-06-05T06:48:36.000Z

@JulStrat This issue is exactly about implementing relative benchmarks. However, Set doesn't provide the same interface as Treap so it's not fair to compare against Set. The closest data structure is FingerTree implemented in either fingertree or hw-fingertree package.