Most important speed issues

Question

I am participating in Al Zimmermann's Programming Contest.

http://www.azspcs.net/Contest/SonOfDarts

I have written a recursive algorithm but it takes a long time to run. I was wondering what are the most important things to consider about speed of recursive algorithms. I have made most of the properties global so they don't get allocated every time the recursions step. Is there anything else I can do that will speed up my program without changing my algorithm?

Answer 1

Recusrsion is always slower than itterative. Due to stack/heap/memory aloocation performs slower than most. It is alwyas easier to implement a recusive function in complex algorithms, nut if possible, itterative will be faster.

Answer 2

It depends on the details of your algorithm. If it is tail recursive you could transform it to an iterative algorithm fairly easily.

Answer 3

What language are you using for writing your program? Some languages like Haskell are tailor-made for recursive algorithms while others like Python are not.

How much time is being spent within each function call vs the number of recursive calls out of the function? Too less code being executed within the function itself would certainly lead to performance loss.

Variables on stack are usually much faster than global variables. Consider passing them around from function to function rather than putting them in global.

Unfortunately there isn't enough context in the question to provide better answer.

Recursive algorithms can also be designed in such a way that they are tail recursive. In such a situation, compilers support tail recursion optimization leading to much faster code.

Answer 4

There are probably a lot of overlapping sub-questions in your algorithm and you didn't save the intermediate results for each sub-questions. If you do, your program should be fast enough.

EDIT: I just gave the dart question some thought and felt taking the recursion may not be a good approach to the solution. I did some research in SQL server with the sample given by the question:

create table regions (score int)
insert into regions values (0)
insert into regions values (1)
insert into regions values (2)
insert into regions values (4)
insert into regions values (7)
insert into regions values (11)

create table results (score int)

insert into results
select distinct (s1.score+s2.score+s3.score)
from regions s1, regions s2, regions s3

select * from results

The script clearly reveals a possible solution that can be easily implemented in an imperative programming style, without taking any recursive approach.

Answer 5

Don't assume the problem is with the recursion, or anything else a priori. Just do this, where you find out what's biggest, fix it, and move on to the next. I'm not saying it won't turn out that recursion is the big deal at some point. It's just that chances are very good there are bigger problems you can fix first.

Answer 6

If you can submit compiled code for Intel platforms, then: Collocation of memory content to favor the CPU cache content wins over best classical algorithms in any area. Make sure to use Intel VTune performance analyzer output fed to your linker options to keep bodies of related functions located close in code memory.