optimization question

Peter Hansen peter at engcorp.com
Sun Aug 11 12:20:27 EDT 2002

Andrew Koenig wrote:
> If s and t are strings, and I evaluate an expression of the form
>     s[i:j] == t
> can I count on the implementation not to form s[i:j] as a new
> substring?  Suppose, for instance, that s is many megabytes
> long, i and j are far apart, and t is very short.  Can I assume
> that the execution time for this comparison will be no worse
> than O(len(t)), or must I assume O(j-1)?

If you mean O(j-i) above, then yes, you must assume it.  Nowhere
are there guarantees that all implementations will perform this
work in O(len(t)).  

Anyway, you are optimizing before you've profiled and determined
you have a problem.  Just write the code in the most simple and
maintainable way you know how and save your time.  If you don't
like the performance when it's working, "import profile" and
resolve the bottlenecks.  "Premature optimization is the root of
all evil in programming." -Knuth


More information about the Python-list mailing list