Java - 从文本文件中的平面结构读取分层数据并构建 HashMap

Question

我有一个文本文件，其中分层数据以平面结构提供。

child parent
Y,     X
Z,     Y
A,     Z

就像 X 是 Y 的父级一样，Y 本身是 Z 的父级，而 Z 是 A 的进一步父级。它可以以任何顺序出现在文件中。我需要构建一个 HashMap ，其中键应该是 element ，值应该是所有祖先元素的列表。例如， HashMap 应该具有基于上述数据的条目，如下所示

A=[Z, Y, X]，Y=[X]，Z=[Y, X]。

我用java编写了一段代码来构建这个 HashMap 。只需知道是否有更有效的方法来做到这一点。？逻辑是

1. 读取 hashmap 中的整个文件，其中 child 是键，parent 是值

2. 从上面创建的 HashMap 中递归遍历每个 child 并构建 parent 列表。

   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);
    }
}