7

我正在寻找一种方法来洗牌大量不适合内存的数据（大约 40GB）。

我有大约 3000 万个长度可变的条目，存储在一个大文件中。我知道该文件中每个条目的开始和结束位置。我需要对这些不适合 RAM 的数据进行洗牌。

我想到的唯一解决方案是使用Fisher-Yates 算法1对包含从到的数字N（其中N是条目数）的数组进行洗牌，然后根据此顺序将条目复制到新文件中。不幸的是，这个解决方案涉及大量的查找操作，因此会非常慢。

有没有更好的解决方案来混洗大量均匀分布的数据？

4

6 回答 6

5

首先shuffle从你的脸上解决这个问题。通过为您的条目发明一种产生类似随机结果的散列算法来做到这一点，然后对散列进行正常的外部排序。

现在，您已将您的问题shuffle转变sort为寻找适合您的口袋和内存限制的有效外部排序算法。现在应该像google.

于 2013-01-31T14:41:05.033 回答
4

一个简单的方法是选择一个合适的数据在内存中K。1/K也许K=4对于您的数据，假设您有 16GB 的 RAM。我假设您的随机数函数具有从tornd(n)生成统一随机数的形式。0n-1

然后：

for i = 0 .. K-1
   Initialize your random number generator to a known state.
   Read through the input data, generating a random number rnd(K) for each item as you go.
   Retain items in memory whenever rnd(K) == i.
   After you've read the input file, shuffle the retained data in memory.
   Write the shuffled retained items to the output file.

这很容易实现，会避免大量的寻找，而且显然是正确的。

另一种方法是根据随机数将输入数据划分为K文件，然后遍历每个文件，在内存中洗牌并写入磁盘。这减少了磁盘 IO（每个项目被读取两次并写入两次，与第一种方法相比，每个项目被读取 K 次并写入一次），但您需要小心缓冲 IO 以避免大量查找，它使用更中间的磁盘，并且实现起来有些困难。如果您只有 40GB 的数据（所以K很小），那么对输入数据进行多次迭代的简单方法可能是最好的。

如果使用 20ms 作为读取或写入 1MB 数据的时间（并假设内存中的 shuffle 成本微不足道），简单的方法将花费 40*1024*(K+1)*20ms，即 1 分 8 秒（假设K=4）。中间文件方法将花费 40*1024*4*20ms，大约是 55 秒，假设您可以最小化查找。请注意，SSD 的读取和写入速度大约快 20 倍（即使忽略搜索），因此您应该期望使用 SSD 在 10 秒内执行此任务。每个程序员都应该知道的延迟数字中的数字

于 2018-05-19T08:44:41.640 回答
2

前提

据我了解，使用 Fisher-Yates 算法和您拥有的有关条目位置的数据，您应该能够获得（并计算）以下列表：

struct Entry {
    long long sourceStartIndex;
    long long sourceEndIndex;
    long long destinationStartIndex;
    long long destinationEndIndex;
}

问题

从这一点开始，天真的解决方案是寻找源文件中的每个条目，读取它，然后寻找目标文件中条目的新位置并写入它。

这种方法的问题在于它使用了太多的搜索。

解决方案

一个更好的方法是减少查找次数，为每个文件使用两个巨大的缓冲区。

我建议源文件使用一个小缓冲区（比如 64MB），目标文件使用一个大缓冲区（用户可以承受的最大 - 比如 2GB）。

最初，目标缓冲区将映射到目标文件的前 2GB。此时，在源缓冲区中以 64MB 的块读取整个源文件。阅读时，将正确的条目复制到目标缓冲区。当您到达文件末尾时，输出缓冲区应该包含所有正确的数据。将其写入目标文件。

接下来，将输出缓冲区映射到目标文件的下一个 2GB 并重复该过程。继续，直到您编写了整个输出文件。

警告

由于条目具有任意大小，因此在缓冲区的开头和结尾很可能会有条目的后缀和前缀，因此您需要确保正确复制数据！

估计时间成本

