On 9/3/10 12:08 PM, John Bokma wrote:
Terry Reedy writes:
On 9/1/2010 8:11 PM, John Bokma wrote:
[...]
Right. And if 'small values of n' include all possible values, then
rejecting a particular O(log n) algorithm as 'unacceptable' relative
to all O(1) algorithms is pretty absurd.
I have
Terry Reedy writes:
> On 9/1/2010 8:11 PM, John Bokma wrote:
[...]
> Right. And if 'small values of n' include all possible values, then
> rejecting a particular O(log n) algorithm as 'unacceptable' relative
> to all O(1) algorithms is pretty absurd.
I have little time, but want to reply to th
On 09/02/2010 02:47 PM, Terry Reedy wrote:
> On 9/1/2010 10:57 PM, ru...@yahoo.com wrote:
>
>> So while you may "think" most people rarely read
>> the docs for basic language features and objects
>> (I presume you don't mean to restrict your statement
>> to only sets), I and most people I know *do*
Terry Reedy writes:
> On 9/1/2010 8:11 PM, John Bokma wrote:
[...]
Uhm, O(1) /is/ constant time, see page 45 of Introduction to Algorithms,
2nd edition.
>
> Given that the Wikipedia article references that section also, I
> wonder if it really disagrees with the definition above.
In si
On 9/1/2010 8:11 PM, John Bokma wrote:
Terry Reedy writes:
On 9/1/2010 5:40 PM, John Bokma wrote:
[..]
Yes, I switched, because 'constant time' is a comprehensible claim
that can be refuted and because that is how some will interpret O(1)
(see below for proof;-).
You make it now sound as
On 9/1/2010 10:57 PM, ru...@yahoo.com wrote:
So while you may "think" most people rarely read
the docs for basic language features and objects
(I presume you don't mean to restrict your statement
to only sets), I and most people I know *do* read
them. And when read them I expect them, as any go
On 09/01/2010 04:51 PM, Raymond Hettinger wrote:
> On Aug 30, 6:03 am, a...@pythoncraft.com (Aahz) wrote:
>> That reminds me: one co-worker (who really should have known better ;-)
>> had the impression that sets were O(N) rather than O(1). Although
>> writing that off as a brain-fart seems approp
Robert Kern writes:
> On 9/1/10 4:40 PM, John Bokma wrote:
>> Arnaud Delobelle writes:
>>
>>> Terry Reedy writes:
[...]
>>> I don't understand what you're trying to say. Aahz didn't claim that
>>> random list element access was constant time, he said it was O(1) (and
>>> that it should be pa
Terry Reedy writes:
> On 9/1/2010 5:40 PM, John Bokma wrote:
[..]
> Yes, I switched, because 'constant time' is a comprehensible claim
> that can be refuted and because that is how some will interpret O(1)
> (see below for proof;-).
You make it now sound alsof this interpretation is not correc
On 9/1/2010 5:40 PM, John Bokma wrote:
Arnaud Delobelle writes:
Terry Reedy writes:
On 9/1/2010 11:40 AM, Aahz wrote:
I think that any implementation
that doesn't have O(1) for list element access is fundamentally broken,
Whereas I think that that claim is fundamentally broken in multipl
On Aug 30, 6:03 am, a...@pythoncraft.com (Aahz) wrote:
> That reminds me: one co-worker (who really should have known better ;-)
> had the impression that sets were O(N) rather than O(1). Although
> writing that off as a brain-fart seems appropriate, it's also the case
> that the docs don't really
On 9/1/10 4:40 PM, John Bokma wrote:
Arnaud Delobelle writes:
Terry Reedy writes:
But such a document, after stating that array access may be thought of
as constant time on current hardware to a useful first approximation,
should also state that repeated seqeuntial accessess may be *much*
Arnaud Delobelle writes:
> Terry Reedy writes:
>
>> On 9/1/2010 11:40 AM, Aahz wrote:
>>> I think that any implementation
>>> that doesn't have O(1) for list element access is fundamentally broken,
>>
>> Whereas I think that that claim is fundamentally broken in multiple ways.
>>
>>> and we shou
On 9/1/2010 2:42 AM, Paul Rubin wrote:
Terry Reedy writes:
Does anyone seriously think that an implementation should be rejected
as an implementation if it intellegently did seq[n] lookups in
log2(n)/31 time units for all n (as humans would do), instead of
stupidly taking 1 time unit for all n<
Terry Reedy writes:
> On 9/1/2010 11:40 AM, Aahz wrote:
>> I think that any implementation
>> that doesn't have O(1) for list element access is fundamentally broken,
>
> Whereas I think that that claim is fundamentally broken in multiple ways.
>
>> and we should probably document that somewhere.
On 9/1/2010 11:40 AM, Aahz wrote:
I think that any implementation
that doesn't have O(1) for list element access is fundamentally broken,
Whereas I think that that claim is fundamentally broken in multiple ways.
and we should probably document that somewhere.
I agree that *current* algorith
Aahz, 01.09.2010 17:40:
I still think that making a full set of
algorithmic guarantees is a Bad Idea, but I think that any implementation
that doesn't have O(1) for list element access is fundamentally broken,
and we should probably document that somewhere.
+1
Stefan
--
http://mail.python.org
In article ,
Jerry Hill wrote:
>On Tue, Aug 31, 2010 at 10:09 AM, Aahz wrote:
>>
>> I suggest that we should agree on these guarantees and document them in
>> the core.
>
>I can't get to the online python-dev archives from work (stupid
>filter!) so I can't give you a link to the archives, but th
Lie Ryan, 01.09.2010 15:46:
On 09/01/10 00:09, Aahz wrote:
However, I think there are some rock-bottom basic guarantees we can make
regardless of implementation. Does anyone seriously think that an
implementation would be accepted that had anything other than O(1) for
index access into tuples a
On 09/01/10 00:09, Aahz wrote:
> In article ,
> Jerry Hill wrote:
>> On Mon, Aug 30, 2010 at 7:42 PM, Aahz wrote:
>>>
>>> Possibly; IMO, people should not need to run timeit to determine basic
>>> algorithmic speed for standard Python datatypes.
>>
>> http://wiki.python.org/moin/TimeComplexity t
Terry Reedy writes:
> Does anyone seriously think that an implementation should be rejected
> as an implementation if it intellegently did seq[n] lookups in
> log2(n)/31 time units for all n (as humans would do), instead of
> stupidly taking 1 time unit for all n < 2**31 and rejecting all larger
>
On 8/31/2010 10:09 AM, Aahz wrote:
In article,
Jerry Hill wrote:
On Mon, Aug 30, 2010 at 7:42 PM, Aahz wrote:
Possibly; IMO, people should not need to run timeit to determine basic
algorithmic speed for standard Python datatypes.
http://wiki.python.org/moin/TimeComplexity takes a stab at i
On Tue, Aug 31, 2010 at 10:09 AM, Aahz wrote:
> I suggest that we should agree on these guarantees and document them in
> the core.
I can't get to the online python-dev archives from work (stupid
filter!) so I can't give you a link to the archives, but the original
thread that resulted in the cre
On 31/08/2010 15:09, Aahz wrote:
I suggest that we should agree on these guarantees and document them in
the core.
I suspect that documenting them will be the easy part ;)
--
http://mail.python.org/mailman/listinfo/python-list
Jerry Hill, 31.08.2010 14:24:
On Mon, Aug 30, 2010 at 7:42 PM, Aahz wrote:
Possibly; IMO, people should not need to run timeit to determine basic
algorithmic speed for standard Python datatypes.
http://wiki.python.org/moin/TimeComplexity takes a stab at it. IIRC,
last time this came up, there
In article ,
Jerry Hill wrote:
>On Mon, Aug 30, 2010 at 7:42 PM, Aahz wrote:
>>
>> Possibly; IMO, people should not need to run timeit to determine basic
>> algorithmic speed for standard Python datatypes.
>
>http://wiki.python.org/moin/TimeComplexity takes a stab at it. IIRC,
>last time this c
On Mon, Aug 30, 2010 at 7:42 PM, Aahz wrote:
> Possibly; IMO, people should not need to run timeit to determine basic
> algorithmic speed for standard Python datatypes.
http://wiki.python.org/moin/TimeComplexity takes a stab at it. IIRC,
last time this came up, there was some resistance to makin
Paul Rubin writes:
> a...@pythoncraft.com (Aahz) writes:
>> Possibly; IMO, people should not need to run timeit to determine basic
>> algorithmic speed for standard Python datatypes.
>
> Indeed. Alex Stepanov (designer of C++ Standard Template Library) was
> emphatic that algorithm complexity as
a...@pythoncraft.com (Aahz) writes:
> Possibly; IMO, people should not need to run timeit to determine basic
> algorithmic speed for standard Python datatypes.
Indeed. Alex Stepanov (designer of C++ Standard Template Library) was
emphatic that algorithm complexity assertions should be part of the
In article <878w3ogpvq@benfinney.id.au>,
Ben Finney wrote:
>a...@pythoncraft.com (Aahz) writes:
>>
>> That reminds me: one co-worker (who really should have known better ;-)
>> had the impression that sets were O(N) rather than O(1).
>
>For settling exactly this kind of confusion, Python's st
a...@pythoncraft.com (Aahz) writes:
> That reminds me: one co-worker (who really should have known better ;-)
> had the impression that sets were O(N) rather than O(1).
For settling exactly this kind of confusion, Python's standard library
comes with a module, the ‘timeit’ module. Your co-worker
a...@pythoncraft.com (Aahz) writes:
> That reminds me: one co-worker (who really should have known better ;-)
> had the impression that sets were O(N) rather than O(1). Although
> writing that off as a brain-fart seems appropriate, it's also the case
> that the docs don't really make that clear, i
In article ,
Raymond Hettinger wrote:
>On Aug 29, 12:12=A0pm, John Nagle wrote:
>>
>> Is the "in" test faster for a dict or a set? Is "frozenset" faster
>> than "set"? Use case is for things like applying "in" on a list of
>> 500 or so words while checking a large body of text.
>
>There is no s
Seth Rees wrote:
> On 08/29/10 14:43, Peter Otten wrote:
>> John Nagle wrote:
>>
>>> Is the "in" test faster for a dict or a set?
>>> Is "frozenset" faster than "set"? Use case is
>>> for things like applying "in" on a list of 500 or so words
>>> while checking a large body of text.
>>
>> As
On Aug 29, 12:12 pm, John Nagle wrote:
> Is the "in" test faster for a dict or a set?
> Is "frozenset" faster than "set"? Use case is
> for things like applying "in" on a list of 500 or so words
> while checking a large body of text.
There is no significant difference.
All three are implemen
On 08/29/10 14:43, Peter Otten wrote:
John Nagle wrote:
Is the "in" test faster for a dict or a set?
Is "frozenset" faster than "set"? Use case is
for things like applying "in" on a list of 500 or so words
while checking a large body of text.
As Arnaud suspects: no significant differenc
John Nagle wrote:
> Is the "in" test faster for a dict or a set?
> Is "frozenset" faster than "set"? Use case is
> for things like applying "in" on a list of 500 or so words
> while checking a large body of text.
As Arnaud suspects: no significant difference:
$ python dictperf.py
dict --> 0
John Nagle writes:
>Is the "in" test faster for a dict or a set?
> Is "frozenset" faster than "set"? Use case is
> for things like applying "in" on a list of 500 or so words
> while checking a large body of text.
>
> John Nagle
IIRC Frozensets are implemented m
Is the "in" test faster for a dict or a set?
Is "frozenset" faster than "set"? Use case is
for things like applying "in" on a list of 500 or so words
while checking a large body of text.
John Nagle
--
http://mail.python.org/mailman/listinfo/python-list
39 matches
Mail list logo
