Calculation of a Randomized Algorithm

Question

I have a randomized recursive backtracking algorithm for creating Sudoku puzzles (see here ). It runs fast enough on average, but the worst-case time is unacceptably slow. Here is a histogram of the runtime in milliseconds for 100 tests ("More" is about 200,000 ms!):

I would like to improve the algorithm by simply exposing it after t ms and restarting with a new random seed. To prevent this from repeating indefinitely, I either stopped after trying n, or increased t after every failed attempt. If t is much larger than the median, there is a good chance of getting a much faster start on subsequent attempts.

Questions:

• How to set timeout period t for different processors? Is there a quick and reliable way to compare processor performance before each run? Alternatively, should the processor be adapted to multiple runs, for example, using the average duration of all previous runs? I use it on Android, if relevant.
• Is there a better whole strategy to avoid a long tail in allocating runtime?

Answer 1

Since your algorithm is repetitive, why not set the maximum recursion depth? If a particular random seed results in a recursion depth that you have empirically set to be high enough for you to hit the long tail, interrupt at that point.

According to visual approximation, it seems that after 4500 ms you will not get a significant return on your investment for this seed. Repeat this test, also tracking the recursion depth and see what kind of number it is. However, I would run more than 100 samples.

This solution is independent of processor speed.

Answer 2

• Yes, this is called the confidence interval . By running the algorithm several times in preprocessing (or on the fly), you can determine with confidence x% (where x is the parameter), what is the interval in which the median run-time is located.
  You can reduce the size of the interval by decreasing x or increasing the number of times the algorithm tries. Of course, if you really cannot run the algorithm itself, you can try to compare it on some machine and find the confidence interval (let it be I ) and create some function f(I,s) that gives a choice of time for another algorithm (time s) on another machine (M), predicts what the interval should be for machine M. The search for s is performed in a similar way - using the confidence interval.

• Your approach seems fine, I would probably do the same thing - first I will set up a small factor and increase it after each unsuccessful attempt. Note that this is somehow similar to congestion control in the TCP protocol (from the network area) to find an acceptable packet transfer rate over the network.