如何对N个文件进行排序

Question

如何对N个文件进行排序

javaalgorithm

3

以下是答案 -->

如何对大型文件进行排序

我只需要在磁盘上已经排序好的N个文件中使用Merge函数，将它们排序到一个大文件中。我的限制是内存不超过K行(K < N)，所以我不能获取所有行然后再排序，最好使用Java。

到目前为止，我尝试了下面的代码，但我需要一种很好的方法逐行迭代所有N个文件(在内存中不超过K行) + 将最终排序后的文件存储到磁盘上。

       public void run() {
            try {
                System.out.println(file1 + " Started Merging " + file2 );
                FileReader fileReader1 = new FileReader(file1);
                FileReader fileReader2 = new FileReader(file2);

                //......TODO with N ?? ......

                FileWriter writer = new FileWriter(file3);
                BufferedReader bufferedReader1 = new BufferedReader(fileReader1);
                BufferedReader bufferedReader2 = new BufferedReader(fileReader2);
                String line1 = bufferedReader1.readLine();
                String line2 = bufferedReader2.readLine();
                //Merge 2 files based on which string is greater.
                while (line1 != null || line2 != null) {
                    if (line1 == null || (line2 != null && line1.compareTo(line2) > 0)) {
                        writer.write(line2 + "\r\n");
                        line2 = bufferedReader2.readLine();
                    } else {
                        writer.write(line1 + "\r\n");
                        line1 = bufferedReader1.readLine();
                    }
                }
                System.out.println(file1 + " Done Merging " + file2 );
                new File(file1).delete();
                new File(file2).delete();
                writer.close();
            } catch (Exception e) {
                System.out.println(e);
            }
        }

敬礼，

- VitalyT

你能在内存中存储N行吗？还是K < N？ - ciamej

@ciamej，假设我们只能存储K行（K<N），如果不可能，则为N，但最好是K。 - VitalyT

2个回答

0

@Holger的回答很好，假设K>=N。

你可以通过使用BufferedInputStream的mark(int)和reset()方法来扩展到K<N的情况。

mark的参数是单行可以有多少个字节。

思路如下：

不是将所有的N行都放入TreeMap中，而是只有K行。每当你将一行新数据放入集合中时，如果它已经“满了”，则从中排除最小的一行，并重置其来源流。因此，当你再次读取它时，相同的数据可能会出现。

你必须跟踪未保留在TreeSet中的最大行，称之为下界。一旦TreeSet中没有大于维护下限的元素，就要再次扫描所有文件并重新填充集合。

我不确定这种方法是否最优，但应该还可以。

此外，你必须意识到BufferedInputStream内部有一个至少与单行大小相同的缓冲区，这将消耗大量内存，也许自己维护缓冲区会更好。

- ciamej

1

你需要在BufferedReader上使用mark(int)和reset()方法，而不是在BufferedInputStream上使用。但是，使用这些方法意味着该行仍然在内存中，因为这些方法的工作原理就是如此。实际上，正如你所说，缓冲区的大小总是比行的长度大，这就是我说的，试图节省行的内存很少会导致实际节省。你需要确保没有超过K个BufferedReader实例，才能获得实际的节省效果。正如我在答案的结尾所说，你可以将文件合并到一个临时文件中，以实际节省内存... - Holger

@Holger 可能几个合并会更好。然而，我很好奇在某些情况下，如果我的方法可以更好，假设 BufferedReader 被一些自定义代码替换。然后，当然，驱逐一行将意味着与该行相关联的缓冲区被处理掉，只保留一个表示给定文件中位置的整数。 - ciamej

1

也没有便宜的方法来寻找字符位置。除非你实现自己的字符集处理，假设一个8位字符集（或至少是固定字节数，即不是UTF-8）。你将不得不自己完成很多事情。 - Holger

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Holger · Accepted Answer

你可以使用类似如下的方式：

您可以采用以下方法之一：

public static void mergeFiles(String target, String... input) throws IOException {
    String lineBreak = System.getProperty("line.separator");
    PriorityQueue<Map.Entry<String,BufferedReader>> lines
        = new PriorityQueue<>(Map.Entry.comparingByKey());
    try(FileWriter fw = new FileWriter(target)) {
        String header = null;
        for(String file: input) {
            BufferedReader br = new BufferedReader(new FileReader(file));
            String line = br.readLine();
            if(line == null) br.close();
            else {
                if(header == null) fw.append(header = line).write(lineBreak);
                line = br.readLine();
                if(line != null) lines.add(new AbstractMap.SimpleImmutableEntry<>(line, br));
                else br.close();
            }
        }
        for(;;) {
            Map.Entry<String, BufferedReader> next = lines.poll();
            if(next == null) break;
            fw.append(next.getKey()).write(lineBreak);
            final BufferedReader br = next.getValue();
            String line = br.readLine();
            if(line != null) lines.add(new AbstractMap.SimpleImmutableEntry<>(line, br));
            else br.close();
        }
    }
    catch(Throwable t) {
        for(Map.Entry<String,BufferedReader> br: lines) try {
            br.getValue().close();
        } catch(Throwable next) {
            if(t != next) t.addSuppressed(next);
        }
    }
}

请注意，与您问题中的代码不同，此代码处理标题行。与原始代码一样，它将删除输入行。如果这不是预期的结果，您可以删除 DELETE_ON_CLOSE 选项，并将整个读取器构造简化为
BufferedReader br = new BufferedReader(new FileReader(file)); 它在内存中具有与文件数量相同的行数。

虽然原则上可以在需要时保留较少的行字符串以便重新读取，但由于已经有 N 个字符串在内存中，因为您有 N 个文件名，这将导致性能灾难并且节省很少的空间。

但是，如果您想要尽可能减少同时保存的行数，您可以简单地使用问题中显示的方法。将前两个文件合并成一个临时文件，将该临时文件与第三个文件合并到另一个临时文件中，依此类推，直到将临时文件与最后一个输入文件合并到最终结果。然后，您最多只有两个行字符串在内存中（K == 2），比操作系统用于缓冲的内存更少，尝试缓解此方法的可怕性能。

同样，您可以使用上面显示的方法将 K 个文件合并成一个临时文件，然后将该临时文件与下一个 K-1 个文件合并，依此类推，直到将临时文件与剩余的 K-1 个或更少文件合并到最终结果，以具有与 K < N 相关的内存消耗。此方法允许调整 K 以获得与 N 合理比例的内存和速度之间的平衡。我认为，在大多数实际情况下，K == N 就足够了。