Path: csiph.com!usenet.pasdenom.info!gegeweb.org!newsfeed.kamp.net!newsfeed.kamp.net!newsfeed.freenet.ag!news2.euro.net!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
Return-Path: <davea@davea.name>
X-Original-To: python-list@python.org
Delivered-To: python-list@mail.python.org
X-Spam-Status: OK 0.043
X-Spam-Evidence: '*H*': 0.92; '*S*': 0.00; 'algorithm': 0.04; 'argument': 0.05; 'subject:Python': 0.06; 'correct.': 0.07; 'modifying': 0.07; 'assume': 0.14; 'comparison.': 0.16; 'hashes': 0.16; 'key=': 0.16; 'received:74.208.4.195': 0.16; 'sorting': 0.16; 'unordered': 0.16; 'wrote:': 0.18; 'wed,': 0.18; 'header :User-Agent:1': 0.23; 'replace': 0.24; 'typical': 0.24; 'sort': 0.25; 'post': 0.26; 'subject:/': 0.26; 'values': 0.27; 'header:In- Reply-To:1': 0.27; 'point': 0.28; 'function': 0.29; 'am,': 0.29; "i'm": 0.30; 'work.': 0.31; 'code': 0.31; 'comparison': 0.31; 'equality': 0.31; 'guess': 0.33; 'raw': 0.33; 'could': 0.34; 'something': 0.35; 'case,': 0.35; 'but': 0.35; 'doing': 0.36; 'two': 0.37; 'to:addr:python-list': 0.38; 'pm,': 0.38; 'to:addr:python.org': 0.39; 'how': 0.40; 'dave': 0.60; 'ian': 0.60; 'course': 0.61; 'simply': 0.61; 'different': 0.65; 'here': 0.66; 'determine': 0.67; 'received:74.208': 0.68; 'alone.': 0.84; 'case?': 0.84; 'confusing': 0.84; 'faster.': 0.84; 'partial': 0.84; 'subject:long': 0.84; 'angel': 0.91; '2013': 0.98
Date: Wed, 03 Apr 2013 13:51:26 -0400
From: Dave Angel <davea@davea.name>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:17.0) Gecko/20130308 Thunderbird/17.0.4
MIME-Version: 1.0
To: python-list@python.org
Subject: Re: Performance of int/long in Python 3
References: <mailman.3703.1364248275.2939.python-list@python.org> <87dff083-14d8-4163-89f3-d78a9be6c802@c15g2000vbl.googlegroups.com> <mailman.21.1364931932.3114.python-list@python.org> <3qadncD4-6fcPsbMnZ2dnUVZ_rqdnZ2d@westnet.com.au> <515bbedb$0$29891$c3e8da3$5496439d@news.astraweb.com> <mailman.38.1364970346.3114.python-list@python.org> <iaadnbgQ-smCUMbMnZ2dnUVZ_qydnZ2d@westnet.com.au> <CAPTjJmr9v3gijxoFmhsFM1xw1h4VCaG4K88g03bftouxcG1Q0g@mail.gmail.com> <CALwzid=T6oLzSJ=05vdrQwdpKK8JRaqevOjQhDTojcBo_ynBRw@mail.gmail.com> <mailman.41.1364973874.3114.python-list@python.org> <Y9SdnZYmE9t4QcbMnZ2dnUVZ_gCdnZ2d@westnet.com.au> <a71c7d9b-c0c5-4c6f-ad4f-225ed7ca52aa@kw7g2000pbb.googlegroups.com> <vuOdnV0t7qAPesbMnZ2dnUVZ_rednZ2d@westnet.com.au> <mailman.45.1364984455.3114.python-list@python.org> <gcSdnY65iPFAkMHMnZ2dnUVZ_h2dnZ2d@westnet.com.au> <515C180A.4030302@davea.name> <CALwzidnm-KcMEjtaEteB+YW4Thx8K7WA1xmcWqfrsGrbeeKsOw@mail.gmail.com>
In-Reply-To: <CALwzidnm-KcMEjtaEteB+YW4Thx8K7WA1xmcWqfrsGrbeeKsOw@mail.gmail.com>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
X-Provags-ID: V02:K0:p9ey/6I+SZkzwTRO36Nrt9qIGQERXF3sMP7baM6yetu hQsgcqKXbrbysXu6lBIwVWbAAMUyFJE6pn9b5xt5gh2EZVWXrr RG1qwW0VIYAaKrga8fHNWjwLlK9Ci1howUDkI27rI9ZbMfhby+ o01YHM23FHVpxE2Up5RALVCdyRiPDKJNInhjHTnTu3i62HN8Zh WEJ+im0YYyrJdslC8JOlo6PEKOhAxwnlhkBs2BKMUrY/m+22jg DTvc6lVQv6QxzXaq58bNvegQF4dGbAmam/lUZ9lU1Bpe267iMF xN+cvn6SZ9l6cUtGoVtbV4voW3iD2/ACLmsfnplIRyHYWjGZg= =
X-BeenThere: python-list@python.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: General discussion list for the Python programming language <python-list.python.org>
List-Unsubscribe: <http://mail.python.org/mailman/options/python-list>, <mailto:python-list-request@python.org?subject=unsubscribe>
List-Archive: <http://mail.python.org/pipermail/python-list/>
List-Post: <mailto:python-list@python.org>
List-Help: <mailto:python-list-request@python.org?subject=help>
List-Subscribe: <http://mail.python.org/mailman/listinfo/python-list>, <mailto:python-list-request@python.org?subject=subscribe>
Newsgroups: comp.lang.python
Message-ID: <mailman.70.1365011504.3114.python-list@python.org>
Lines: 23
NNTP-Posting-Host: 2001:888:2000:d::a6
X-Trace: 1365011504 news.xs4all.nl 6845 [2001:888:2000:d::a6]:49236
X-Complaints-To: abuse@xs4all.nl
Xref: csiph.com comp.lang.python:42692

On 04/03/2013 12:30 PM, Ian Kelly wrote:
> On Wed, Apr 3, 2013 at 5:52 AM, Dave Angel <davea@davea.name> wrote:
>> I'm also puzzled.  I thought that the sort algorithm used a hash of all the
>> items to be sorted, and only reverted to a raw comparison of the original
>> values when the hash collided.  Is that not the case?  Or is the code you
>> post here only used when the hash collides?
>
> I think you are mistaken, because I don't see how that could work.  If
> the hashes of two items are different then you can assume they are not
> equal, but sorting requires a partial ordering comparison, not simply
> an equality comparison.  You cannot determine which item is less or
> greater than the other from the hash values alone.
>

You are of course correct.  The particular data that Neil had provided 
might well have had many duplicates, but that won't be the typical case, 
so there's not much point in doing an unordered hash.  I guess I was 
confusing it with the key= argument for modifying sort order, where the 
key function might replace a slow-to-compare data type with something 
faster.

-- 
DaveA