Deterministic time/space for an algorithm?

[Coolphreak]

can someone point me to some resources to help find deterministic time and space for algorithms? Is there any software I can download which will help me determine these? Also is there any software which will help me come up with a growth function? Perhaps plotting data etc.

 

[Coolphreak]

bump...
is there any software i can use to maybe get a graph to predict how computing time and resources needed change as larger inputs are put in?

 

[christianjb]

You want to know how long an arbitrary piece of software takes to run?

That's impossible (if I understand the Q properly).

 

[Coolphreak]

well, I'm basically trying to determine how efficient an algorithm I wrote is, how it scales, etc...If there is any way to "experimentally" do this, that would be ideal, rather than doing it theoretically.

 

[christianjb]

Yes- you can run it and time how long it takes. Note that your results will depend on your processor, your compiler etc.

It is possible to do theoretical analysis of predicted algorithm efficiencies- but there is no algorithm which will tell you how fast another arbitrary algorithm will run.

 

[CRGreathouse]

Technically, it's impossible.

On a practical level you can get an idea of the complexity by running it at a variety of different inputs. The less uniformly it performs on inputs of the same size, the more times you must run it at each input size, and the more careful you must be to pick problems 'uniformly' and 'at random' whatever those mean for your problem. Average the run times at each size (possibly discarding a high and low element first in case of outliers) and compare the ratios of the run times between sizes. This should give you a good idea of whether the algorithm is (at least) exponential, (at most) linear, or in-between -- this might take 4 or 5 sizes. If your algorithm is polynomial then you might need 10-20 sizes to get a decent idea of the exponent; this may not even be enough if the lower terms have large coefficients.

In doing all this you have to keep particulars about your programin mind. Does it run fundamentally differently on different sizes? For example, if normal inputs are 40-90 bits, the run time might triple between 64 and 65 bits if the program needs to use another variable and/or technique for such 'large' numbers.*

* Can you tell from this sentence that I'm thinking of an exponential-time algorithm I'm using? Even small inputs take forever. I expect the 160 bit input I'm crunching now will take around a week.

 

[Coolphreak]

so, it would be acceptable to basically run a whole bunch of trials, at different inputs (maybe many trials per input size) and then plot it on a graph, do a curve fit, and get some idea of a function of how the algorithm scales?

 

[ytoruno]

if you can recast the algorithm in the form of a turing machine, you can measure complexity. just what does the algorithm do?

 

[Coolphreak]

my algorithm mainly does a bunch of matrix manipulations..in a nutshell. I was thinking of maybe saying each step takes time T and go from there...How would you recast in the form of turing machine?

 

[D H]

You can analyze some algorithms by hand. For example, computing the product of two NxN matrices is an O(N³) operation. Computing the towers of hanoi problem requires exponential time (as far as we know). OTOH, writing a piece of software to analyze software time and space complexity is akin to the solving halting problem. Writing said piece of software would most likely be worth at least one million dollars.

 

[Coolphreak]

hmm let's say if matrix multiplication was the first step of my algorithm, and only performed once, I would assign it time T_1. Let's say I have some loop, after the multiplication, which is performed n times. I would assign this nT_2. So, then I would just add them nT_2 + T_1. Wouldn't this indicate that this example algorithm runs in linear time, O(n) ? Do i have the basic concept correct? or would I assign the matrix multiplication operation O(n^3)? Would this mean that my program would grow at the rate of O(n^3), since this is a faster growth rate than O(n)? Or is the first thing I proposed correct?

 

[KTC]

The order of an algorithm indicate on how the resource (in this case time) grows wrt the growth of the input size. n indicate the size of the resource.

In this case, the matrix multiplication of of your algorithm grows at O(n^3), assuming that this is the fastest growth part of the algorithm, then your algorithm as a whole will be O(n^3).

 

[Coolphreak]