执行时间基本上取决于源文件的大小、应用程序的可用 RAM 和 HDD 的读取速度。假设一个 40GB 的文件、2GB 的 RAM 和 200MB/s 的 HDD 读取速度，程序将需要读取 800GB 的数据（40GB * (40GB / 2GB)）。假设 HDD 不是高度碎片化的，则用于寻道的时间可以忽略不计。这意味着读取将占用一小时！但是，如果幸运的是，用户有 8GB 的​​ RAM 可用于您的应用程序，则时间可能会减少到仅 15 到 20 分钟。

我希望这对你来说已经足够了，因为我没有看到任何其他更快的方法。

于 2013-02-02T01:01:40.070 回答
2

我建议保留您的一般方法，但在进行实际复制之前反转地图。这样，您可以按顺序阅读并进行分散的写入，而不是相反。

在程序可以继续之前，必须在请求时完成读取。可以将写入留在缓冲区中，从而增加在实际执行写入之前对同一磁盘块累积多次写入的可能性。

于 2013-01-31T14:42:14.210 回答
1

尽管您可以按照OldCurmudgeon的建议对随机键使用外部排序，但随机键不是必需的。您可以将内存中的数据块打乱，然后按照aldel的建议通过“随机合并”将它们连接起来。

值得更清楚地说明“随机合并”的含义。给定两个大小相等的混洗序列，随机合并的行为与合并排序中的完全相同，不同之处在于，要添加到合并列表中的下一项是使用来自 0 和 1 的混洗序列中的布尔值选择的，完全一样许多零作为一。（在合并排序中，将使用比较进行选择。）

证明它

我断言这行得通是不够的。我们怎么知道这个过程给出了一个打乱的序列，这样每个排序都是同样可能的？可以用图表和一些计算给出证明草图。

首先，定义。假设我们有N唯一的项目，其中N是偶数，并且M = N / 2。这些项目以两个标记的项目序列N提供给我们，并保证以随机顺序排列。合并它们的过程会产生一个项目序列，使得每个项目来自 sequence或 sequence ，并且相同数量的项目来自每个序列。它看起来像这样：M01N01

0: a b c d
1: w x y z
N: a w x b y c d z

请注意，虽然0和中的项目1看起来是有序的，但它们在这里只是标签，顺序并不意味着什么。它只是用来连接 的0和1的 顺序N。

由于我们可以从标签中分辨出每个项目来自哪个序列，因此我们可以创建一个由 0 和 1 组成的“源”序列。叫那个c。

c: 0 1 1 0 1 0 0 1

根据上面的定义，在c.

现在观察，对于 中任何给定的标签顺序N，我们可以直接复制一个c序列，因为标签保留了它们来自的序列的信息。并且给定Nand c，我们可以重现0and1序列。所以我们知道从一个序列N到一个三元组总是有一条路径(0, 1, c)。换句话说，我们定义了一个反向函数r，从标签的所有排序集合N到三元组(0, 1, c)—— r(N) = (0, 1, c)。

我们还有一个f来自任何三元组的前向函数，它可以根据 的值简单地r(n)重新合并。这两个函数一起表明，在 的输出和 的排序之间存在一一对应的关系。01cr(N)N

但我们真正想证明的是，这种一一对应是详尽无遗的——也就是说，我们想证明不存在N不对应于任何三元组的额外排序，并且不存在与 .的任何排序不对应的额外三元组N。如果我们能证明这一点，那么我们可以N通过以均匀随机方式选择三元组(0, 1, c)来以均匀随机方式选择排序。

我们可以通过计算 bin 来完成证明的最后一部分。假设每个可能的三元组都有一个 bin。然后我们将每一个排序都N放在 bin 中，以获得r(N)给我们的三元组。如果 bin 的数量与 orderings 的数量完全相同，那么我们就有了详尽的一对一对应关系。

从组合学中，我们知道N唯一标签的排序数是N!。我们也知道 和 的排序0数1都是M!。我们知道可能的序列数c是N choose M，与 相同N! / (M! * (N - M)!)。

这意味着总共有

