logo标签列表

如何在Java中加速外部归并排序

javaalgorithmsortingmergesort
4

我正在编写外部归并排序的代码。其思想是输入文件包含太多数字无法存储在数组中，因此您需要读取其中一些内容并将其放入文件中进行存储。以下是我的代码。虽然它运行得很快，但速度还不够快。请问您是否能想到任何改进代码的方法？请注意，首先，我将每1m个整数排序在一起，因此跳过了合并算法的迭代。

import java.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.DataInputStream;
import java.io.DataOutputStream;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.RandomAccessFile;
import java.security.DigestInputStream;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.Arrays;

public class ExternalSort {

    public static void sort(String f1, String f2) throws Exception {
        RandomAccessFile raf1 = new RandomAccessFile(f1, "rw");
        RandomAccessFile raf2 = new RandomAccessFile(f2, "rw");
        int fileByteSize = (int) (raf1.length() / 4);
        int size = Math.min(1000000, fileByteSize);
        externalSort(f1, f2, size);  
        boolean writeToOriginal = true;
        DataOutputStream dos;
        while (size <= fileByteSize) {
            if (writeToOriginal) {
                raf1.seek(0);
                dos = new DataOutputStream(new BufferedOutputStream(
                        new MyFileOutputStream(raf1.getFD())));
            } else {
                raf2.seek(0);
                dos = new DataOutputStream(new BufferedOutputStream(
                        new MyFileOutputStream(raf2.getFD())));
            }
            for (int i = 0; i < fileByteSize; i += 2 * size) {
                if (writeToOriginal) {
                    dos = merge(f2, dos, i, size);
                } else {
                    dos = merge(f1, dos, i, size);
                }
            }
            dos.flush();
            writeToOriginal = !writeToOriginal;
            size *= 2;
        }
        if (writeToOriginal)
        {
            raf1.seek(0);
            raf2.seek(0);
            dos = new DataOutputStream(new BufferedOutputStream(
                    new MyFileOutputStream(raf1.getFD())));
            int i = 0;
            while (i < raf2.length() / 4){
                dos.writeInt(raf2.readInt());
                i++;
            }   
            dos.flush();
        }
    }

    public static void externalSort(String f1, String f2, int size) throws Exception{

        RandomAccessFile raf1 = new RandomAccessFile(f1, "rw");
        RandomAccessFile raf2 = new RandomAccessFile(f2, "rw");

        int fileByteSize = (int) (raf1.length() / 4);

        int[] array = new int[size];
        DataInputStream dis = new DataInputStream(new BufferedInputStream(
                new MyFileInputStream(raf1.getFD())));
        DataOutputStream dos = new DataOutputStream(new BufferedOutputStream(
                new MyFileOutputStream(raf2.getFD())));

        int count = 0;
        while (count < fileByteSize){
            for (int k = 0; k < size; ++k){
                array[k] = dis.readInt();
            }
            count += size;
            Arrays.sort(array);
            for (int k = 0; k < size; ++k){
                dos.writeInt(array[k]);
            }       
        }
        dos.flush();
        raf1.close();
        raf2.close();
        dis.close();
        dos.close();
    }

    public static DataOutputStream merge(String file,
            DataOutputStream dos, int start, int size) throws IOException {
        RandomAccessFile raf = new RandomAccessFile(file, "rw");
        RandomAccessFile raf2 = new RandomAccessFile(file, "rw");

        int fileByteSize = (int) (raf.length() / 4);
        raf.seek(4 * start);
        raf2.seek(4 *start);
        DataInputStream dis = new DataInputStream(new BufferedInputStream(
                new MyFileInputStream(raf.getFD())));
        DataInputStream dis3 = new DataInputStream(new BufferedInputStream(
                new MyFileInputStream(raf2.getFD())));
        int i = 0;
        int j = 0;
        int max = size * 2;

        int a = dis.readInt();

        int b;
        if (start + size < fileByteSize) {
            dis3.skip(4 * size);
            b = dis3.readInt();
        } else {
            b = Integer.MAX_VALUE;
            j = size;
        }
        while (i + j < max) {
            if (j == size || (a <= b && i != size)) {
                dos.writeInt(a);
                i++;
                if (start + i == fileByteSize) {
                    i = size;
                } else if (i != size) {
                    a = dis.readInt();
                }
            } else {
                dos.writeInt(b);
                j++;
                if (start + size + j == fileByteSize) {
                    j = size;
                } else if (j != size) { 

                    b = dis3.readInt();
                }
            }
        }
        raf.close();
        raf2.close();
        return dos;
    }

