On 14/10/13 03:20, AntC wrote:
Thanks Niklas, I hadn't spotted those benchmarks back in July.
No worries :)
I'm surprised at that result for singletons (and for very small numbers of elements which are in fact each different).
I think one of the main reasons for the performance difference is that a list node and a Set binary tree node have pretty much the same performance, with the difference that in http://hackage.haskell.org/package/containers-0.5.2.1/docs/src/Data-Set-Base... data Set a = Bin {-# UNPACK #-} !Size !a !(Set a) !(Set a) | Tip there are strictness and unpack annotations, while for data [a] = [] | a : [a] -- pseudo syntax there are not. Good for us in this case, I guess.
It seems to me that for small numbers, the Set-based approach still requires comparing each element to each other.
This I don't understand.
Then here's a further possible optimisation, instead of making separate calls to `member` and `insert`:
This I understand again. Where do you get insert' from? containers doesn't seem to have it. Do you suggest adding it? Niklas