合并排序的文件Java

无穷

即时通讯使用Java实现外部合并排序。

因此,给定一个文件,我将其拆分为较小的文件,然后对较小的部分进行排序,最后合并已排序(较小)的文件。

因此,最后一步是我遇到的麻烦。

我有一个文件列表,我想在每个步骤中,取每个文件的第一行的最小值,然后删除该行。

因此,应该是这样的:

public static void mergeSortedFiles(List<File> sorted, File output) throws IOException {
    BufferedWriter wf = new BufferedWriter(new FileWriter(output));
    String curLine = "";
    while(!sorted.isEmpty()) {
        curLine = findMinLine(sorted);
        wf.write(curLine);
    }
}

public static String findMinLine(List<File> sorted) throws IOException {
    List<BufferedReader> brs = new ArrayList<>();
    for(int i =0; i<sorted.size() ; i++) {
        brs.add(new BufferedReader(new FileReader(sorted.get(i))));
    }
    List<String> lines = new ArrayList<>();
    for(BufferedReader br : brs) {
        lines.add(br.readLine());
    }
    Collections.sort(lines);
    return lines.get(0);
}

我不确定如何更新文件,有人可以提供帮助吗?

感谢您的帮助!

你说

您可以Comparable围绕每个文件创建包装器,然后将包装器放置在堆中(例如PriorityQueue)。

public class ComparableFile<T extends Comparable<T>> implements Comparable<ComparableFile<T>> {
    private final Deserializer<T> deserializer;
    private final Iterator<String> lines;
    private T buffered;

    public ComparableFile(File file, Deserializer<T> deserializer) {
        this.deserializer = deserializer;
        try {
            this.lines = Files.newBufferedReader(file.toPath()).lines().iterator();
        } catch (IOException e) {
            // deal with it differently if you want, I'm just providing a working example
            // and wanted to use the constructor in a lambda function
            throw new UncheckedIOException(e);
        }
    }

    @Override
    public int compareTo(ComparableFile<T> that) {
        T mine = peek();
        T theirs = that.peek();

        if (mine == null) return theirs == null ? 0 : -1;
        if (theirs == null) return 1;
        return mine.compareTo(theirs);
    }

    public T pop() {
        T tmp = peek();

        if (tmp != null) {
            buffered = null;
            return tmp;
        }

        throw new NoSuchElementException();
    }

    public boolean isEmpty() {
        return peek() == null;
    }

    private T peek() {
        if (buffered != null) return buffered;
        if (!lines.hasNext()) return null;
        return buffered = deserializer.deserialize(lines.next());
    }
}

然后,您可以通过以下方式合并它们:

public class MergeFiles<T extends Comparable<T>> {
    private final PriorityQueue<ComparableFile<T>> files;

    public MergeFiles(List<File> files, Deserializer<T> deserializer) {
        this.files = new PriorityQueue<>(files.stream()
                .map(file -> new ComparableFile<>(file, deserializer))
                .filter(comparableFile -> !comparableFile.isEmpty())
                .collect(toList()));
    }

    public Iterator<T> getSortedElements() {
        return new Iterator<T>() {
            @Override
            public boolean hasNext() {
                return !files.isEmpty();
            }

            @Override
            public T next() {
                if (!hasNext()) throw new NoSuchElementException();
                ComparableFile<T> head = files.poll();
                T next = head.pop();
                if (!head.isEmpty()) files.add(head);
                return next;
            }
        };
    }
}

这是一些代码来演示它的工作原理:

public static void main(String[] args) throws IOException {
    List<File> files = Arrays.asList(
            newTempFile(Arrays.asList("hello", "world")),
            newTempFile(Arrays.asList("english", "java", "programming")),
            newTempFile(Arrays.asList("american", "scala", "stackoverflow"))
    );

    Iterator<String> sortedElements = new MergeFiles<>(files, line -> line).getSortedElements();
    while (sortedElements.hasNext()) {
        System.out.println(sortedElements.next());
    }
}

private static File newTempFile(List<String> words) throws IOException {
    File tempFile = File.createTempFile("sorted-", ".txt");
    Files.write(tempFile.toPath(), words);
    tempFile.deleteOnExit();
    return tempFile;
}

输出:

american
english
hello
java
programming
scala
stackoverflow
world

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章