M! * M! * N! / (M! * (N - M)!)

三倍。但是N = 2 * M, 所以N - M = M, 以上简化为

M! * M! * N! / (M! * M!)

那只是N!。QED。

执行

要以均匀随机的方式选取三元组，我们必须以均匀随机的方式选取三元组的每个元素。对于0和，我们在内存1中使用简单的Fisher-Yates 洗牌来实现这一点。唯一剩下的障碍是生成正确的 0 和 1 序列。

这很重要——重要！-- 仅生成具有相同数量的零和一的序列。否则，您没有从Choose(N, M)具有统一概率的序列中进行选择，并且您的 shuffle 可能会出现偏差。最明显的方法是对包含相等数量的 0 和 1 的序列进行洗牌......但问题的整个前提是我们无法在内存中容纳那么多的 0 和 1！因此，我们需要一种方法来生成零和一的随机序列，这些随机序列受到约束，使得零与一完全相同。

为了以概率一致的方式做到这一点，我们可以模拟从瓮中绘制标记为 0 或 1 的球，无需替换。假设我们从五十0个球和五十1个球开始。如果我们对瓮中每种球的数量进行计数，就可以保持一个选择其中一个的运行概率，这样最终的结果就不会有偏差。（可疑的类似 Python 的）伪代码将是这样的：

def generate_choices(N, M):
    n0 = M
    n1 = N - M
    while n0 + n1 > 0:
        if randrange(0, n0 + n1) < n0:
            yield 0
            n0 -= 1
        else:
            yield 1
            n1 -= 1

由于浮点错误，这可能并不完美，但它会非常接近完美。

算法的最后一部分至关重要。详尽地通过上述证明清楚地表明，其他生成 1 和 0 的方法不会给我们适当的洗牌。

在真实数据中执行多次合并

还有一些实际问题。上面的论点假设了一个完美平衡的合并，它还假设你的数据只有内存的两倍。这两种假设都不太可能成立。

事实证明，拳头并不是一个大问题，因为上述论点实际上并不需要相同大小的列表。只是如果列表大小不同，计算会稍微复杂一些。如果你通过上面的替换forM列表，所有细节都以相同的方式排列。（伪代码的编写方式也适用于任何大于零和小于 的情况。然后将恰好是零和一。）1N - MMNMM - N

第二个意味着在实践中，可能会有很多很多块以这种方式合并。该过程继承了合并排序的几个属性——特别是，它要求对于K块，您必须执行粗略的K / 2合并，然后K / 4合并，依此类推，直到所有数据都被合并。每批合并将遍历整个数据集，并且将大致有log2(K)批，运行时间为O(N * log(K)). 一个普通的 Fisher-Yates 洗牌在 中是严格线性的N，因此理论上对于非常大的 来说会更快K。但是在K变得非常非常大之前，惩罚可能比磁盘搜索惩罚要小得多。

因此，这种方法的好处来自智能 IO 管理。而对于 SSD，它甚至可能不值得——寻找惩罚可能不足以证明多次合并的开销是合理的。Paul Hankin的回答为思考提出的实际问题提供了一些实用技巧。

一次合并所有数据

进行多个二进制合并的另一种方法是一次合并所有块——这在理论上是可能的，并且可能会导致一种O(N)算法。值的随机数生成算法c需要从 到 生成标签，0以便K - 1最终输出具有每个类别的正确标签数量。（换句话说，如果您将三个块与10、12和13项目合并，那么 的最终值c将需要有010 倍、112 倍和213 倍。）

我认为可能有一种O(N)时间、O(1)空间算法可以做到这一点，如果我能找到或解决一个问题，我会在这里发布。结果将是一个真正的O(N)洗牌，就像保罗汉金在他的回答结尾所描述的那样。

于 2018-05-18T23:36:53.200 回答
-1
  • 对您的数据库条目进行逻辑分区（例如按字母顺序）
  • 根据您创建的分区创建索引
  • 构建DAO以基于索引敏感
于 2013-01-31T14:27:30.517 回答