4 ms·
Since the post mentions it, can someone provide a summary of the asymptotic runtime of different python list operations? I have no idea how python lists are imp
by thurn 15y ago
Since the post mentions it, can someone provide a summary of the asymptotic runtime of different python list operations? I have no idea how python lists are implemented.
- MichaelSalib 15y agoThey're implemented like C++ vectors or Java ArrayLists. a[x] is O(1) and so is a.append. del a[x] is O(n) unless x==-1.
- algorias 15y agoCpython lists are self-resizing arrays IIRC. That makes lookups O(1), insert / remove at the end O(1) amortized, insert / remove anywhere else O(n). In short: append, extend and pop methods are efficient.
- andrewcooke 15y agothey're described here - http://wiki.python.org/moin/TimeComplexity http://wiki.python.org/moin/TimeComplexity (as others have said, they're what you'd expect for an amortized dynamic array that expands proportional to the contents)