使用外部排序算法进行排序的预期时间

Question

有谁知道排序的最短预期时间（以秒为单位？）比方说 32 位整数的 64MB 二进制文件，这意味着在不使用任何内部排序算法或数据结构的情况下按升序对 16777216 个值进行排序可以触发 "Out of memory exceptions"？只是两个辅助文件中的数据分布，然后将它们合并在一起以产生最终的排序序列 - 这就是直接外部合并排序与 k 重复的工作方式。

关于算法的一些更多假设是它是用 Java 编写的，它使用缓冲的读写器并且它是运行在具有 5GB 内存的双核 Windows 机器上，剩下的取决于算法在理论上的工作方式。

我知道这个问题有点奇怪，但我希望可以估计一些最短的时间？如果此处需要更多信息，请询问。

谢谢！

Answer 1

您应该考虑使用 ObjectInputStream。它会更简单、更快，并且因为 Integer 实现了 Serializable，所以它变得更容易。参见：

long howLong(String path) throws IOException, ClassCastException{
   long start = System.currentTimeMillis();
   ObjectInputStream ois = new ObjectInputStream(new FileInputStream(new File(path)));

   List<Integer> allInts = new ArrayList<>();
   while(ois.ready()){
       allInts.add((Integer)ois.readObject());
   }
   ois.close();
   sortList(allInts);

   ObjectOuputStream oos = new ObjectOutputStream(new FileOutputStream(newFile(path)));

   for(Integer i:allInts){
       oos.writeObject(i);
   }
   oos.close();
   long end = System.currentTimeMillis();       

   //returns how long the alg took
   return (end-start)/1000;
}

private <E extends Comparable<E>> void sortList(List<E> l){
    boolean sorted;
    while(!sorted){
        soreted=true;
        for(int i=0,n=l.size()-1;i<n;i++){

            if(arr1[i].compareTo(arr1[i+1])>0){
                E tmp = l.get(i);
                l.get(i) = l.get(i+1);
                l.get(i+1) = tmp;

                sorted = false;
            }
        }

    }


}

在您的计算机上尝试运行，看看效果如何 returns。输出将在秒 .

内

Answer 2

对于典型的外部排序，I/O 时间通常是您的限制因素。执行外部排序所需的最少时间——如果使用标准算法——是读取和写入整个输入文件两次所需的时间。

考虑一下它分两次完成的外部排序。在第一遍中，输入文件以固定大小的块为单位读取。当每个块被读取时，它被排序，然后写入一个临时文件。在第一遍结束时，输入文件中的每个项目都被读取一次，并写入一次。

在第二遍中，使用 k 向合并将临时文件组合成单个排序的输出文件。同样，每个项目再次从磁盘读取一次，并写入磁盘一次。

如果输入文件已经排序，并且块排序算法实现得很好，那么对单个块进行排序的时间几乎为零。与合并相同：已排序的文件是 k 向合并的最佳情况。

在现代桌面硬件上，每 GB 的读取时间约为 20 秒，写入时间可能翻倍。因此，您应该期望每 GB 大约一分钟的绝对最短时间。你可以自己做一些读取和写入大文件的基准测试，但你必须要么击败 OS 的文件缓存，要么以某种方式考虑到这一点。否则你得不到好数字。

排序和合并当然需要时间。您可以通过创建一个您想到的任何块大小的数组来估计每个块将花费多少时间来排序，然后重复用随机数填充它然后对其进行排序。计算完成 10 次或 100 次排序需要多长时间，然后取平均值。这将是一个合理的估算数字。

根据我的经验，对合并 k 个块（即第二遍）所需时间的良好估计非常接近复制输入文件所需的时间乘以 log(log(块数)) :

merge time = (copy time) * (log₂(log₂(number of blocks)))

假设我有一个 1 GB 的文件，我正在使用 64 MB 的块。所以有 16 个块要合并。我已经确定复制 1 GB 需要一分钟。因此，对执行合并所需时间的一个很好的估计是一分钟乘以 log₂(log₂(16))。 log(log(16)) 等于 2，因此合并 16 个输入文件所花的时间大约是复制合并大小的单个文件所花时间的两倍。

当你把它们放在一起时，你最终会得到以下估计使用块大小 S 对文件大小 S 进行典型外部排序所需的时间 B

复制（读取和写入）大小为 S 的文件的时间；加上
排序 S/B 个块的时间；加上
复制（读取和写入）大小为 S 的文件的时间，时间为 log₂(log₂(S/B))

顺便说一下，进行我上面提到的块排序基准测试很重要。例如，整数通常比字符串排序快得多，前几个字符差异很大的字符串比前 20 个字符相同的字符串排序快得多。当运行你的基准时，使用尽可能接近真实数据的数据总是一个好主意。

使用外部排序算法进行排序的预期时间

Expected time of sorting with external sort algorithm

java

sorting

algorithm

external