Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Python > Python 3.0 - is this true?

Reply
Thread Tools

Python 3.0 - is this true?

 
 
Kay Schluehr
Guest
Posts: n/a
 
      11-09-2008
On 9 Nov., 05:49, Alex_Gaynor <(E-Mail Removed)> wrote:
> On Nov 8, 11:36 pm, Kay Schluehr <(E-Mail Removed)> wrote:
>
>
>
> > On 9 Nov., 05:04, Terry Reedy <(E-Mail Removed)> 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.





 
Reply With Quote
 
 
 
 
Steven D'Aprano
Guest
Posts: n/a
 
      11-09-2008
On Sat, 08 Nov 2008 20:36:59 -0800, Kay Schluehr wrote:

> On 9 Nov., 05:04, Terry Reedy <(E-Mail Removed)> 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 ).


How often do you care about equality ignoring order for lists containing
arbitrary, heterogeneous types?

In any case, the above doesn't work now, since either L1 or L2 might
contain complex numbers. The sorted() trick only works because you're
making an assumption about the kinds of things in the lists. If you want
to be completely general, the above solution isn't guaranteed to work.

If you're prepared to assume hashability, then the obvious Multiset
solution is probably better even than the above. If you want complete
generality, you can't even assume that items in the list can be ordered
at all, so you need something like this:


def collate_and_sort(L):
D = {}
for item in L:
t = type(item)
x = D.setdefault(t, [])
x.append(item)
for x in D.values():
try:
x.sort()
except TypeError:
try:
x.sort(key=str)
except TypeError:
x.sort(key=id)
return D


def unordered_equals(L1, L2):
if len(L1) != len(L2):
return False
try:
return sorted(L1) == sorted(L2)
except TypeError:
return collate_and_sort(L1) == collate_and_sort(L2)


But note that even this solution isn't perfect, since it will fail to do
the right thing for L1=[1, {}, 2] and L2=[1, {}, 2.0]. Here is a way to
solve the problem assuming only that the items support equality:

def unordered_equals2(L1, L2):
if len(L1) != len(L2):
return False
for item in L1:
if L1.count(item) != L2.count(item):
return False
return True


--
Steven
 
Reply With Quote
 
 
 
 
Kay Schluehr
Guest
Posts: n/a
 
      11-09-2008
On 9 Nov., 07:06, Steven D'Aprano <st...@REMOVE-THIS-
cybersource.com.au> wrote:
> On Sat, 08 Nov 2008 20:36:59 -0800, Kay Schluehr wrote:
> > On 9 Nov., 05:04, Terry Reedy <(E-Mail Removed)> 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 ).

>
> How often do you care about equality ignoring order for lists containing
> arbitrary, heterogeneous types?


A few times. Why do you care, Steven?

> In any case, the above doesn't work now, since either L1 or L2 might
> contain complex numbers.
> The sorted() trick only works because you're
> making an assumption about the kinds of things in the lists. If you want
> to be completely general, the above solution isn't guaranteed to work.


You are right. I never used complex numbers in Python so problems were
not visible. Otherwise the following comp function in Python 2.X does
the job:

def comp(x1, x2):
try:
if x1<x2:
return -1
else:
return 1
except TypeError:
if str(x1)<str(x2):
return -1
else:
return 1

Not sure how to transform it into a search key that is efficient and
reliable.

[...]

> Here is a way to
> solve the problem assuming only that the items support equality:
>
> def unordered_equals2(L1, L2):
> if len(L1) != len(L2):
> return False
> for item in L1:
> if L1.count(item) != L2.count(item):
> return False
> return True


Which is O(n**2) as you might have noted.


 
Reply With Quote
 
Steven D'Aprano
Guest
Posts: n/a
 
      11-09-2008
On Sat, 08 Nov 2008 22:53:14 -0800, Kay Schluehr wrote:

>> How often do you care about equality ignoring order for lists
>> containing arbitrary, heterogeneous types?

>
> A few times. Why do you care, Steven?


I'm a very caring kind of guy.


>> In any case, the above doesn't work now, since either L1 or L2 might
>> contain complex numbers.
>> The sorted() trick only works because you're making an assumption about
>> the kinds of things in the lists. If you want to be completely general,
>> the above solution isn't guaranteed to work.

>
> You are right. I never used complex numbers in Python so problems were
> not visible. Otherwise the following comp function in Python 2.X does
> the job:

[...]
> Not sure how to transform it into a search key that is efficient and
> reliable.


Yes, that's a general problem. It's not always easy to convert a sort
comparison function into a key-based sort. I know that 99% of the time
key is the right way to do custom sorts, but what about the other 1%?


> [...]
>
>> Here is a way to
>> solve the problem assuming only that the items support equality:
>>
>> def unordered_equals2(L1, L2):
>> if len(L1) != len(L2):
>> return False
>> for item in L1:
>> if L1.count(item) != L2.count(item):
>> return False
>> return True

>
> Which is O(n**2) as you might have noted.


Yes, I did notice. If you can't assume even ordering, then you need to do
a lot more work.


--
Steven
 
