recursion to iteration

Question

Я работаю в настольном приложении для Windows с использованием Java. В моем приложении существует требование поиска всех .php. Для этого я использую рекурсивные методы.

import java.io.File; 

public class Copier { 

    public static void find(String source,String rep) { 
     File src = new File(rep); 
     if (src!= null && src.exists() && src.isDirectory()) { 
      String[] tab = src.list(); 
      if (tab != null) { 
       for(String s : tab) { 
        File srcc = new File(rep+"\\"+s); 
        if (srcc.isFile()) { 
         if (srcc.getName().matches(".*"+source+"$")) { 
          System.out.println(s); 
         } 
        } else { 
         find(source,srcc.getAbsolutePath()); 
        } 
       } 
      } else { 
       //System.out.println(" list is null"); 
      } 
     } 
    } 

    public static void main(String[] args) { 
     try { 
      find(".java", "C:\\"); 
     } catch (Exception e) { 
      e.printStackTrace(); 
     } 
    } 
} 

Возможно ли это сделать с помощью итерационного алгоритма?

Answer 1

Я не могу понять, почему вы хотите, чтобы избавиться от рекурсии, хотя теоретически то, что вы ищете возможно.

Но хорошим способом получить более быструю программу может быть использование файлового фильтра при переходе к дочерним элементам каталога. Один для каталогов и один для сопоставления файлов (этот должен использовать java.util.regexp.Pattern).

, были обновлены

Вы можете найти документ для перегрузки File.list использовать here. И для шаблона вы можете что-то вроде локальной переменной (вне вашего цикла или члена данных, если вы используете рекурсию).

Pattern p = Pattern.compile(".*"+source+".*"); 
boolean found = p.matcher(p.matcher(srcc.getName()).matches()); 

О, и, кстати, не конвертируйте srcc в файл! Работайте со строками и создавайте как можно меньше объектов.

Answer 2

Конечно. Используйте breadth-first-search с очередью. Вы начинаете с C:\ и на каждом шагу вы вытаскиваете верхнюю папку из очереди и вставляете все подпапки в конец очереди.

ПСЕВДОКОД следующим образом:

queue.push("C:\"); 
while (!queue.empty()) { 
    String topFolder = queue.pop(); 
    foreach (subFolder of topFolder) { 
     queue.push(subFolder); 
    } 
} 

Answer 3

Вы всегда можете использовать очередь вместо рекурсии. В этом случае, я думаю, это заставляет код выглядеть немного легче для чтения. Часто вы получаете лучшую производительность от итеративной реализации, чем рекурсивную, хотя в этом случае они работают с одинаковой скоростью (по крайней мере, на моей машине).

public static List<String> find(final String source, final String directory) 
{ 
    List<String> results = new LinkedList<String>(); 
    Stack<String> stack = new Stack<String>(); 

    stack.add(directory); 

    String rep; 
    while (!stack.isEmpty()) { 
     rep = stack.pop(); 
     File src = new File(rep); 
     if (src != null && src.exists() && src.isDirectory()) { 
      String[] tab = src.list(); 
      if (tab != null) { 
       for (String s : tab) { 
        File srcc = new File(rep + File.separatorChar + s); 
        if (srcc.isFile()) { 
         if (srcc.getName().matches(".*" + source + "$")) { 
          // System.out.println(s); 
          results.add(s); 
         } 
        } else { 
         stack.add(srcc.getAbsolutePath()); 
        } 
       } 
      } else { 
       // System.out.println(" list is null"); 
      } 
     } 
    } 
    return results; 
}