hmm...ok
I'm basically downloaded a library to do linear algebra computations for me, such as matrix manipulations and eigenvalues, and determinants, etc. Looking at the code for the eigenvalue decomposition and such...they seem quite tedious to calculate the growth rate at by hand. I don't think the developer of the library released any info on growth rates of his algorithms. Is there any resource where I can look up the growth rate of certain resource. I ran some "simulation" and I got a general growth rate of each of my algorithms...but this is only empirical.

 

[jim mcnamara]

IF I get what you want, have you considered profiling?

 

[D H]

Consider even the simple problem of computing the product $ABx$, where A and B are nxn matrices and x is an n-vector. There is no difference mathematically between $(AB)x$ and $A(Bx)$. There is a big difference in terms of computational cost. The first, $(AB)x$, requires an nxn matrix multiplication (AB, O(n³)) followed by an nx1 matrix multiplication ((AB)x, O(n²)). The nxn matrix multiplication dominates, making this method an O(n³) operation.

In comparison, the second method, $A(Bx)$, requires two nx1 matrix multiplications. Both operations are O(n²), making this method an O(n²) algorithm.

Since a simple matter of rearranging parentheses in one simple calculation can change an algorithm from O(N³) to O(N²), saying what will happen in a larger chunk of code without seeing said code is kinda silly. There is no way to know in advance tell you how some more complex code will work. Eigenvalues and eigenvectors algorithms are particularly touchy.


Usually I do not care about efficiency unless poor performance whomps me upside the head. Program efficiency tends to work against with every other computer software "ility" (e.g., maintainability, portability, understandability, ...). If performance is an issue, it is very common for the cause of the poor performance to be isolated to a small chunk of code.

 

[KTC]

If performance is an issue, it is very common for the cause of the poor performance to be isolated to a small chunk of code.

And to find out where that small chunk of codes are at, you profile it as suggested above.

 

[Coolphreak]

hmm...my code is written pretty well. I guess the only reason i want to know the complexity is just for the sake of knowing. I think i'll look more into profiling.
thanks

 

[jim mcnamara]

DH I programmed for a living these many years - I disagree. Compilers, in general, do better at optimizing simple code. If you create flaky, hard to read code, the compiler may have issues with it as well.

That isn't usually what optimization is. IMO.

On the other hand your comment about algorithms is, if I read between the lines, correct. Most optimization comes from picking the best algorithm.

Worked on commercial sorting software, and the first thing the software did was to analyze the input stream, then play mix-n-match with different alogorithms. The other optimization was to convert data to an easy to compare - just once on the read-in step.

The only real "trick" in there was to (in C) create unions that allowed comparison on native datatypes - like unsigned int, for example. This kind of stuff is what you probably mean by obfuscating code. And is does make it harder to read, and therefore to support.

This trick meant there was almost always a single opcode on the destination platform that would perform the operations instead of calling something like memcmp or strcmp.

However with a bad algorthm choice the sort operation still ran like a dog. There were ways the users could 'tune' a sort.

 

[D H]

Jim,

I think you misread my post. I said "Program efficiency tends to work against with every other computer software "ility" (e.g., maintainability, portability, understandability, ...). " This is a well-known phenomenon, not just my opinion. I don't have any articles on hand, but I have read several studies of software quality versus performance. Organizations that put an undo emphasis on performance tend to produce flaky, hard-to-read software.

The two biggest problems with flaky, hard-to-read code are that the code is flaky and hard-to-read. In my experience, such "tuned" code is typically low quality, buggy, undocumented, unmaintainable, unverifiable, and almost any other -ility one can think of.

I only worry about performance when it becomes an issue. If you have worked in programming for any length of time you should know that most of the CPU time is spent in a relatively small portion of the total code that comprises a program. As mentioned above, profiling is a very good tool for identifying the culprits that cause low performance. And as you mentioned, the poor performance often is the result of a poorly chosen algorithm. Hand tuning of the poor algorithm often accomplishes little other than making the code flaky and hard-to-read. OTOH, simply choosing a better algorithm can accomplish much and will still be high-quality software.