Reply With Quote
 
Arnaud Delobelle
Guest
Posts: n/a
 
      11-09-2008
Kay Schluehr <(E-Mail Removed)> writes:

> On 9 Nov., 07:06, Steven D'Aprano <st...@REMOVE-THIS-

[...]
>> In any case, the above doesn't work now, since either L1 or L2 might
>> contain complex numbers.
>> The sorted() trick only works because you're
>> making an assumption about the kinds of things in the lists. If you want
>> to be completely general, the above solution isn't guaranteed to work.

>
> You are right. I never used complex numbers in Python so problems were
> not visible. Otherwise the following comp function in Python 2.X does
> the job:
>
> def comp(x1, x2):
> try:
> if x1<x2:
> return -1
> else:
> return 1
> except TypeError:
> if str(x1)<str(x2):
> return -1
> else:
> return 1
>


Sadly it fails on transitivity:

>>> comp(2, 3j)

-1
>>> comp(3j, True)

-1
>>> comp(True, 2)

-1

--
Arnaud
 
Reply With Quote
 
Rhamphoryncus
Guest
Posts: n/a
 
      11-09-2008
On Nov 8, 10:14*pm, Kay Schluehr <(E-Mail Removed)> wrote:
> 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.


Although it has a runtime of k*n, it is still O(n). big-O notation
ignores constant factors, dealing only with scalability.
 
Reply With Quote
 
Stefan Behnel
Guest
Posts: n/a
 
      11-09-2008
Kay Schluehr wrote:
> On 9 Nov., 07:06, Steven D'Aprano <st...@REMOVE-THIS-
> cybersource.com.au> wrote:
>> How often do you care about equality ignoring order for lists containing
>> arbitrary, heterogeneous types?

>
> A few times. Why do you care, Steven?


"I miss this feature" is an unqualified statement, just like "I'll miss George
W. Bush". That does not necessarily imply that I want him back in the position
that the had for the last eight years. It might just mean that it was fun to
see him on telly (although I bet his entertainment show was more expensive
than the average Marx-Brothers sketch).

Stefan
 
Reply With Quote
 
Kay Schluehr
Guest
Posts: n/a
 
      11-09-2008
On 9 Nov., 09:26, Rhamphoryncus <(E-Mail Removed)> wrote:
> On Nov 8, 10:14*pm, Kay Schluehr <(E-Mail Removed)> wrote:
>
> > 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.

>
> Although it has a runtime of k*n, it is still O(n). *big-O notation
> ignores constant factors, dealing only with scalability.


You are right. I remembered this short after my posting was sent.
 
Reply With Quote
 
Roy Smith
Guest
Posts: n/a
 
      11-09-2008
In article <(E-Mail Removed)>,
Terry Reedy <(E-Mail Removed)> wrote:

> Yes, key= lets you sort anything anyway you want.
> >>> l=[1, '2', 3j]
> >>> sorted(l, key = str)

> [1, '2', 3j]


The problem here is that str() is degenerate, i.e. a != b does not imply
str(a) != str(b).

> >>> sorted(l, key = id)

> ['2', 3j, 1]


And of course, this has to opposite problem, a == b does not imply id(a) ==
id(b). Whether either of these "problems" is really a problem obviously
depends on what you're trying to do.

In 3.0, can you still order types? In 2.x, you can do:

>>> t1 = type(1)
>>> t2 = type(1j)
>>> t1 < t2

False

If this still works in 3.0, then you can easily do something like:

def total_order(o1, o2):
"Compare any two objects of arbitrary types"
try:
return o1 <= o2
except UncomparableTypesError: # whatever the right name is
return type(o1) <= type(o2)

and get the same effect as you had in 2.x.
 
Reply With Quote
 
Diez B. Roggisch
Guest
Posts: n/a
 
      11-09-2008
>
> Also, I thought that part of the python philosophy was to allow any
> sort of object in a list, and to allow the same methods to work with
> whatever was in list.


Not really. When the usual argument about the existence (and
justification) of lists & tuples comes along, one common distinction is
that

- tuples contain arbitrary object of varying types, so they are kind
of "records"
- lists should contain uniform objects.

None of this is enforced, but it's good customs to do so & to put it
frankly: if I came along a piece of code that created a list like the
one you presented, I'd say it's a code-smell.

Diez
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Re: [Python-Dev] [python-committers] [RELEASED] Python 3.2 rc 1 R. David Murray Python 0 01-17-2011 02:23 PM
Re: [Python-Dev] [python-committers] [RELEASED] Python 3.2 rc 1 Senthil Kumaran Python 0 01-17-2011 10:31 AM
Re: [Python-Dev] [Python-3000] RELEASED Python 2.6a1 and 3.0a3 Martin v. L÷wis Python 0 03-01-2008 10:51 PM
Re: [Python-Dev] [Python-3000] RELEASED Python 2.6a1 and 3.0a3 Paul Moore Python 0 03-01-2008 10:39 PM
Searching comp.lang.python/python-list@python.org (was: UTF-8) skip@pobox.com Python 0 03-10-2007 02:50 PM



Advertisments