When Python outruns C++ ...

Isaac To kkto at csis.hku.hk
Tue Apr 1 14:56:30 CEST 2003

>>>>> "Alex" == Alex Martelli <aleax at aleax.it> writes:

    Alex> Jacek Generowicz wrote: ...
    >> Will you make this code public ?

    Alex> Sure, it's nothing special -- just a tiny, simple example.

    Alex> Here's the naivest Python I could come up with for the task
    Alex> (Python 2.3 given the use of enumerate, but that's easy to remove
    Alex> if you want, of course):

The algorithms have different time order.  The Python version is around O(n)
due to the use of hashed dictionary, the C++ version is O(n log n) due to
the use of tree maps.  This is a two-side sword, though: I usually want to
have a predecessor operation in Python but then remember that it is
impossible unless I use some custom dictionaries.  BTW, nearly all STL
implementation of STL does support hashed implementation, the problem is
just that the standard committee is waiting for C++ implementations to catch
up with the current standard before rolling out new things into the library.


More information about the Python-list mailing list