In article <0233137f$0$8244$c3e8...@news.astraweb.com>,
Steven D'Aprano wrote:
>On Sun, 31 May 2009 12:08:33 +0100, Arnaud Delobelle wrote:
>
>> Anyway, it's good to know that quicksort is O(n^2) in the worst case -
>> and that this worst case can crop up very easily in some situations,
>> especi
In article <003e1491$0$9723$c3e8...@news.astraweb.com>,
Steven D'Aprano wrote:
>On Sun, 31 May 2009 07:24:09 +0100, Arnaud Delobelle wrote:
>>
>> AFAIK, 'complexity' means 'worst case complexity' unless otherwise
>> stated.
>
>No, it means "average or typical case" unless otherwise specified.
>C
Steven D'Aprano wrote:
On Sun, 31 May 2009 12:08:33 +0100, Arnaud Delobelle wrote:
Anyway, it's good to know that quicksort is O(n^2) in the worst case -
and that this worst case can crop up very easily in some situations,
especially if not too much care has been taken implementing it.
The na
On Sun, 31 May 2009 12:08:33 +0100, Arnaud Delobelle wrote:
> Anyway, it's good to know that quicksort is O(n^2) in the worst case -
> and that this worst case can crop up very easily in some situations,
> especially if not too much care has been taken implementing it.
The naive quicksort algorit
Arnaud Delobelle wrote:
Steven D'Aprano writes:
On Sun, 31 May 2009 07:24:09 +0100, Arnaud Delobelle wrote:
AFAIK, 'complexity' means 'worst case complexity' unless otherwise
stated.
No, it means "average or typical case" unless otherwise specified.
I think you both are standing on opposi
Steven D'Aprano writes:
> On Sun, 31 May 2009 07:24:09 +0100, Arnaud Delobelle wrote:
>
>> AFAIK, 'complexity' means 'worst case complexity' unless otherwise
>> stated.
>
> No, it means "average or typical case" unless otherwise specified.
> Consult almost any comp sci text book and you'll see h
On Sun, 31 May 2009 07:24:09 +0100, Arnaud Delobelle wrote:
> AFAIK, 'complexity' means 'worst case complexity' unless otherwise
> stated.
No, it means "average or typical case" unless otherwise specified.
Consult almost any comp sci text book and you'll see hash tables with
chaining (like Pyth
Piet van Oostrum writes:
>> Arnaud Delobelle (AD) wrote:
>
>>AD> Piet van Oostrum writes:
> Aaron Brady (AB) wrote:
>>AB> I am writing a mapping object, and I want to ask about the details of
>>AB> __hash__ and __eq__. IIUC if I understand correctly, the Python
>>AB> dict's
> Arnaud Delobelle (AD) wrote:
>AD> Piet van Oostrum writes:
Aaron Brady (AB) wrote:
>>>
>AB> I am writing a mapping object, and I want to ask about the details of
>AB> __hash__ and __eq__. IIUC if I understand correctly, the Python
>AB> dict's keys' hash codes are looked up firs
On 2009-05-30 17:29, Terry Reedy wrote:
Aaron Brady wrote:
I am writing a mapping object, and I want to ask about the details of
__hash__ and __eq__. IIUC if I understand correctly, the Python
dict's keys' hash codes are looked up first in O( 1 ), then all the
matching hash entries are compared
Aaron Brady wrote:
I am writing a mapping object, and I want to ask about the details of
__hash__ and __eq__. IIUC if I understand correctly, the Python
dict's keys' hash codes are looked up first in O( 1 ), then all the
matching hash entries are compared on equality in O( n ). That is,
the has
Piet van Oostrum writes:
>> Aaron Brady (AB) wrote:
>
>>AB> I am writing a mapping object, and I want to ask about the details of
>>AB> __hash__ and __eq__. IIUC if I understand correctly, the Python
>>AB> dict's keys' hash codes are looked up first in O( 1 ), then all the
>>AB> matching ha
> Aaron Brady (AB) wrote:
>AB> I am writing a mapping object, and I want to ask about the details of
>AB> __hash__ and __eq__. IIUC if I understand correctly, the Python
>AB> dict's keys' hash codes are looked up first in O( 1 ), then all the
>AB> matching hash entries are compared on equali
On May 30, 12:11 pm, Dennis Lee Bieber wrote:
> On Sat, 30 May 2009 11:20:47 -0700 (PDT), Aaron Brady
> declaimed the following in
> gmane.comp.python.general:
>
> > P.S. I always feel like my posts should start like, "A mapping object
> > am writing I." Not too many verbs you can do that with
I am writing a mapping object, and I want to ask about the details of
__hash__ and __eq__. IIUC if I understand correctly, the Python
dict's keys' hash codes are looked up first in O( 1 ), then all the
matching hash entries are compared on equality in O( n ). That is,
the hash code just really na
15 matches
Mail list logo
