FAQ

Peter Hansen wrote:

Erik Max Francis wrote:
JB wrote:
...
quantitative information about where the bottlenecks truly are. This
concept is especially powerful in a high-level language like Python; the
very choice of using Python means that you're willing to trade raw speed
for flexibility. If you're overconcerned with squeezing every last bit
of CPU power right from the start, then Python (or any other high-level
language) was probably not a good choice of languages.

Well stated, although a note about changing algorithms generally
providing the most significant speedups might be in order. Even
with Python, picking a better algorithm can produce huge gains.
(This does not, of course, apply to a small idiomatic choice such
as this thread was about.)

Highly applicable to this thread. Deleting the first item of a Python
list or C++ vector is an O(n) operation - proportional to the number of
items in the list. If you do that for every item in the list it is
O(n^2) - proportional to the square.

The thing about O(n^2), and any complexity higher than that, is that
there are many values of N that are small enough for N items to easily
fit into memory, but large enough to make the program run for days and
days and days and days.

O(n^2) is bad, unless you know that n will always be small.

So, if performance is a problem, the OP should consider reworking the
code. For instance, if the original code was:

while myList:
# Do Something with the first element
del myList[0]

Then it should be much better to go:

myList.reverse()
while myList:
# Do Something with the last element
del myList[len(myList)-1]

This changes it from O(n^2) to O(n), which could make it run thousands
of times faster.

Premature optimization is the root of all evil, but O(n^2) is pretty
darned evil too!

Of course, the OP's code may not be so easily reworked as my simple example.

Search Discussions

Discussion Posts

Previous

Follow ups

Related Discussions

Discussion Navigation
viewthread | post
posts ‹ prev | 8 of 17 | next ›
Discussion Overview
grouppython-list @
categoriespython
postedOct 2, '02 at 10:34p
activeOct 3, '02 at 10:48p
posts17
users11
websitepython.org

People

Translate

site design / logo © 2022 Grokbase