[Haskell-cafe] tighter bounds for Data.Map operations (using min(n.m))?

[Johannes Waldmann]

Dear Cafe,

I wonder if some of the resource bounds in
https://hackage.haskell.org/package/containers-0.5.7.1/docs/Data-Map-Strict.html
can be improved. I do not mean "improve the implementation",
but "improve the (stated) bounds".

For example, I am interested in intersection(With).
Bound is stated as O(n+m) (*)

This is a fine worst case bound -
but I certainly use this function with the implied assumption
that it will not visit both trees completely -
in the case that one of them is small.

So, what can we say in terms of min(n,m) ?
Is it linear in that parameter?
Perhaps with an additional factor log(max(n,m)) ?
(for looking up the keys of the smaller tree in the larger one)

The paper linked from the docs has this (p 18 before 9.3)
"the running time of union is better for fortuitous inputs,
for example, similar sized disjoint ranges, and trees which
differ greatly in size" but does not make a formal statement.
This is about union, not intersection, and not hedge_union,
but it's the closest this paper gets to what I have in mind.

Oh, and after that, same question for Data.IntMap.

- J.W.

(*) with the usual neglect for alphabetic order...
_______________________________________________
Haskell-Cafe mailing list
Haskel...@haskell.org
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe

[Johannes Waldmann]

See also https://github.com/haskell/containers/issues/177
(which I found only now) - J.W.