如何根据键值对合并文件并使用 Java 对其进行排序？

Question

我写过一个类似于外部排序的程序。我从 this blog 那里得到了一个好主意。在这里，他们试图对数字进行外部排序。我的要求有点不同。我的输入文件可以有超过百万条记录并且很难在内存中对它们进行排序，所以我必须使用我的磁盘。我将我的输入分成不同的部分，对其进行排序，然后将其存储在临时文件中。然后将排序后的输出合并到一个文件中。下面我可以将其拆分为临时文件，然后仅合并密钥。

我有一个输入文件如下：

key1 abc
key2 world
key1 hello
key3 tom
key7 yankie
key3 apple
key5 action
key7 jack
key4 apple
key2 xon
key1 lemon

假设磁盘上文件的大小是 10，内存缓冲区可以容纳的最大项目是 4，所以我所做的是一次获取 4 条记录并将其存储在 HashMap 中，将我的值与更新计数。此输入将分为 3 个排序文件，如下所示。您可以看到，对于每个键，我都有一个计数以及字典序最高值。

临时文件-0.txt

key1: 2, hello
key2: 1, world
key3: 1, tom

临时文件-1.txt

key5: 1, action
key3: 1, apple
key7: 2, yankie

临时文件-2.txt

key1: 1, lemon
key2: 1, xon
key4: 1, apple

合并所有这 3 个文件后，输出应如下所示：

key1: 3 lemon
key2: 2 xon
key3: 2 world
key5: 1 action
key7: 2 yankie

我不确定将整行与计数和该键的字典序最高值合并的逻辑，我的以下代码能够为我提供所有键，如下所示：

key1
key1
key2
key2
key3
key4
key5
key3
key7

在下面的代码中，我打开每个文件并合并它们，然后写回磁盘到一个名为 external-sorted.txt

的新文件中

    static int N = 10; // size of the file in disk
     static int M = 4; // max items the memory buffer can hold
     int slices = (int) Math.ceil((double) N/M);
     String tfile = "temp-file-";

//Reading all the 3 temp files
     BufferedReader[] brs = new BufferedReader[slices];
     String[] topNums = new String[slices];
     for(i = 0; i<slices; i++){
      brs[i] = new BufferedReader(new FileReader(tfile + Integer.toString(i) + ".txt"));
      String t = brs[i].readLine();
      String[] kv = t.split(":");

      if(t!=null){
        topNums[i] = kv[0];
      }
    //topNums [key1, key5, key1]
     }

    FileWriter fw = new FileWriter("external-sorted.txt");
    PrintWriter pw = new PrintWriter(fw);

    for(i=0; i<N; i++){

    String min = topNums[0];
    System.out.println("min:"+min);
    int minFile = 0;

    for(j=0; j<slices; j++){

    if(min.compareTo(topNums[j])>0)
      {
      min = topNums[j];
      minFile = j;
      }
    }

     pw.println(min);
      String t = brs[minFile].readLine();
     String[] kv = new String[2];
      if (t != null)
         kv = t.split(":");
         topNums[minFile] = kv[0];

    }

       for (i = 0; i < slices; i++)
        brs[i].close();

       pw.close();
       fw.close();
      }

如有任何想法，我们将不胜感激。请询问，如果您有任何问题。 TIA.

Answer 1

好吧，像这样的方法可行，我相信有更好的方法，但目前我还没有真正思考：

    // Declare Scanner Object to read our file
    Scanner in = new Scanner(new File(stringRepresentingLocationOfYourFileHere));

    // create Map that will contain keys in sorted order (TreeMap)
    // along with last value assigned to the key
    Map<String, String> mapa = new TreeMap<>();

    // another map to hold keys from first map and number of
    // occurrences of those keys (repetitions), this could have been
    // done using single Map as well, but whatever
    Map<String, Integer> mapaDva = new HashMap<>();

    // String array that will hold words of each line of our .txt file
    String[] line;

    // we loop until we reach end of our .txt file
    while(in.hasNextLine()){

        // check if map already contains given key, if it does
        // increment value by 1 otherwise initialize the value with 1
        if (mapa.put((line = in.nextLine().split(" "))[0], line[1]) != null)
            mapaDva.put(line[0], mapaDva.get(line[0])+1);
        else
            mapaDva.put(line[0], 1);
    }

    // loop through our maps and print out keys, number of 
    //repetitions, last assigned value
    for (Map.Entry<String, String> m : mapa.entrySet()){
        System.out.println(m.getKey() + " " + mapaDva.get(m.getKey()) + " " + m.getValue());
    }

如果这段代码有什么具体不清楚的地方，请询问。

示例输入文件：

key1 abcd
key2 zzz
key1 tommy
key3 world

完成后输出：

key1 2 tommy
key2 1 zzz
key3 1 world

编辑 2（处理多个文件时的解决方案）：

 // array of File objects that hold path to all your files to iterate through
    File[] files = {new File("file1.txt"),
                    new File("file2.txt"),
                    new File("file3.txt")};

    Scanner in;
    Map<String, String> mapa = new TreeMap<>();
    Map<String, Integer> mapaDva = new HashMap<>();
    String[] line;

    for (int i = 0; i < files.length; i++) {
        // assign new File to Scanner on each iteration (go through our File array)
        in = new Scanner(files[i]);
        while(in.hasNextLine()){
            if (mapa.put((line = in.nextLine().split(" "))[0], line[1]) != null)
                mapaDva.put(line[0], mapaDva.get(line[0])+1);
            else
                mapaDva.put(line[0], 1);
        }
    }



    for (Map.Entry<String, String> m : mapa.entrySet()){
        System.out.println(m.getKey() + " " + mapaDva.get(m.getKey()) + " " + m.getValue());
    }

所以我们将所有的 File 对象存储在我们的 File 数组中，我们遍历每个对象，组合所有内容并打印出最终结果：

3 个示例输入文件：

file1.txt

key1 abcd
key2 zzz
key1 tommy
key3 world

file2.txt

key1 abc
key3 xxx
key1 tommy
key6 denver

file3.txt

key5 lol
key8 head
key6 tommy
key6 denver

输出：

key1 4 tommy
key2 1 zzz
key3 2 xxx
key5 1 lol
key6 3 denver
key8 1 head

如何根据键值对合并文件并使用 Java 对其进行排序？

How to merge files based on key value pairs and also sort it using Java?

java

sorting

file

external-sorting