рекурсия к итерации - PullRequest
Новая
       27

рекурсия к итерации

0 голосов
/ 19 декабря 2011

Я работаю в настольном приложении для 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();
        }
    }
}

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

Ответы [ 3 ]

3 голосов
/ 19 декабря 2011

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

Псевдокод следует: 

queue.push("C:\");
while (!queue.empty()) { 
   String topFolder = queue.pop();
   foreach (subFolder of topFolder) {
        queue.push(subFolder);
   }
}
1 голос
/ 19 декабря 2011

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

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;
}
1 голос
/ 19 декабря 2011

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

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

-обновлен

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

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

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

...