[Python-Dev] Document performance requirements? (original) (raw)

James Y Knight foom at fuhm.net
Fri Jul 21 19:48:28 CEST 2006

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

More information about the Python-Dev mailing list