    public static void main(String[] args) throws Exception {
        String f1 = args[0];
        String f2 = args[1];

        sort(f1, f2);

     }
}
你有什么性能期望？这些文件中有多少个整数？ - Qwerky
4个回答
2

您可能希望一次合并k>2个段。这将把I/O量从n log k / log 2减少到n log n / log k。

编辑：以伪代码的形式，可能如下所示：

void sort(List list) {
    if (list fits in memory) {
        list.sort();
    } else {
        sublists = partition list into k about equally big sublists
        for (sublist : sublists) {
            sort(sublist);
        }
        merge(sublists);
    }
}

void merge(List[] sortedsublists) {
    keep a pointer in each sublist, which initially points to its first element
    do {
        find the pointer pointing at the smallest element
        add the element it points to to the result list
        advance that pointer
    } until all pointers have reached the end of their sublist
    return the result list
}

为了高效地找到“最小的”指针，您可以使用PriorityQueue。
这将略微提高速度，但我需要巨大的提升...这可能与进行IO读取有关。 - SuperString
1

我会使用内存映射文件。它可以比使用此类型的IO快10倍。我怀疑在这种情况下它也会更快。映射缓冲区使用虚拟内存而不是堆空间来存储数据，可以比您可用的物理内存更大。

2
如果他有足够的内存将文件映射到内存中，那么他就有足够的内存将文件读入程序中的内存。 - Alexander Kjäll
我不熟悉那个，请问你能解释一下如何做吗？ - SuperString
1
正如我所说，内存映射缓冲区不受计算机物理内存的限制。（而且它们可以更快）它们受虚拟内存大小的限制，因此32位JVM仅限于几GB，但64位JVM实际上受到磁盘容量大小的限制。@AlexanderKjäll - Peter Lawrey
实际上，出于这个课程的目的，我不应该这样做。 - SuperString
3
@SuperString，如果是这样的话，您应该将其标记为“[作业]”。 - Peter Lawrey
1
我们已经在Java中实现了一个公共领域的外部排序：

http://code.google.com/p/externalsortinginjava/

它可能比你的更快。我们使用字符串而不是整数，但你可以轻松地通过将整数替换为字符串来修改我们的代码（设计时考虑了可被黑客入侵）。至少，你可以将其与我们的设计进行比较。

看着你的代码，似乎你正在以整数单位读取数据。所以我猜IO会成为瓶颈。对于外部存储算法，你需要读写数据块，尤其是在Java中。

是的，我认为我同意你关于读取数据块的观点...具体该如何实现呢？ - SuperString
如果您查看我们的源代码，您会发现我们使用缓冲区。我们创建了自定义类来存储数据块。（我们的代码并不是那么复杂。请看一下！） - Daniel Lemire
@DanielLemire，感谢您的工作。我看到您的实现是单线程的，但我们可以并行地对文件的两个部分进行排序，所以我现在正在尝试编写一个并发的多线程版本。您认为呢？ - yetanothercoder
@yetanothercoder 我们有一个并行化版本，但它只在Java 8下运行：https://github.com/lemire/externalsortinginjava8。目前它不可通过Maven仓库获得（因为需要Java 8）。我主要的问题是我不知道如何使Java代码具备可移植性，以便在Java 8可用时使用同一库，否则回退到在Java 6下运行的代码。 - Daniel Lemire
0
你正在对整数进行排序，因此你应该看一下基数排序。基数排序的核心思想是使用256进制，通过n次对数据的遍历来排序n字节的整数。
你可以将其与归并排序理论相结合。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接