When Python outruns C++ ...
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