Оптимизация алгоритма java

Question

Привет У меня есть следующий метод. Что он делает, так это найти все возможные пути от верхнего левого к нижнему праву матрицы N x M. Мне было интересно, что лучший способ оптимизировать его для скорости, поскольку сейчас он немного медленный. Приведенные пути затем сохраняются в наборе.

EDIT я забыл уточнить, вы можете двигаться только вниз или вправо на соседнюю точку, не диагонали от текущей позиции

For example 
ABC 
DEF 
GHI 

Путь от верхнего левого угла к нижнему правому не будет ADEFI

static public void printPaths (String tempString, int i, int j, int m, int n, char [][] arr, HashSet<String> palindrome) { 
    String newString = tempString + arr[i][j]; 
    if (i == m -1 && j == n-1) { 
     palindrome.add(newString); 
     return; 
    } 
    //right 
    if (j+1 < n) { 
     printPaths (newString, i, j+1, m, n, arr, palindrome); 
    } 
    //down 
    if (i+1 < m) { 
     printPaths (newString, i+1, j, m, n, arr, palindrome);   
    } 
} 

EDIT Вот совокупность кода

public class palpath { 

    public static void main(String[] args) throws IOException { 
     BufferedReader br = new BufferedReader(new FileReader("palpath.in")); 
     PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("palpath.out"))); 
     StringTokenizer st = new StringTokenizer(br.readLine()); 

     int d = Integer.parseInt(st.nextToken()); 


     char[][] grid = new char [d][d]; 

     String index = null; 

     for(int i = 0; i < d; i++) 
     { 
      String temp = br.readLine(); 
      index = index + temp; 
      for(int j = 0; j < d; j++) 
      { 
       grid[i][j] = temp.charAt(j); 
      } 
     } 

     br.close(); 

     int counter = 0; 

     HashSet<String> set = new HashSet<String>(); 
     printPaths ("", 0, 0, grid.length, grid[0].length, grid, set); 

     Iterator<String> it = set.iterator(); 
     while(it.hasNext()){ 
      String temp = it.next(); 
      StringBuilder sb = new StringBuilder(temp).reverse(); 
      if(temp.equals(sb.toString())) { 
       counter++; 
      } 

     } 




     pw.println(counter); 
     pw.close(); 

    } 


     static public void printPaths (String tempString, int i, int j, int m, int n, char [][] arr, HashSet<String> palindrome) { 
      String newString = tempString + arr[i][j]; 
      if (i == m -1 && j == n-1) { 
       palindrome.add(newString); 
       return; 
      } 
      //right 
      if (j+1 < n) { 
       printPaths (newString, i, j+1, m, n, arr, palindrome); 
      } 
      //down 
      if (i+1 < m) { 
       printPaths (newString, i+1, j, m, n, arr, palindrome);   
      } 
     } 

Answer 1

Вы тратите много времени на управление строковой памятью.
Являются ли строки в Java изменяемыми? Если вы можете изменить символы внутри строки, тогда задайте длину строки как n + m и используйте эту единственную строку, установив (i + j) th char на каждой итерации. Если они не изменяются, используйте массив символов или что-то подобное и преобразуйте его в строку в конце

Answer 2

Для заданного размера N × M массива все ваши пути имеют N + M + 1 элемент (N + M шагов), поэтому первый шаг оптимизации избавляет от рекурсии, выделяет массив и запускает рекурсию с while на явный стек.

Каждый частичный путь может быть расширен одним или двумя шагами: вправо или вниз. Таким образом, вы можете легко создать явный стек с посещенными позициями и шаг в каждой позиции. Помещенный положение (0,0) в стек с фазой (шаг) «Нет», то:

while stack not empty { 
    if stack is full /* reached lower-right corner, path complete */ { 
     print the path; 
     pop; 
    } 
    else if stack.top.phase == none { 
     stack.top.phase = right; 
     try push right-neighbor with phase none; 
    } 
    else if stack.top.phase == right { 
     stack.top.phase = down; 
     try push down-neighbor with phase none; 
    } 
    else /* stack.top.phase == down */ { 
     pop; 
    } 
} 

Answer 3

Учитывая график длины М х N, все пути от (0,0) до (M -1, N-1), которые только включают в себя движения вправо и вниз, гарантированно содержат точно M-1, перемещается вправо, а N-1 перемещается вниз.

Это представляет интересное свойство: мы можем представить путь от (0,0) до (M-1, N-1) в виде двоичной строки (0, указывающей движение вправо и 1, указывающее движение вниз) ,

Итак, возникает вопрос: насколько быстро мы можем распечатать список перестановок этой битовой строки?

Довольно быстро.

public static void printPaths(char[][] arr) { 
    /* Get Smallest Bitstring (e.g. 0000...111) */ 
    long current = 0; 
    for (int i = 0; i < arr.length - 1; i++) { 
     current <<= 1; 
     current |= 1; 
    } 

    /* Get Largest Bitstring (e.g. 111...0000) */ 
    long last = current; 
    for (int i = 0; i < arr[0].length - 1; i++) { 
     last <<= 1; 
    } 

    while (current <= last) { 
     /* Print Path */ 
     int x = 0, y = 0; 
     long tmp = current; 
     StringBuilder sb = new StringBuilder(arr.length + arr[0].length); 
     while (x < arr.length && y < arr[0].length) { 
      sb.append(arr[x][y]); 
      if ((tmp & 1) == 1) { 
       x++; 
      } else { 
       y++; 
      } 
      tmp >>= 1; 
     } 
     System.out.println(sb.toString()); 

     /* Get Next Permutation */ 
     tmp = (current | (current - 1)) + 1; 
     current = tmp | ((((tmp & -tmp)/(current & -current)) >> 1) - 1); 
    } 
} 

