Recursion takes long, Android

Question

I need a little assistance regarding my algorithm. I have tried to look for similar questions but couldn't find something that would satisfy me.

I have code that executes very fast (0.3s) in my desktop but when deployed on Android device (not emulator, Samsung S3) it executes really slow, it can take up to a one minute. I would like to know what possibilities do I have to make it run a lot faster, say under 1s.

I have read that heavy recursion in Android can cause memory allocation / GC issues, can it be the case here? How to avoid it? Go iterative?

Code is here:

public class CombinationsQuestion {

public static void main(String[] args) {
    CombinationsQuestion comb = new CombinationsQuestion();
    long start = new Date().getTime();
    List<String> combinations = comb.combinations("12345678".toCharArray());
    long end= new Date().getTime();
    for(String s : combinations) {
        System.err.println(s);
    }
    System.err.println(combinations.size());
    System.err.println("took " + (end - start)  + " ms");
}

public List<String> combinations(char[] word) {
    List<String> list = new ArrayList<String>();
    if (word.length == 1) {
        list.add(String.valueOf(word));
    } else {
        char[] sub = new char[word.length - 1];
        for (int i = 0; i < word.length; i++) {
            System.arraycopy(word, 0, sub, 0, i);
            System.arraycopy(word, i + 1, sub, i, sub.length - i);
            list.add(String.valueOf(word[i]));
            list.addAll(concatenate(word[i], combinations(sub)));
        }
        sub = null;
    }
    return list;
}

public List<String> concatenate(char c, final List<String> lst) {
    List<String> ret_set = new ArrayList<String>(lst.size());
    for (String s : lst) {
        ret_set.add(c + s);
    }
    return ret_set;
}

}

Could I solve it by temporarily allocating a bigger stack like Android: Increase call stack size?

Thank you in advance!

ps. I know this produces a lot of Strings.

-- update --

I debugged the code and it seems that Dalvik is doing heavy GC during the recursion. This does not happen on regular desktop.

So the only way of doing this is trying to reuse the variables and not to instantiate objects so many. Of course this is a bit tricky when producing Strings but you can use StringBuilder / StringBuffer to some extent.

I found an article saying using NDK could solve this problem but adding NDK code adds complexity to the project and I was not willing (yet) to go that road.

Just to inform everyone, increasing stack size didn't help at all. — user2832636, Dec 27 '13 at 09:31
If you can avoid using recursion do it, recursion takes memory — Michael A, Jan 19 '14 at 11:35
Do I unterstand your code right, that it produces all possible numbers for a given set of characters? In another comment you mentioned, that you need all outcome stored somewhere for later use. Must that be a randomly accessible list or would an `Iterator` be enough? — jboi, Jan 19 '14 at 11:48
@jboi I have tried an Iterator solution as well but it didn't yield any better results. I think the problem in either solution is the fact that code produces a lot of Strings and while producing the Strings GC tries to release memory which causes Dalvik to GC_CONCURRENT to delay the actual execution. — user2832636, Jan 19 '14 at 12:08

aaronrod · Answer 1 · 2013-12-26T23:21:38.230

0

Do you have to print the entire set? If not, you can use the standard permutation formulas which should run a lot faster.

    /**
     * The setSize in the question's example would be 8 since there are 8 possible numbers 
     * to choose from in the set "12345678"
     */
    public static void solvePermutation(int setSize){
       long p = 0;
       for(int subSet=1; subSet<setSize+1; subSet++){
        p = p + permutation(setSize,subSet);
       }
       System.out.println(p);
   }

/**
 * p(n,r)  =  n!/((n-r)!) 
 * http://www.calctool.org/CALC/math/probability/combinations
 * 
 * @param n set size
 * @param r subset size
 * @return
 */
public static long permutation(long n, long r){
    long p = factorial(n)/
            (factorial(n-r));
    return p;
}

/**
 * http://stackoverflow.com/a/7879559/1361695
 * 
 * @param n
 * @return
 */
public static long factorial(long n) {
    long fact = 1; // this  will be the result
    for (long i = 1; i <= n; i++) {
        fact *= i;
    }
    return fact;
}

edited Dec 26 '13 at 23:21

answered Dec 26 '13 at 23:14

aaronrod

1
2

Where does he use permutations? – Michael Yaworski Dec 26 '13 at 23:25
@aaronrod I need to have them stored in a data structure for later purposes so just printing them out inside the function doesn't work for me. – user2832636 Dec 27 '13 at 09:35
@mikeyaworski This is just an example how the recursion is slow, actual example isn't used as such. – user2832636 Dec 27 '13 at 09:39
I turned it into iterative according to implementation here http://stackoverflow.com/questions/2799078/permutation-algorithm-without-recursion-java and now it's down to 6s which is one tenth of the original which is very nice. But it still takes long and I still don't know how to make it faster in either way. And I definitely don't know what's causing the "slowness". – user2832636 Dec 27 '13 at 16:13
Yes, my answer only gives one solution to the permutations possible. Have you considered shipping the app with a pre-populated db? [Copy Db from Asset folder](http://stackoverflow.com/a/10738956/1361695). – aaronrod Dec 29 '13 at 03:19
@aaronrod Yeah, I do have a database in the app. Are you suggesting that I would put all the permutations in the database and read it from there? – user2832636 Dec 29 '13 at 22:09

Recursion takes long, Android

1 Answers1