Re: [Python-ideas] Add OrderedSet now that OrderedDict is in collections
On 8 May 2009, at 15:23, Mart Sõmermaa wrote:
I implemented a unification algorithm that needed multisets to work in O(n^2). -- Arnaud
On Fri, May 8, 2009 at 6:06 PM, Arnaud Delobelle <arnodel@googlemail.com> wrote:
I implemented a unification algorithm that needed multisets to work in O(n^2).
Complexity is a totally different theme and best reserved for extensions. Supporting special-case containers that have various space/speed and best/worst case tradeoffs have been discussed before and the consensus seems to be that supporting them in stdlib is infeasible -- with what I entirely agree. Supporting multiset only for O(n^2) performance would violate that consensus. However, ordered set and ordered map are not special-case in that sense. It's not the O-complexity but general utility -- i.e. the plugging of the holes in the ordering and uniqueness table and helping people with the corresponding use cases -- that vouch for their inclusion in the stdlib. Now that ordered map is in, ordered set could follow.
On 8 May 2009, at 16:56, Mart Sõmermaa wrote:
You misunderstand me. My task was to implement this algorithm. Multisets were the natural data structure to implement this algorithm. That it was O(n^2) (rather than the exponential complexity of the naive unification algorithm) is an issue attached to the algorithm, not to whether I use multisets or not to implement it. -- Arnaud
On Fri, May 8, 2009 at 6:06 PM, Arnaud Delobelle <arnodel@googlemail.com> wrote:
I implemented a unification algorithm that needed multisets to work in O(n^2).
Complexity is a totally different theme and best reserved for extensions. Supporting special-case containers that have various space/speed and best/worst case tradeoffs have been discussed before and the consensus seems to be that supporting them in stdlib is infeasible -- with what I entirely agree. Supporting multiset only for O(n^2) performance would violate that consensus. However, ordered set and ordered map are not special-case in that sense. It's not the O-complexity but general utility -- i.e. the plugging of the holes in the ordering and uniqueness table and helping people with the corresponding use cases -- that vouch for their inclusion in the stdlib. Now that ordered map is in, ordered set could follow.
On 8 May 2009, at 16:56, Mart Sõmermaa wrote:
You misunderstand me. My task was to implement this algorithm. Multisets were the natural data structure to implement this algorithm. That it was O(n^2) (rather than the exponential complexity of the naive unification algorithm) is an issue attached to the algorithm, not to whether I use multisets or not to implement it. -- Arnaud
participants (2)
-
Arnaud Delobelle -
Mart Sõmermaa