Performance: sets vs dicts.

[John Bokma]

Arnaud Delobelle <arnodel at googlemail.com> writes:

> Terry Reedy <tjreedy at udel.edu> 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.
>>
>> I agree that *current* algorithmic behavior of parts of CPython on
>> typical *current* hardware should be documented not just 'somewhere'
>> (which I understand it is, in the Wiki) but in a CPython doc included
>> in the doc set distributed with each release.
>>
>> Perhaps someone or some group could write a HowTo on Programming with
>> CPython's Builtin Classes that would describe both the implementation
>> and performance and also the implications for coding style. In
>> particular, it could compare CPython's array lists and tuples to
>> singly linked lists (which are easily created in Python also).
>>
>> 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*
>> faster than repeated random accessess. People in the high-performance
>> computing community are quite aware of this difference between
>> simplified lies and messy truth. Because of this, array algorithms are
>> (should be) written differently in Fortran and C because Fortran
>> stores arrays by columns and C by rows and because it is usually much
>> faster to access the next item than one far away.
>
> 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 part of the Python spec that it is).

Uhm, O(1) /is/ constant time, see page 45 of Introduction to Algorithms,
2nd edition.

-- 
John Bokma                                                               j3b

Blog: http://johnbokma.com/    Facebook: http://www.facebook.com/j.j.j.bokma
    Freelance Perl & Python Development: http://castleamber.com/