用於創建文件體系結構的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的最小數量

回答

相關問題