My usual procedure for optimizing something is:
- Profile it, to find out which part of the problem is
taking the most time. (Sometimes the problem's a single
algorithm, in which case this isn't really necessary.)
- Estimate the asymptotic bound of that bit of the
problem. (Yet another excellent real-world use for those
icky awful theory courses you were forced to take in
- Try to make the algorithm faster. Sometimes this just
isn't possible; IIRC, you can't get a general sort on a
single-processor machine faster than O(n log n). But you
can often simplify the problem: put a few restrictions on
what you sort, and you can get down to O(n). Nobody knows
how to solve the travelling salesman problem in less than
exponential time, but if you don't need a perfect
solution, just one no worse than twice as bad as optimal,
you can do it in polynomial (cubic, IIRC) time.
- Repeat until you run out of relevant sub-problems.
- If it still isn't fast enough, profile it again; this
time, look for lines and functions that get executed most
often, and try to slim those down. If your program's data
set is particularly small, this might be more important
than step 2; then again, if n is small, your program's
probably "fast enough".
Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
Read Where should I post X? if you're not absolutely sure you're posting in the right place.
Please read these before you post! —
Posts may use any of the Perl Monks Approved HTML tags:
You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
- a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
Link using PerlMonks shortcuts! What shortcuts can I use for linking?
See Writeup Formatting Tips and other pages linked from there for more info.
| & || & |
| < || < |
| > || > |
| [ || [ |
| ] || ] ||