On Saturday 22 Oct 2005 11:57 am, Adrian Hey wrote:
2- The Hedge algorithm seems to be a bit of a problem IMO. The actual benchmark times for AVL union and Data.Set union aren't significantly different for sets of Ints (AVL seemed marginally faster, but nothing to get excited about). But if you count the number of comparisons actually performed Data.Set (Hedge algorithm) is doing about 3..5 times as many comparisons. Presumably this would be reflected in measured execution times in cases where set element comparison was less trivial than comparing Ints.
I've just re-run some old benchmarking code to see what the latest situation is re. this. There are 3 tests, all with random Ints: Test1 : union of two different sets, both of size 200000 Test2 : union of two different sets, of size 200000 and 200 Test3 : union of two different sets, of size 200 and 200000. Relative execution times (in no particular units) are: Data.Tree.AVL Data.Set Test1: 0.51 0.66 Test2: 1.07e-3 2.35e-3 Test3: 1.07e-3 2.32e-3 So it seems if there's a big difference in set size the difference in performance isn't so marginal after all. The above tests do not include comparison counting overhead. If I count the number of comparisons the same tests give.. Data.Tree.AVL Data.Set Test1: 470668 1562230 Test2: 2449 11336 Test3: 2445 11238 Regards -- Adrian Hey