Java - 從文本文件中的平面結構讀取分層數據並構建散列圖

Question

我有一個文本文件，其中分層數據在文本文件中的平面結構中可用。

child parent 
Y,  X 
Z,  Y 
A,  Z 

它像X是Y的父親，它本身Z和Z的父親是A的父親。它可以以任何順序出現在文件中。我需要構建一個hashmap，其中鍵應該是元素，值應該是所有祖先元素的列表。例如，HashMap應該具有基於上述數據的條目，如下所示：其中A = [Z，Y，X]，Y = [X]，Z = [Y，X]。

我已經在java中編寫了一個代碼來構建這個hashmap。只需要知道是否有更有效的方法來做到這一點。 邏輯是

1. 閱讀其中的孩子是關鍵，家長是價值

2. 從上面創建遞歸遍歷每個孩子和父母建立的名單HashMap中的散列映射整個文件。

   public class Test { 
   public static final String FILE_NAME = "dataset1"; 
   public static final HashMap<String,String> inputMap = new HashMap<String,String>(); 
   public static final Map<String, ArrayList<String>> parentChildMap = new HashMap<String,ArrayList<String>>(); 
   
   private static void readTextFile(String aFileName) throws IOException { 
   
       Path path = Paths.get(aFileName); 
   
       try (BufferedReader reader = Files.newBufferedReader(path, StandardCharsets.UTF_8)){ 
        String line = null; 
        while ((line = reader.readLine()) != null) { 
         String[] dataArray = line.split(","); 
         String child = dataArray[0]; 
         String parent = dataArray[1]; 
   
         inputMap.put(child, parent); 
        }  
       } 
       } 
   public static ArrayList<String> getParents(String childId, ArrayList<String> parents) { 
   
       if (childId == null) 
       return parents; 
   
       String parentId = inputMap.get(childId); 
       if(parentId!=null) parents.add(parentId); 
       getParents(parentId, parents); 
   
       return parents; 
   } 
   
   public static void main(String[] s) throws IOException { 
       readTextFile(FILE_NAME); 
       for(String child : inputMap.keySet()) { 
       ArrayList<String> parents = getParents(child, new ArrayList<String>()); 
       parentChildMap.put(child, parents); 
   } 
   } 
   

Answer 1

遞歸已經是相當有效的。這裏是可以優化的：

• 認沽遞歸轉換到一個循環，遞歸/環路（避免重複計算）
• 不要重新計算祖先每次
• 使用記憶化的getParent被調用時，預先計算的結果，並將其儲存

這裏是我的代碼：

import java.io.BufferedReader; 
import java.io.IOException; 
import java.nio.charset.StandardCharsets; 
import java.nio.file.Files; 
import java.nio.file.Path; 
import java.nio.file.Paths; 
import java.util.ArrayList; 
import java.util.HashMap; 
import java.util.Map; 

public class Test { 
    public static final String FILE_NAME = "dataset1"; 
    public static final HashMap<String, String> inputMap = new HashMap<String, String>(); 
    public static final Map<String, ArrayList<String>> parentChildMap = new HashMap<String, ArrayList<String>>(); 

    private static void readTextFile(String aFileName) throws IOException { 

     Path path = Paths.get(aFileName); 

     try (BufferedReader reader = Files.newBufferedReader(path, StandardCharsets.UTF_8)) { 
      String line = null; 
      while ((line = reader.readLine()) != null) { 
       String[] dataArray = line.split(","); 
       String child = dataArray[0]; 
       String parent = dataArray[1]; 

       inputMap.put(child, parent); 
      } 
     } 

     // this replaces the recursion: 
     for (String k : inputMap.keySet()) { 
      String ok = k; 
      ArrayList<String> tmp = new ArrayList<String>(); 
      while (true) { 
       // if this has already been computed, use old answer 
       if (parentChildMap.containsKey(k)) { 
        tmp.addAll(parentChildMap.get(k)); 
        break; 
       } 
       if (inputMap.containsKey(k)) { 
        String v = inputMap.get(k); 
        tmp.add(v); 
        k = v; 
       } else { 
        break; 
       } 
      } 
      parentChildMap.put(ok, tmp); 
     } 
    } 

    public static ArrayList<String> getParents(String childId) { 
     // do not recompute 
     return parentChildMap.get(childId); 
    } 
} 

Answer 2

您所要求的 「更有效的方式」，所以這裏是我的批評（小調）和我的建議。

• 請勿初始化line至null。只需聲明它。
• 請勿使用split()。它可能會分成兩個以上的值，並且它必須創建一個數組。只需使用indexOf()。

因此，第一種方法爲（壓縮一些）：

public static final Map<String, String> inputMap = new HashMap<>(); 
private static void readTextFile(String aFileName) throws IOException { 
    try (BufferedReader reader = Files.newBufferedReader(Paths.get(aFileName), 
                 StandardCharsets.UTF_8)){ 
     for (String line; (line = reader.readLine()) != null;) { 
      int idx = line.indexOf(','); 
      inputMap.put(/*child*/line.substring(0, idx), 
         /*parent*/line.substring(idx + 1)); 
     }  
    } 
} 

現在的建議。

您的代碼會多次解析同一父母，例如，當檢索父母A時，必須步行整個母鏈Z,Y,X，並且在檢索父母Z時，必須走母鏈Y,X。你多次做同樣的行程。

只做一次會更有效率。由於數據無序，你必須使用遞歸來完成。我已將parentChildMap更名爲更合適的ancestorMap。

public static final Map<String, List<String>> ancestorMap = new HashMap<>(); 
private static List<String> getAncestors(String child) { 
    // Check if ancestors already resolved 
    List<String> ancestors = ancestorMap.get(child); 
    if (ancestors == null) { 
     // Find parent 
     String parent = inputMap.get(child); 
     if (parent == null) { 
      // Child has no parent, i.e. no ancestors 
      ancestors = Collections.emptyList(); 
     } else { 
      // Find ancestors of parent using recursive call 
      List<String> parentAncestors = getAncestors(parent); 
      if (parentAncestors.isEmpty()) { 
       // Parent has no ancestors, i.e. child has single ancestor (the parent) 
       ancestors = Collections.singletonList(parent); 
      } else { 
       // Child's ancestors is parent + parentAncestors 
       ancestors = new ArrayList<>(parentAncestors.size() + 1); 
       ancestors.add(parent); 
       ancestors.addAll(parentAncestors); 
      } 
     } 
     // Save resolved ancestors 
     ancestorMap.put(child, ancestors); 
    } 
    return ancestors; 
} 

如果你不關心使用emptyList()和singletonList()，或有意見的優化，它可以壓縮到：

private static List<String> getAncestors(String child) { 
    List<String> ancestors = ancestorMap.get(child); 
    if (ancestors == null) { 
     ancestorMap.put(child, ancestors = new ArrayList<>()); 
     String parent = inputMap.get(child); 
     if (parent != null) { 
      ancestors.add(parent); 
      ancestors.addAll(getAncestors(parent)); 
     } 
    } 
    return ancestors; 
} 

的main方法就變成了：

public static final String FILE_NAME = "dataset1"; 
public static void main(String[] args) throws IOException { 
    readTextFile(FILE_NAME); 
    for (String child : inputMap.keySet()) 
     getAncestors(child); // Ignore return value 
}