Performance: sets vs dicts.
robert.kern at gmail.com
Thu Sep 2 00:30:31 CEST 2010
On 9/1/10 4:40 PM, John Bokma wrote:
> Arnaud Delobelle<arnodel at googlemail.com> writes:
>> Terry Reedy<tjreedy at udel.edu> 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*
>>> 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.
While we often use the term "constant time" to as a synonym for O(1) complexity
of an algorithm, Arnaud and Terry are using the term here to mean "an
implementation takes roughly the same amount of wall-clock time every time".
"I have come to believe that the whole world is an enigma, a harmless enigma
that is made terrible by our own mad attempt to interpret it as though it had
an underlying truth."
-- Umberto Eco
More information about the Python-list