Idea: Algorithm speed testing

[sh0]

Hello!

I am pretty new here, but I have already noticed that after solving a problem, many solvers try to optimize their code to have faster execution times. The only problem is that there is no standard to measure the speed (different pc = different speed). Because of that, for times under a second or so, it is practically pointless to make any comparisons between algorithms. I know that there are some emulators that execute a program at a certain clock speed and measure the execution time. I have no idea whether those emulators can control execution speed of environments like java or not. Since the algorithm should be the priority, "slow" languages like java should probably be given a little extra clock speed.

I have no idea, if this has been discussed before and I just couldn't find it in forums, but I find that correct time measuring would open up a whole new level of competition. Am I right or wrong here?

Sh0

[joshbowman205]

Im not sure that idea would work on project euler. It would be helpful to find equivalent times given the differences in languages and processors but the competition isnt built around it. Because the solution works to a given limit it may contain deductions specific to that, to the extreme that it may just output the answer.

TopCoder have implemented such a system but thinking about the implementation gives me headaches!

[sh0]

I have to agree. Giving points or some rank for fastest code can't be done. In the end it would mean that every piece of code would have to be checked manually for "optimizations" like printing out the answer. The second thing that happens is that nobody releases his code to public if it is quick enough and thats the last thing that should happen on this site.

The thing that I'm thinking is that people can give a standardized time count for their uploaded code themselves. It certainly puts different algorithms in perspective. It is really hard to figure out which code is better unless you bench all of them yourself. The competition part would be about earning respect for thinking faster algorithms. Giving a false time count would be totally pointless since fast codes will probably be tested by others anyways.

[rayfil]

The competition part would be about earning respect for thinking faster algorithms.

The identical algorithm written in different programming languages (and even using the same language but with different compilers) can vary VERY widely. That alone makes it almost impossible to single out the fastest algo. However, when comparing one's algo taking a few seconds to someone else's algo running under 1 ms, it's not difficult to admit that the latter must be superior regardless of the language and hardware used.

[sh0]

Again, I have to agree. Looks like perfect algorithm timing is not possible :/ Multiplying result time with a coefficient for each compiler/language would probably not work either, because elementary operations cost different amounts of time on different systems. So the next thing I can think of would be to count the different elementary operations required to do the algorithm. That is again strongly dependent on compiler and won't give usable results without knowing the cost of different elementary operations again.

My practical problem was that one java algo I copied from forums ran two times faster than the poster said it ran. It means that there could probably be differences a lot more than just two times. If the running time were even approximate to some standard, then it would help in algo evaluation.

I think I have pretty much concluded that there exists no such thing as universally best algo anyways, so there is no point of finding it.

[stijn263]

extension problems usually give an idea about algorithm speed. for instance, in problem 173, some algorithms can solve for n=10¹⁸ in under a minute, while others would take over a year in any language. so i guess that answers the question to what algorithm is faster

[joshbowman205]

Thats an idea, maybe the best comparison is asymptotic performance. If the algorithm is of a different order that will be more significant than the difference in language.

[joehypo]

Knuth in The Art of Computer Programming vol 2 pages 369-370 discusses an algorithm for factorizing which has pretty good speed but sometimes fails to determine the factors. How would you rate it?

Let us consider problem #61 and two possible algorithms for its solution
algorithm A: runs in 200 milliseconds on machine X and takes 1 hour to code
algorithm B: runs in 4 milliseconds on machine X and takes 3 hours to code

Both algorithms give the correct answer. Algorithm A also uses less RAM.

In my opinion, algorithm A is more efficient. Consider giving the pseudocode for each algorithm to two groups of students. Which group will have the solution sooner (on average)?

The code will not be run enough times to compensate for the longer development time.

Problem 61 might scale to the point where algorithm B is superior but as the problem is stated that is not the case.

[daniel.is.fischer]

Knuth in The Art of Computer Programming vol 2 pages 369-370 discusses an algorithm for factorizing which has pretty good speed but sometimes fails to determine the factors. How would you rate it?

Good question.

Let us consider problem #61 and two possible algorithms for its solution
algorithm A: runs in 200 milliseconds on machine X and takes 1 hour to code
algorithm B: runs in 4 milliseconds on machine X and takes 3 hours to code

Both algorithms give the correct answer. Algorithm A also uses less RAM.

In my opinion, algorithm A is more efficient. Consider giving the pseudocode for each algorithm to two groups of students. Which group will have the solution sooner (on average)?

The code will not be run enough times to compensate for the longer development time.

Problem 61 might scale to the point where algorithm B is superior but as the problem is stated that is not the case.

You raise some excellent points. However, if one wants to rate the efficiency/quality of an algorithm, one has to pick a setting. You can assume a run-once scenario, in which case you would measure developing time + running time and A would be the clear winner. Or you can suppose a write-once, run-often-with-different-inputs-in-a-fixed-range scenario, then if 'often' and the range are large enough, B wins. Or you could judge the asymptotic complexity, which might be less relevant to real-life situations, but is at least an objective measure -- well, more or less, you can still choose whether you measure worst-case complexity or average complexity.
For Project Euler, the first and third setting would be interesting, the second rather less. I tend to find the third most interesting.

[hk]

From the Project Euler about page:

I've written my program but should it take days to get to the answer?

Absolutely not! Each problem has been designed according to a "one-minute rule", which means that although it may take several hours to design a successful algorithm with more difficult problems, an efficient implementation will allow a solution to be obtained on a modestly powered computer in less than one minute.

Does it matter if it takes more than one minute to solve?
Of course not, but that should provide the impetus to return to the problem and see how you can improve your approach. But remember that once you've solved a particular problem you will be able to access a thread relating to that problem and it is here that you may be able to pick some tips from others that have solved it.

All I can get out of this is: Project Euler problems (especially the lower numbered ones) are not meant as "once the answer is obtained in as little time as possible from starting to read the problem statement I'm finished with it".
If one is really interested in a problem one will start to refine and extend. However that's a very personal affair and a mark: "this is the best solution" is contradictory to that.