Java非递归文件系统步行

我需要创建应用程序，它使用非递归遍历文件系统并打印出特定深度的文件。我有什么：Java非递归文件系统步行

public void putFileToQueue() throws IOException, InterruptedException { 
File root = new File(rootPath).getAbsoluteFile(); 
checkFile(root, depth); 
    Queue<DepthControl> queue = new ArrayDeque<DepthControl>(); 
    DepthControl e = new DepthControl(0, root); 
    do { 
     root = e.getFileName(); 

     if (root.isDirectory()) { 
      File[] files = root.listFiles(); 

      if (files != null) 
       for (File file : files) { 

        if (e.getDepth() + 1 <= depth && file.isDirectory()) { 
         queue.offer(new DepthControl(e.getDepth() + 1,file)); 
        } 

        if (file.getName().contains(mask)) { 
         if (e.getDepth() == depth) { 
          System.out.println(Thread.currentThread().getName() 
            + " putting in queue: " 
            + file.getAbsolutePath()); 
         } 
        } 
       } 
       } 
     e = queue.poll(); 
    } while (e != null); 
}

和辅助类

public class DepthControl { 

    private int depth; 
    private File file; 

    public DepthControl(int depth, File file) { 

     this.depth = depth; 
     this.file = file; 
    } 

    public File getFileName() { 
     return file; 
    } 

    public int getDepth() { 
     return depth; 
    } 
}

我收到的答案，这个程序使用，因为广度优先搜索（希望右平移）的额外内存。我有O（k^n），其中k - 平均数量的子目录，n - 深度。这个程序可以用O（k * n）轻松完成。请帮我修复我的算法。

来源

2012-03-07 user1255246

为什么它必须非递归？ – 2012-03-07 17:30:10

@HotLicks，这可能是一个家庭作业相关的要求。 – Moonbeam 2012-03-07 17:32:34

为了复杂化，我想。这是面试任务。 – user1255246 2012-03-07 17:35:00

我认为这应该可以完成这项工作，并且更简单一些。它只是跟踪下一级文件，扩展它们，然后重复这个过程。算法本身跟踪深度，所以不需要额外的类。

// start in home directory. 
File root = new File(System.getProperty("user.dir")); 

List<File> expand = new LinkedList<File>(); 
expand.add(root); 

for (int depth = 0; depth < 10; depth++) { 
    File[] expandCopy = expand.toArray(new File[expand.size()]); 
    expand.clear(); 
    for (File file : expandCopy) { 
     System.out.println(depth + " " + file); 
     if (file.isDirectory()) { 
      expand.addAll(Arrays.asList(file.listFiles())); 
     } 
    } 
}

来源

2012-03-07 17:50:43 Adam

非常漂亮和美丽。我会试试这个。 – user1255246 2012-03-07 18:20:01

但perfomance是可怕的，因为复制每一次迭代，但仍然美丽的代码。 – user1255246 2012-03-10 21:44:06

除非有特殊的性能要求，否则我通常会比美容更注重美观。在这种情况下，限制因素可能是文件系统。 – Adam 2012-03-10 23:51:33

要步行一棵树时，为了避免递归基本上有两种选择：

使用的“工作清单”（类似于以上）来跟踪工作要做。在检查每个项目时，作为结果“发现”的新工作项目被添加到工作清单（可以是FIFO，LIFO或随机顺序 - 概念上无关紧要，尽管它通常会影响“参考的地点”性能）。
使用一个堆栈/“下推列表”，所以基本上模拟了递归方案。

对于＃2，您必须编写一个算法，这是一个状态机，在每一步之后返回到堆栈以确定下一步要做什么。树形结构的堆栈条目基本上包含当前树节点以及要检查的下一个子项的子列表中的索引。

来源

2012-03-07 17:51:07

你可以给我一个链接阅读＃2。 – user1255246 2012-03-07 18:13:04

我明白了，但仍然无法得到它的工作方式 – user1255246 2012-03-07 18:14:40

这三种方案（递归和上述两种）应该具有相同的“大O”效率，因为每个方案都只需访问一次节点。方案＃1将使用更多的存储 - O（n）（n =节点总数）平均来说，我怀疑，而递归和方案＃2将是O（log n），我想。（我没有坐下来详细研究效率。） – 2012-03-07 18:43:09

假设你想限制的空间使用量和：

你可以假设的文件/目录列表是在你穿越的过程中静态的，
你可以假设名单文件/目录在给目录以相同的顺序总是返回
您可以访问到当前目录的父

然后你可以使用在遍历目录最后访问的节点的信息。具体来说，沿

1. Keep track of the last Entry (directory or file) visited 
2. Keep track of the current directory 
3. Get a list of files in the current directory 
4. Find the index of the last Entry visited in the list of files 
5. If lastVisited is the last Entry in the current directory, 
5.1.1 If current directory == start directory, we're done 
5.1.2 Otherwise, lastVisited = the current directory and current directory is the parent directory 
5.2. Otherwise, visit the element after lastVisited and set lastVisited to that element 
6. Repeat from step 3

线的东西如果我可以，我会尝试写一些代码来说明我的意思，明天......但我没有时间，现在。

注意：这不是一个遍历目录结构的好方法......它只是一种可能的方式。在正常框外，可能是有很好的理由。

