Python 3.0 - is this true?

Kay Schluehr kay.schluehr at gmx.net
Sun Nov 9 00:14:18 EST 2008


On 9 Nov., 05:49, Alex_Gaynor <alex.gay... at gmail.com> wrote:
> On Nov 8, 11:36 pm, Kay Schluehr <kay.schlu... at gmx.net> wrote:
>
>
>
> > On 9 Nov., 05:04, Terry Reedy <tjre... at udel.edu> wrote:
>
> > > Have you written any Python code where you really wanted the old,
> > > unpredictable behavior?
>
> > Sure:
>
> > if len(L1) == len(L2):
> >     return sorted(L1) == sorted(L2)  # check whether two lists contain
> > the same elements
> > else:
> >     return False
>
> > It doesn't really matter here what the result of the sorts actually is
> > as long as the algorithm leads to the same result for all permutations
> > on L1 ( and L2 ).
>
> that same thing could be done with a multiset type, which would also
> have better performance(O(n) vs. O(nlogn)).

I guess building a multiset is a little more expensive than just O(n).
It is rather like building a dict from a list which is O(k*n) with a
constant but small factor k. The comparison is of the same order. To
enable the same behavior as the applied sorted() a multiset must
permit unhashable elements. dicts don't do the job.








More information about the Python-list mailing list