search

kowainik / treap

:leaves: :deciduous_tree: :fallen_leaf: Efficient implementation of the implicit treap data structure
Mozilla Public License 2.0
63 stars 1 forks source link

Add benchmarks #18

Open chshersh opened 5 years ago

chshersh commented 5 years ago

Compare with fingertree package:

JulStrat commented 5 years ago

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).

chshersh commented 5 years ago

@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!

JulStrat commented 5 years ago

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.

chshersh commented 5 years ago

@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.