你必须原谅我没有在Java中给出示例代码，我没有时间去处理这个atm。在Tcl中做它对我来说更快，它不应该太难理解。所以，他这样说：

proc getFiles {dir} { 
    set result {} 
    foreach entry [glob -tails -directory $dir * .*] { 
     if { $entry != "." && $entry != ".." } { 
      lappend result [file join $dir $entry] 
     } 
    } 
    return [lsort $result] 
} 

proc listdir {startDir} { 
    if {! ([file exists $startDir] && [file isdirectory $startDir])} { 
     error "File '$startDir' either doesn't exist or isnt a directory" 
    } 
    set result {} 
    set startDir [file normalize $startDir] 
    set currDir $startDir 
    set currFile {} 

    set fileList [getFiles $currDir] 
    for {set i 0} {$i < 1000} {incr i} { # use for to avoid infinate loop 
     set index [expr {1 + ({} == $currFile ? -1 : [lsearch $fileList $currFile])}] 
     if {$index < ([llength $fileList])} { 
      set currFile [lindex $fileList $index] 
      lappend result $currFile 
      if { [file isdirectory $currFile] } { 
       set currDir $currFile 
       set fileList [getFiles $currDir] 
       set currFile {} 
      } 
     } else { 
      # at last entry in the dir, move up one dir 
      if {$currDir == $startDir} { 
       # at the starting directory, we're done 
       return $result 
      } 
      set currFile $currDir 
      set currDir [file dirname $currDir] 
      set fileList [getFiles $currDir] 
     } 
    } 
} 

puts "Files:\n\t[join [listdir [lindex $argv 0]] \n\t]"

而且，跑步吧：

VirtualBox:~/Programming/temp$ ./dirlist.tcl /usr/share/gnome-media/icons/hicolor 
Files: 
    /usr/share/gnome-media/icons/hicolor/16x16 
    /usr/share/gnome-media/icons/hicolor/16x16/status 
    /usr/share/gnome-media/icons/hicolor/16x16/status/audio-input-microphone-high.png 
    /usr/share/gnome-media/icons/hicolor/16x16/status/audio-input-microphone-low.png 
    /usr/share/gnome-media/icons/hicolor/16x16/status/audio-input-microphone-medium.png 
    /usr/share/gnome-media/icons/hicolor/16x16/status/audio-input-microphone-muted.png 
    /usr/share/gnome-media/icons/hicolor/22x22 
    [snip] 
    /usr/share/gnome-media/icons/hicolor/48x48/devices/audio-subwoofer-testing.svg 
    /usr/share/gnome-media/icons/hicolor/48x48/devices/audio-subwoofer.svg 
    /usr/share/gnome-media/icons/hicolor/scalable 
    /usr/share/gnome-media/icons/hicolor/scalable/status 
    /usr/share/gnome-media/icons/hicolor/scalable/status/audio-input-microphone-high.svg 
    /usr/share/gnome-media/icons/hicolor/scalable/status/audio-input-microphone-low.svg 
    /usr/share/gnome-media/icons/hicolor/scalable/status/audio-input-microphone-medium.svg 
    /usr/share/gnome-media/icons/hicolor/scalable/status/audio-input-microphone-muted.svg

来源

2012-03-10 06:17:48 RHSeeger

那么只需将收藏集更改为堆叠呢？它的工作原理，性能似乎更好，在这种情况下，记忆是什么？ – user1255246 2012-03-10 21:53:13

如果我说得对，这是一种持久的搜索状态。这就是我从一开始就认为的，但不知道如何去做的。我现在就试试。如果你有时间，请发布实现或给出一个链接更详细的阅读。谢谢！ – user1255246 2012-03-10 22:05:40

如果您使用的是Java 7，有步行的文件目录树的一个非常优雅的方法。您需要确认它是否满足您的递归明智需求。

import java.nio.file.*; 
import java.nio.file.attribute.BasicFileAttributes; 
import static java.nio.file.FileVisitResult.*; 

public class myFinder extends SimpleFileVisitor<Path> { 

public FileVisitResult visitFile(Path file, BasicFileAttributes attr) { } 
public FileVisitResult postVisitDirectory(Path dir, IOException exc) { } 
public FileVisitResult preVisitDirectory(Path dir, BasicFileAttributes attrs) { } 
public FileVisitResult visitFileFailed(Path file, IOException exc) { } 


<snip> 

}

本质上，它确实树的深度第一次散步，当它进入调用某些方法/退出目录，当它“访问”的文件。

我相信这是特定于Java 7，虽然。

http://docs.oracle.com/javase/tutorial/essential/io/walk.html

来源

2012-03-10 07:04:45 FreudianSlip

我认为它在现实世界的应用程序中非常有用，但在我的情况下却不是这样。它使用递归。 :(尽管如此，非常感谢你的留言，对于观看java的新功能非常有用。 – user1255246 2012-03-10 21:49:29

和 - 当然 - 总是有多线程选项来避免递归。

创建一个文件队列。
如果它是一个文件，将其添加到队列中。
如果它是一个文件夹中启动一个新的线程来列出它的档案也进此队列。
获取下一个项目。
根据需要重复2。

显然，这可能无法列出可预知的顺序文件。

来源

2012-10-01 11:17:21 OldCurmudgeon

Java非递归文件系统步行

回答

相关问题