Steven D'Aprano wrote: > > Of course. I was just trying to make a point about string accumulation being > > O(n) and not O(n^2). > > But according to Fredrik, string accumulation is still quadratic, even > with the optimizations added to Python 2.4. Quoting: > > "it only means that if the interpreter can make sure that else is > using the target string, it's modified in place. > > however, the string type doesn't use overallocation (beyond the > 8-byte alignment provided by the memory allocator), so this fix > only avoids extra copying in a few specific cases. O(n*n/8) is > still quadratic..." > > I presume Fredrik meant to say "nothing else".
correct. the only way to get amortized O(n) behaviour is by adding small strings to the end of a larger string, and hope that the memory allocator can satisfy all reallocations without too much copying. the list implementation, in contrast, uses controlled overallocation and can therefore guarantee amortized O(n) even if realloc always fails to reallocate in place. </F> -- http://mail.python.org/mailman/listinfo/python-list
