Time limit on recursive methods in java

Question

I am trying to write a search (ids) program in java that halts if 3 minutes have passed and a solution has not been found. I tried using a while loop, but the loop continued even once the solution had been found but the time limit was still going, so I changed it to using an Executor service, but that also keeps repeating. I don't think I have the Executor working right. What am I doing wrong??

public void search(Node head) throws InterruptedException, ExecutionException{
    solution = new Stack<Node>();
    allnodes = 0;


    ExecutorService es = Executors.newSingleThreadExecutor();
    Future f = es.submit(new Runnable() {
        @Override
        public void run() {
            startTime = System.nanoTime();
            while(!Thread.interrupted()) {
                endTime = searching(start);
            }
            long time = endTime - startTime;
            System.out.printf("Finished task after %,d ns%n"+ time);
        }
    });
    try {// stops if the task completes.
        f.get(1, TimeUnit.SECONDS); 
    } catch (TimeoutException e) {
        f.cancel(true);
    }
    es.shutdown();



}



public long searching(Node head){

    solution.push(head);

        if((head.getRow() == goal.getRow()) && (head.getCol() == goal.getCol())){
            System.out.println("solution");
            endTime = System.currentTimeMillis();
            solution.push(head);
            allnodes = allnodes+1;

            return endTime; //here it returns the end time to then be printed out but the loop keeps going?



        }
        //recursively calling
        int r = head.getRow();
        int c = head.getCol();

        if((r-1 >-1 )){
            if(gr.getstate(r - 1, c) == State.Unvisited){       
                allnodes = allnodes+1;
                System.out.println("go north");
                gr.updatemap(r - 1, c);
                solution.push(head);
                searching(head.getN(head));

            }
        }
        if(r+1 < (map[1].length-1)){
            if(gr.getstate(r + 1, c) == State.Unvisited){               
                System.out.println("go south");
                allnodes = allnodes+1;
                gr.updatemap(r + 1, c);
                solution.push(head);
                head = head.getS(head);
                searching(head);    
            }
        }
        if(c+1 < map.length-1){
            if(gr.getstate(r , c +1) == State.Unvisited){
                allnodes = allnodes+1;
                System.out.println("go east");
                gr.updatemap(r , c +1);
                solution.push(head);
                head = head.getE(head);
                searching(head);
            }   
        }
        if(c -1 > -1){
            if (gr.getstate(r, c-1) == State.Unvisited){
                System.out.println("go west");
                allnodes = allnodes+1;
                gr.updatemap(r, c-1);
                solution.push(head);
                head = head.getW(head);
                searching(head);
            }   
        }


        return endTime;

}

looks like a dup of: http://stackoverflow.com/questions/2758612/executorservice-that-interrupts-tasks-after-a-timeout — Amir Afghani, Feb 20 '15 at 19:56
I borrowed the executor from that question and it didn't work for my program, I wondered what I was doing wrong. — user3369920, Feb 20 '15 at 20:55

score 0 · Answer 1 · answered Feb 20 '15 at 19:41

0

Shutting down an ExecutorService prevents new tasks, it does not stop existing ones. Have you tried just using something like:

long t1 = System.getCurrentTimeMillis();
for (...) {
    // your code

    if (System.CurrentTimeMillis()-t1 > 1000*60*3) {
        break; // or even return
    }
}

You can put a similar if statement anywhere you'd like. It will slow down your computation, but it'll cause it to stop as you'd expect.

answered Feb 20 '15 at 19:41

mk.

11,360
6
40
54

It seemed that the timer kept reinitiating when I did the recursive call and the timer was inside that method that was being recursively called, or it didn't stop when the methods were separated and the second was the recursive caller. – user3369920 Feb 20 '15 at 19:51
Pass your original time t1 into each recursive method call without changing or resetting it, or make it a field. – mk. Feb 20 '15 at 19:56

score 0 · Answer 2 · answered Feb 20 '15 at 20:07

You cannot end recursion immediately (well unless you throw an Exception but I do not recommend this). Even if the desired time passes execution service cannot just kill the task that was not finished. I recommend counting the time inside the recursion and when the time passes just return out of function - it will still take some time to break out of all the recursive calls. Or use the stack instead of the recursion if it is possible, you can jump out of function immediately after the time limit.

Time limit on recursive methods in java

2 Answers2