[Python-ideas] Add OrderedSet now that OrderedDict is in collections
Arnaud Delobelle
arnodel at googlemail.com
Fri May 8 21:16:41 CEST 2009
On 8 May 2009, at 16:56, Mart Sõmermaa wrote:
> On Fri, May 8, 2009 at 6:06 PM, Arnaud Delobelle <arnodel at 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.
>
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
More information about the Python-ideas
mailing list