用于创建文件体系结构的mkdirs的最小数量

假设我有一个List的路径，并且我想减少它以使最少数量的file.mkdirs()运行来重新创建整个体系结构。用于创建文件体系结构的mkdirs的最小数量

因此，来自：

[/ FOO，/富/酒吧，/富/酒吧/ COO，/富/酒吧/ coo2，/富/芭比，/ notFoo /东西]

我想到：

[/ notFoo /东西，/富/芭比/富/酒吧/首席运营官/富/酒吧/ coo2]

我做这个天真的方法是：

List<String> l_paths = Arrays.asList("/foo","/foo/bar", "/foo/bar/coo","/foo/barbie","/notFoo/something"); 
    ArrayList<String> l_reducted = new ArrayList<>(); 
    List<String> l_ordered = l_paths.stream().sorted((p1,p2) -> p2.compareTo(p1)).collect(Collectors.toList()); 
    for(String l_string : l_ordered){ 
     if(l_reducted.stream().noneMatch(e -> e.startsWith(l_string) && e.substring(l_string.length()).contains("/"))){ 
      l_reducted.add(l_string); 
     } 
    } 
    System.out.println(l_reducted);

，或者对Java 8对恋人：

// java 8 style, way less readable IMO 
    BiFunction<List<String>, String, List<String>> myAccumulator = new BiFunction<List<String>, String, List<String>>() { 
     @Override 
     public List<String> apply(List<String> list, String string) { 
      if (list.stream().noneMatch(e -> e.startsWith(string) && e.substring(string.length()).contains("/"))) { 
       list.add(string); 
      } 
      return list; 
     } 
    }; 
    System.out.println(l_paths.stream().sorted((p1, p2) -> p2.compareTo(p1)) 
      .reduce(new ArrayList<>(), 
        myAccumulator, 
        (list1, list2) -> { 
         list2.stream().forEach(i -> myAccumulator.apply(list1, i)); 
         return list1; 
        }));

但我敢确信，分裂在隔板上的每一条路径，并将其插入到树形结构类似于文件系统会更好（但我不擅长树木，所以我没有实现它），因为它会允许以我的方式访问节点和mkdir。

你认为哪个更好？免责声明：我不是真的在这里讨论关于过早优化，我只是对算法感兴趣，对于知识好奇。但是让我们说mkdir实际上是一个调用非常慢的web服务（它甚至不理解整个路径上的mkdirs），并且调用的数量很重要。而且我们也会假设我的集合中有数百万条路径，并且减少的计算复杂度也很重要。

来源

2017-06-01 Jeremy Grand

你是否分析了它，看看你的程序是否比简单地调用每个路径的'mkdirs（）'更快？ –

@SteveSmith我还没有，因为它不是一个实际的生产瓶颈，只是我多次遇到这个问题，从不关心。今天，我决定“如果我照顾一次，该怎么办？”。如果这件事很重要，那么做这种事情的方法是什么？如何通过迭代列表的测试正确地减少我的列表？我在我的问题中增加了一个免责声明（但我想我可以在没有它的情况下解决这个问题） –

我没有时间和预算来运行基准测试来优化不是瓶颈的事情。但是，如果有一个优雅的（简短易读的）方法来减少比mkdirs更好的列表，我会很高兴发现它。 –

这当作一项学术活动，而不是同意减少调用mkdirs()是一个值得追求......

排序列表中按字母顺序
每串映射到String[]与path.split("/")
遍历列表。如果当前条目不是以前一个条目的所有元素开头，则输出前一个条目。
最后输出看到的最后一个条目（假设输入列表不为空）

喜欢的东西：

List<String[]> sortedPaths = paths.stream().sorted().map(s -> s.split("/")) 

List<String> out = new ArrayList<>(); 
String[] previous = new String[0]; 

for(String[] path : sortedPaths) { 
    if(! beginsWith(path,previous)) { 
      out.add(String.join(",", previous)); 
    } 
    previous = path; 
} 
out.add(String.join(",", previous));

我离开的beginsWith(String[], String[])实施给读者，以及处理与空的输入列表，如果你需要。

另外，还按字母顺序排序第一：

for(String path : paths) { 
     if(out.isEmpty() || ! isSubPath(out.get(out.size()-1), path) { 
      out.add(path); 
     } else { 
      out.set(out.size()-1, path); 
     } 
    }

（isSubPath测试第一个参数是否具有相同的父迪尔斯作为第二）

请注意，如果你是试图节省文件系统调用：

mkdirs("https://stackoverflow.com/a/b/c/d"); 
mkdirs("https://stackoverflow.com/a/b/e/f");

...仍然在执行比完全必要的更多的系统调用，因为在mkdirs()后面是一堆mkdir()，它将尝试创建两次/a和/a/b。

如果你是狂热的关于减少文件系统操作（这可能是值得的，例如一个缓慢的链接到一个远程服务），你会想：

扩大你的路径列表，列表个人mkdir()秒 - 也就是说，{"a/b/c"}变得{"a", "a/b", "a/b/c"}
排序并删除重复
mkdir()对于每一个。

来源

2017-06-01 16:03:22 slim

Upvoter here。无法理解你的意思是“以前的入门不是以现有的元素开始”，这就是为什么我添加了自己的答案。但我相信你的回答给了我一些提示。 –

@GrzegorzGórkiewicz将澄清 – slim

“以相同元素开始”在我看来是不够的。可能是：'/ a/b/c'和'/ a/b/d'。它们都以'/ a/b'开始，但它们之间没有“是它们的子目录”关系。你的想法是对的，其措辞不是。 –

但我敢确信，在分隔每分裂路径和将它们插入到一个树状结构类似于文件系统会是更好的方式（但我不是在树上精通，所以我没有实现它），因为它然后将允许只是访问我的方式节点和 mkdir。

您当然可以使用类似Trie的树型数据结构来处理问题，每个节点对应一个路径段。如果您将这些数据结构中的所有路径记录下来，那么您可以找到创建整个层次结构所需的最小集合 - 正是那些对应于叶节点的集合。

但是编写数据结构的代码要花费很多工作量。只有当你有一些继续使用它会对我有任何意义。如果您只需确定（假设）trie的叶节点，您可以通过@slim建议的方法非常干净而高效地完成。

来源

2017-06-01 16:16:10

用于创建文件体系结构的mkdirs的最小数量

回答

相关问题