Armin Rigo wrote: > I think that O-wise the current CPython situation should be documented > as a "minimal requirement" for implementations of the language, with > just one exception: the well-documented "don't rely on this" hack in > 2.4 to make repeated 'str += str' amortized linear, for which the 2.3 > quadratic behavior is considered compliant enough. > > I suppose that allowing implementations to provide better algorithmic > complexities than required is fine, although I can think of some > problems with that (e.g. nice and efficient user code that would > perform horribly badly on CPython).
I'm not sure big-O tells the whole truth. For instance, do we want to allow an implementation to use a hash table as underlying type for a list? It would match big-O requirements, but would still be slower than a plain array because of higher overhead of implementation (higher constant factor). And if this is allowed, I would like to find in CPython tutorials and documentations a simple statement like: "to implement the list and match its requirements, CPython choose a simple array as underlying data structure". -- Giovanni Bajo _______________________________________________ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com