Answer 4

Если вы сделаете несколько замечаний о своих требованиях, вы можете оптимизировать это по-настоящему.

1. Будут выполнены шаги (r-1) + (c-1) (где r = строки и c = столбцы).
2. Вправо будут шаги (c-1) справа и (r-1).

Таким образом, вы можете использовать числа, в которых нулевой бит может (произвольно) указывать шаг вниз, когда 1 бит проходит через. Затем мы можем просто перебрать все числа битов (r-1) + (c-1), содержащих только (c-1) бит. Для этого есть хороший алгоритм на сайте Stanford BitTwiddling Compute the lexicographically next bit permutation.

Первый a BitPatternIterator Я использовал раньше. Вы можете вытащить код в hasNext, если хотите.

/** 
* Iterates all bit patterns containing the specified number of bits. 
* 
* See "Compute the lexicographically next bit permutation" http://graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation 
* 
* @author OldCurmudgeon 
*/ 
public static class BitPattern implements Iterable<BigInteger> { 

    // Useful stuff. 
    private static final BigInteger ONE = BigInteger.ONE; 
    private static final BigInteger TWO = ONE.add(ONE); 
    // How many bits to work with. 
    private final int bits; 
    // Value to stop at. 2^max_bits. 
    private final BigInteger stop; 

    // All patterns of that many bits up to the specified number of bits. 
    public BitPattern(int bits, int max) { 
     this.bits = bits; 
     this.stop = TWO.pow(max); 
    } 

    @Override 
    public Iterator<BigInteger> iterator() { 
     return new BitPatternIterator(); 
    } 

    /* 
    * From the link: 
    * 
    * Suppose we have a pattern of N bits set to 1 in an integer and 
    * we want the next permutation of N 1 bits in a lexicographical sense. 
    * 
    * For example, if N is 3 and the bit pattern is 00010011, the next patterns would be 
    * 00010101, 00010110, 00011001, 
    * 00011010, 00011100, 00100011, 
    * and so forth. 
    * 
    * The following is a fast way to compute the next permutation. 
    */ 
    private class BitPatternIterator implements Iterator<BigInteger> { 

     // Next to deliver - initially 2^n - 1 - i.e. first n bits set to 1. 
     BigInteger next = TWO.pow(bits).subtract(ONE); 
     // The last one we delivered. 
     BigInteger last; 

     @Override 
     public boolean hasNext() { 
      if (next == null) { 
       // Next one! 
       // t gets v's least significant 0 bits set to 1 
       // unsigned int t = v | (v - 1); 
       BigInteger t = last.or(last.subtract(BigInteger.ONE)); 
       // Silly optimisation. 
       BigInteger notT = t.not(); 
       // Next set to 1 the most significant bit to change, 
       // set to 0 the least significant ones, and add the necessary 1 bits. 
       // w = (t + 1) | (((~t & -~t) - 1) >> (__builtin_ctz(v) + 1)); 
       // The __builtin_ctz(v) GNU C compiler intrinsic for x86 CPUs returns the number of trailing zeros. 
       next = t.add(ONE).or(notT.and(notT.negate()).subtract(ONE).shiftRight(last.getLowestSetBit() + 1)); 
       if (next.compareTo(stop) >= 0) { 
        // Dont go there. 
        next = null; 
       } 
      } 
      return next != null; 
     } 

     @Override 
     public BigInteger next() { 
      last = hasNext() ? next : null; 
      next = null; 
      return last; 
     } 

     @Override 
     public void remove() { 
      throw new UnsupportedOperationException("Not supported."); 
     } 

     @Override 
     public String toString() { 
      return next != null ? next.toString(2) : last != null ? last.toString(2) : ""; 
     } 

    } 

} 

С помощью этого итерировать ваше решение:

public void allRoutes(char[][] grid) { 
    int rows = grid.length; 
    int cols = grid[0].length; 
    BitPattern p = new BitPattern(rows - 1, cols + rows - 2); 
    for (BigInteger b : p) { 
     //System.out.println(b.toString(2)); 
     /** 
     * Walk all bits, taking a step right/down depending on it's set/clear. 
     */ 
     int x = 0; 
     int y = 0; 
     StringBuilder s = new StringBuilder(rows + cols); 
     for (int i = 0; i < rows + cols - 2; i++) { 
      s.append(grid[y][x]); 
      if (b.testBit(i)) { 
       y += 1; 
      } else { 
       x += 1; 
      } 
     } 
     s.append(grid[y][x]); 
     // That's a solution. 
     System.out.println("\t" + s); 
    } 
} 

public void test() { 
    char[][] grid = {{'A', 'B', 'C'}, {'D', 'E', 'F'}, {'G', 'H', 'I'}}; 
    allRoutes(grid); 
    char[][] grid2 = {{'A', 'B', 'C'}, {'D', 'E', 'F'}, {'G', 'H', 'I'}, {'J', 'K', 'L'}}; 
    allRoutes(grid2); 
} 

печать

ADGHI 
ADEHI 
ABEHI 
ADEFI 
ABEFI 
ABCFI 
ADGJKL 
ADGHKL 
ADEHKL 
ABEHKL 
ADGHIL 
ADEHIL 
ABEHIL 
ADEFIL 
ABEFIL 
ABCFIL 

, который - на мой взгляд - выглядит правильно.