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 
}