[Python-Dev] Document performance requirements?

[James Y Knight]

On Jul 21, 2006, at 12:45 PM, Giovanni Bajo wrote:
> Jason Orendorff wrote:
>
>>> However, I'm also struggling to think of a case other than list vs
>>> deque where the choice of a builtin or standard library data
>>> structure would be dictated by big-O() concerns.
>>
>> OK, but that doesn't mean the information is unimportant.  +1 on
>> making this something of a priority.  People looking for this info
>> should find it in the obvious place.  Some are unobvious. (How  
>> fast is
>> dict.__eq__ on average? Worst case?)
>
> I also found out that most people tend to think of Python's lists as a
> magical data structure optimized for many operations (like a "rope" or
> something complex like that). Documenting that it's just a bare vector
> (std::vector in C++) would be of great help.

Indeed, I was talking to someone a while back who thought that lists  
were magically hashed, in that he did something like:
dictionary = open("/usr/share/dict/words").readlines()

and then expected:
"word" in dictionary

would be fast. And was very surprised when it turned out to be slow a  
linear search of the list. :)

James