Another Python rookie trying to port to C/C++ question.

Stephen Horne $$$$$$$$$$$$$$$$$ at $$$$$$$$$$$$$$$$$$$$.co.uk
Fri Sep 26 01:12:41 CEST 2003


On Thu, 25 Sep 2003 15:19:00 -0700, Brian Quinlan <brian at sweetapp.com>
wrote:

>> Well, since I'm not worried about "flexible", have my doubts about the
>> "much slower" part,
>
>Your implementation is O(n) with the number of entries while the Python
>implementation is O(log(n)). If n is small then your implementation
>might be acceptably fast. Can't you just use the STL hash_map template
>class?

Are you sure Python dictionaries are O(log n)? - Remember, they are
based on hashing.

Simple hashing is O(1). Handling of collisions and stuff will affect
that (and I'm no expert on hashing techniques) but I can't help
wondering if you're confusing Pythons hashing with tree-based
techniques.


-- 
Steve Horne

steve at ninereeds dot fsnet dot co dot uk




More information about the Python-list mailing list