Performance: sets vs dicts.

[Aahz]

In article <mailman.239.1283257496.29448.python-list at python.org>,
Jerry Hill  <malaclypse2 at gmail.com> wrote:
>On Mon, Aug 30, 2010 at 7:42 PM, Aahz <aahz at pythoncraft.com> 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 making promises
>about time complexity in the official docs, since that would make
>those numbers part of the language, and thus binding on other
>implementations.

I'm thoroughly aware of that page and updated it yesterday to make it
easier to find.  ;-)

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 and lists?  Dicts that were not O(1) for access
with non-pathological hashing?  That we would accept sets having O()
performance worse than dicts?

I suggest that we should agree on these guarantees and document them in
the core.
-- 
Aahz (aahz at pythoncraft.com)           <*>         http://www.pythoncraft.com/

"...if I were on life-support, I'd rather have it run by a Gameboy than a
Windows box."  --Cliff Wells