Speed of string += string
Martin v. Löwis
martin at v.loewis.de
Sun Apr 13 12:06:21 CEST 2003
Alex Martelli <aleax at aleax.it> writes:
> The crucial difference is that Python dicts are hashtables, while the
> std::map in the standard library of C++ can't be, because it's based
> on an order relationship, NOT on hashing. So, std::map has an order,
> but its O(...) performance just can't be as good as a dict's.
Nit-pickers (like myself) will point out that the complexity of a
hash-table depends on the distribution of the hash function (in
addition to depending on the complexity of the hash function). With a
carefully-chosen hash O(1) function, all dictionary operations will be
O(n). For std::map, O(log n) is the worst-case performance.
More information about the Python-list