0

我正在尝试了解快速排序的外部版本（当数据无法放入主内存时）。我在外部快速排序过程的Wiki上找到了以下链接和类似的解释：

定义：将 M/2 的第一个和最后一个元素读入缓冲区（缓冲区的作用类似于快速排序中的枢轴），并对它们进行排序。从头或尾读取下一个元素以平衡书写。如果下一个元素小于缓冲区的最小值，则将其写入开头的可用空间。如果大于最大，就写到最后。否则写入缓冲区的最大或最小，并将下一个元素放入缓冲区。保持写入最大的下键和最小的上键，以避免使用按顺序排列的中间元素。完成后，写入缓冲区。递归地对较小的分区进行排序，并循环对剩余的分区进行排序。

我有理解它的问题：

  • 是M指主存的大小吗？我还有N-M一些驱动器上的剩余元素？

  • The buffer acts like the pivot in quicksort- 这是否意味着我需要N-M将驱动器中的剩余元素分成两部分a，并且b其中的元素a低于缓冲区中的所有元素，而元素中的元素b大于或等于缓冲区中的最大元素？

  • Read the next element from the beginning or end to balance writing.平衡写作是什么意思？应该从缓冲区（内存）还是从驱动器中读取下一个元素？

  • Otherwise write the greatest or least of the buffer, and put the next element in the buffer- 如果我将下一个元素放入缓冲区（已经排序），我需要再次对缓冲区进行排序吗？

一些它如何工作的例子或更好的解释将非常有用。

4

1 回答 1

1

注意 - 我不知道任何使用快速排序进行外部排序的库，所以这主要是一个教育练习。

维基文章提到磁带，但这是错误的。不可能在合理的时间内从磁带上数据的两端读取数据，并且不可能在不破坏数据之后的现有数据的情况下覆盖磁带上的数据。因此，请将此视为对硬盘驱动器或 SSD 类型设备上的文件进行的外部排序，具有随机访问和就地覆盖数据的能力。

是M指主存的大小吗？

根据上下文，工作内存区域的大小为 M·sizeof(element)。需要有额外的可用内存才能在不覆盖缓冲区的情况下读取元素。

某些驱动器上的“NM”元素？

是的，由于内存只能保存 M 个元素，因此 NM 个元素保留在外部设备上。

缓冲区就像快速排序中的枢轴一样？

缓冲区被排序为单次运行，缓冲区中的最小值和最大值加上刚刚读取的一个元素充当一系列枢轴值，以确定要写入的元素。

从头或尾阅读下一个元素以平衡写作。`平衡写作是什么意思？应该从缓冲区（内存）还是从驱动器中读取下一个元素？

在文件的开头或结尾有空间可以写入 M/2 个元素。读取的第一个元素可以从任一端读取。如果从头开始读取一个元素 + M/2。然后缓冲区中的最小元素在开头写入，仍然为要写入的元素留出 M/2 空间。如果从末尾读取一个元素 - M/2，则将最大元素写入文件中的最后一个元素，在末尾留出 M/2 空间用于写入元素。

此时算法存在问题。由于每个元素被读取，需要合并到 M 个元素的缓冲区中，非常慢。此问题的一种解决方案是使用最小-最大堆作为缓冲区。

https://en.wikipedia.org/wiki/Min-max_heap

最终从中间 M 个元素的两端开始写入文件，然后写入 M 元素缓冲区。此时，文件开头的所有元素都小于或等于文件结尾的所有元素，可以将文件视为2个分区。然后对每个分区进行分区，产生 4 个分区，然后是 8 个分区，以此类推，直到最终一个分区适合内存并使用正常的内存排序。

所描述的算法很慢，因为它一次读取和写入一个元素。保留部分内存以分组缓冲读取和写入会快得多。

于 2019-04-24T16:03:06.450 回答