Performance: sets vs dicts.

[Robert Kern]

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".

-- 
Robert Kern

"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