Arnaud Delobelle <arno...@googlemail.com> writes: > Terry Reedy <tjre...@udel.edu> writes: > >> On 9/1/2010 11:40 AM, Aahz wrote: >>> I think that any implementation >>> that doesn't have O(1) for list element access is fundamentally broken, >> >> Whereas I think that that claim is fundamentally broken in multiple ways. >> >>> and we should probably document that somewhere. >> >> I agree that *current* algorithmic behavior of parts of CPython on >> typical *current* hardware should be documented not just 'somewhere' >> (which I understand it is, in the Wiki) but in a CPython doc included >> in the doc set distributed with each release. >> >> Perhaps someone or some group could write a HowTo on Programming with >> CPython's Builtin Classes that would describe both the implementation >> and performance and also the implications for coding style. In >> particular, it could compare CPython's array lists and tuples to >> singly linked lists (which are easily created in Python also). >> >> But such a document, after stating that array access may be thought of >> as constant time on current hardware to a useful first approximation, >> should also state that repeated seqeuntial accessess may be *much* >> faster than repeated random accessess. People in the high-performance >> computing community are quite aware of this difference between >> simplified lies and messy truth. Because of this, array algorithms are >> (should be) written differently in Fortran and C because Fortran >> stores arrays by columns and C by rows and because it is usually much >> faster to access the next item than one far away. > > I don't understand what you're trying to say. Aahz didn't claim that > random list element access was constant time, he said it was O(1) (and > that it should be part of the Python spec that it is).
Uhm, O(1) /is/ constant time, see page 45 of Introduction to Algorithms, 2nd edition. -- John Bokma j3b Blog: http://johnbokma.com/ Facebook: http://www.facebook.com/j.j.j.bokma Freelance Perl & Python Development: http://castleamber.com/ -- http://mail.python.org/mailman/listinfo/python-list
