如何从数组中创建严格排序的均匀分布的桶？
How do I create strictly ordered uniformly distributed buckets out of an array?
我想获取一个整数数组并对该数组执行部分桶排序。它之前桶中的每个元素都小于当前桶中的元素。例如，如果我有 10 个值 0-100 的桶，0-9 将放入第一个桶，10-19 放入第二个桶，依此类推。
例如，我可以将 1 12 23 44 48 放入 10 个桶中的 4 个桶中。但是如果我有 1、2、7、4、9、1，那么所有值都将放入一个桶中。我正在寻找一种在保持排序的同时将值均匀分配给所有存储桶的方法。每个桶中的元素不必排序。例如，我看起来与此类似。
2 1 9 2 3 8 7 4 2 8 11 4 => [[2, 1], [2, 2], [3], [4], [4], [7], [8 , 8], [9], [11]]
我正在尝试使用它作为在 map-reduce 中对列表进行分区的快速方法。
感谢您的帮助。
编辑，也许这会解决问题：
我想创建一个哈希函数，其中 bucket1 < bucket2 < bucket3 ... 中的所有元素，其中每个桶都是未排序的。
如果我理解正确的话，您有大约 100TB 的数据，或 13,743,895,347,200 个无符号 64 位整数，您想要将其分配到多个存储桶中。
第一步可能是迭代输入，例如查看每个整数的最高 24 位，并计算它们。这将为您提供 16,777,216 运行ges 的列表，每个 ges 的平均计数为 819,200，因此可以将它们存储在 32 位无符号整数中，这将占用 64 MB。
然后您可以使用它来创建一个查找 table，告诉您这 16,777,216 个 运行ge 分别进入了哪个存储桶。您计算每个桶中应该有多少整数（输入大小除以桶数）并遍历数组，保持 运行ning 总数，并将每个 运行ge 设置为桶 1，直到 运行ning 总数对于桶 1 来说太多，然后将 运行ges 设置为桶 2，依此类推...
当然总会有一个 运行ge 必须在 bucket n 和 bucket n+1 之间拆分。为了跟踪这一点，您创建了第二个 table 来存储这些拆分 运行ges 中有多少整数应该进入桶 n+1。
所以你现在有例如：
HIGH 24-BIT RANGE BUCKET BUCKET+1
0 0 ~ 2^40-1 1 0
1 2^40 ~ 2*2^40-1 1 0
2 2*2^40 ~ 3*2^40-1 1 0
3 3*2^40 ~ 4*2^40-1 1 0
...
16 16*2^40 ~ 17*2^40-1 1 0
17 17*2^40 ~ 18*2^40-1 1 284,724 <- highest 284,724 go into bucket 2
18 18*2^40 ~ 19*2^40-1 2 0
...
您现在可以再次遍历输入，并为每个整数查看最高 24 位，并使用查找 table 查看整数应该进入哪个桶。如果 运行ge 没有拆分，您可以立即将整数移动到正确的桶中。对于每个拆分 运行ge，您创建一个有序列表或优先级队列，它可以容纳进入下一个存储桶所需的尽可能多的整数；您仅存储此列表或队列中的最高值；任何较小的整数直接进入桶，如果一个整数被添加到完整列表或队列，最小值被移动到桶中。最后这个列表或队列被添加到下一个桶。
在可用内存的情况下，运行ges 的数量应尽可能多，因为这样可以最大限度地减少拆分 运行ges 中的整数数量。有了巨大的输入，您可能需要将拆分 运行ges 保存到磁盘，然后分别查看它们中的每一个，找到最高的 x 值，并将它们相应地移动到桶中。
第一个 运行 的复杂度为 N，然后遍历 运行ges R，然后在再次遍历输入时为 N，然后是拆分 运行ges 你会有类似 M.logM 的东西来排序，M 来分发，所以总共有 2*N + R + M.LogM + M。使用大量的 运行 ges 以保持 split 中的整数数量 运行ges 低可能是加快进程的最佳策略。
其实分裂运行ges的整数个数M取决于桶B的个数和运行ges R的个数，M=N×B/R，所以那例如对于一千个桶和一百万个 运行ges，输入的 0.1% 将处于拆分 运行ges 中并且必须进行排序。 （这些是平均值，具体取决于实际分布。） 使得总复杂度为 2×N + R + (N×B/R).Log(N×B/R) + N×B/R.
另一个例子：
Input: N = 13,743,895,347,200 unsigned 64-bit integers
Ranges: 232 (using the highest 32 bits of each integer)
Integers per range: 3200 (average)
Count list: 232 16-bit integers = 8 GB
Lookup table: 232 16-bit integers = 8 GB
Split range table: B 16-bit integers = 2×B bytes
有 1024 个桶，这意味着 B/R = 1/222，并且有 1023 个拆分 运行ge，每个大约有 3200 个整数，或总共约 3,276,800 个整数；然后必须将这些分类并分发到桶中。
有 1,048,576 个桶，这意味着 B/R = 1/212，并且有 1,048,575 个拆分 运行ge，每个大约有 3200 个整数，或总共约 3,355,443,200 个整数。 （超过 65,536 个桶当然需要使用 32 位整数进行查找 table。）
(如果你发现每个运行ge的计数总和不等于输入的总大小，说明计数列表已经溢出，你应该为计数切换到更大的整数类型。）
让我们 运行 通过一个小例子：运行ge 1-100 中的 50 个整数必须分布在 5 个桶中。我们选择一些 运行ges，比如 20，并迭代输入以计算每个 运行ges:
中整数的数量
2 9 14 17 21 30 33 36 44 50 51 57 69 75 80 81 87 94 99
1 9 15 16 21 32 40 42 48 55 57 66 74 76 88 96
5 6 20 24 34 50 52 58 70 78 99
7 51 69
55
3 4 2 3 3 1 3 2 2 3 5 3 0 4 2 3 1 2 1 3
然后，知道每个桶应该容纳 10 个整数，我们迭代每个 运行ge 的计数列表，并将每个 运行ge 分配给一个桶：
3 4 2 3 3 1 3 2 2 3 5 3 0 4 2 3 1 2 1 3 <- count/range
1 1 1 1 2 2 2 2 3 3 3 4 4 4 4 5 5 5 5 5 <- to bucket
2 1 1 <- to next
当 运行ge 必须在两个桶之间拆分时，我们将应该进入下一个桶的整数数量存储在单独的 table.
中
然后我们可以再次迭代输入，并将非拆分 运行ges 中的所有整数移动到桶中； split 运行ges 中的整数暂时移入单独的桶中：
bucket 1: 9 14 2 9 1 15 6 5 7
temp 1/2: 17 16 20
bucket 2: 21 33 30 32 21 24 34
temp 2/3: 36 40
bucket 3: 44 50 48 42 50
temp 3/4: 51 55 52 51 55
bucket 4: 57 75 69 66 74 57 57 70 69
bucket 5: 81 94 87 80 99 88 96 76 78 99
然后我们一个一个地查看临时存储桶，找到第二个 table 中指示的 x 个最高整数，将它们移至下一个存储桶，以及剩余到前一个存储桶的内容：
temp 1/2: 17 16 20 (to next: 2) bucket 1: 16 bucket 2: 17 20
temp 2/3: 36 40 (to next: 1) bucket 2: 36 bucket 3: 40
temp 3/4: 51 55 52 51 55 (to next: 1) bucket 3: 51 51 52 55 bucket 4: 55
最终结果是：
bucket 1: 9 14 2 9 1 15 6 5 7 16
bucket 2: 21 33 30 32 21 24 34 17 20 36
bucket 3: 44 50 48 42 50 40 51 51 52 55
bucket 4: 57 75 69 66 74 57 57 70 69 55
bucket 5: 81 94 87 80 99 88 96 76 78 99
因此，在 50 个整数中，我们必须对一组 3、2 和 5 个整数进行排序。
实际上，您不需要创建 table 拆分 运行ges 中应该进入下一个存储桶的整数数量。您知道应该将多少个整数放入每个桶中，因此在初始分配之后您可以查看每个桶中已经有多少个整数，然后从拆分中添加必要数量的（最小值）整数 运行格。在上面的示例中，每个桶需要 10 个整数，即：
3 4 2 3 3 1 3 2 2 3 5 3 0 4 2 3 1 2 1 3 <- count/range
1 1 1 / 2 2 2 / 3 3 / 4 4 4 4 5 5 5 5 5 <- to bucket
bucket 1: 9 14 2 9 1 15 6 5 7 <- add 1
temp 1/2: 17 16 20 <- 3-1 = 2 go to next bucket
bucket 2: 21 33 30 32 21 24 34 <- add 3-2 = 1
temp 2/3: 36 40 <- 2-1 = 1 goes to next bucket
bucket 3: 44 50 48 42 50 <- add 5-1 = 4
temp 3/4: 51 55 52 51 55 <- 5-4 = 1 goes to next bucket
bucket 4: 57 75 69 66 74 57 57 70 69 <- add 1-1 = 0
bucket 5: 81 94 87 80 99 88 96 76 78 99 <- add 0
计算有多少输入将被拆分 运行ges 并需要排序，上面给出的 M = N × B/R，是输入的平均值，大致是平均分配。轻微的偏差，在输入的特定部分有更多的值 space 不会有太大影响，但确实有可能设计最坏情况的输入来阻止算法。
让我们再看看这个例子：
Input: N = 13,743,895,347,200 unsigned 64-bit integers
Ranges: 232 (using the highest 32 bits of each integer)
Integers per range: 3200 (average)
Buckets: 1,048,576
Integers per bucket: 13,107,200
首先，如果 运行ges 包含超过 232 个整数，则必须使用 64 位整数来计算 table，因此它的大小为 32GB，这可能会迫使您使用更少的 运行ges，具体取决于可用内存。
此外，每个 运行ge 的整数比每个桶的目标大小都自动成为一个拆分 运行ge。因此，如果整数分布在很多局部簇中，您可能会发现大部分输入都在需要排序的 运行ges 中。
如果你有足够的内存来 运行 第一步使用 232 运行ges，那么每个 运行ge 有 232 个不同的值，您可以使用计数排序（具有线性复杂性）将分割 运行ges 分布在桶上。
如果你没有足够的内存来使用 232 运行ges，而你最终会得到有问题的大拆分 运行ges，你可以在拆分 运行ges 上再次使用完整的算法。假设您使用了 228 运行ges，期望每个 运行ge 包含大约 51,200 个整数，并且您最终得到了意想不到的大拆分 运行ge 有 5,120,000,000 个整数，需要分布在 391 个桶中。如果你对这个有限的 运行ge 再次 运行 算法，你将有 228 运行ges（每个平均持有 19 个整数最多 16 个不同的值）仅用于 391 个桶，并且再次出现大拆分的风险很小 运行ges。
注意：运行必须拆分为两个或更多存储桶的数据不一定要排序。你可以例如使用 Dijkstra 的荷兰国旗算法的递归版本将 运行ge 划分为具有 x 最小值的部分和具有最大值的部分。分区的平均复杂度是线性的（当使用 运行dom pivot 时），相对于排序的 O(N.LogN) 复杂度。
我想获取一个整数数组并对该数组执行部分桶排序。它之前桶中的每个元素都小于当前桶中的元素。例如，如果我有 10 个值 0-100 的桶，0-9 将放入第一个桶，10-19 放入第二个桶，依此类推。
例如，我可以将 1 12 23 44 48 放入 10 个桶中的 4 个桶中。但是如果我有 1、2、7、4、9、1，那么所有值都将放入一个桶中。我正在寻找一种在保持排序的同时将值均匀分配给所有存储桶的方法。每个桶中的元素不必排序。例如，我看起来与此类似。
2 1 9 2 3 8 7 4 2 8 11 4 => [[2, 1], [2, 2], [3], [4], [4], [7], [8 , 8], [9], [11]]
我正在尝试使用它作为在 map-reduce 中对列表进行分区的快速方法。
感谢您的帮助。
编辑，也许这会解决问题：
我想创建一个哈希函数，其中 bucket1 < bucket2 < bucket3 ... 中的所有元素，其中每个桶都是未排序的。
如果我理解正确的话，您有大约 100TB 的数据，或 13,743,895,347,200 个无符号 64 位整数，您想要将其分配到多个存储桶中。
第一步可能是迭代输入，例如查看每个整数的最高 24 位，并计算它们。这将为您提供 16,777,216 运行ges 的列表，每个 ges 的平均计数为 819,200，因此可以将它们存储在 32 位无符号整数中，这将占用 64 MB。
然后您可以使用它来创建一个查找 table，告诉您这 16,777,216 个 运行ge 分别进入了哪个存储桶。您计算每个桶中应该有多少整数（输入大小除以桶数）并遍历数组，保持 运行ning 总数，并将每个 运行ge 设置为桶 1，直到 运行ning 总数对于桶 1 来说太多，然后将 运行ges 设置为桶 2，依此类推...
当然总会有一个 运行ge 必须在 bucket n 和 bucket n+1 之间拆分。为了跟踪这一点，您创建了第二个 table 来存储这些拆分 运行ges 中有多少整数应该进入桶 n+1。
所以你现在有例如：
HIGH 24-BIT RANGE BUCKET BUCKET+1
0 0 ~ 2^40-1 1 0
1 2^40 ~ 2*2^40-1 1 0
2 2*2^40 ~ 3*2^40-1 1 0
3 3*2^40 ~ 4*2^40-1 1 0
...
16 16*2^40 ~ 17*2^40-1 1 0
17 17*2^40 ~ 18*2^40-1 1 284,724 <- highest 284,724 go into bucket 2
18 18*2^40 ~ 19*2^40-1 2 0
...
您现在可以再次遍历输入，并为每个整数查看最高 24 位，并使用查找 table 查看整数应该进入哪个桶。如果 运行ge 没有拆分，您可以立即将整数移动到正确的桶中。对于每个拆分 运行ge，您创建一个有序列表或优先级队列，它可以容纳进入下一个存储桶所需的尽可能多的整数；您仅存储此列表或队列中的最高值；任何较小的整数直接进入桶，如果一个整数被添加到完整列表或队列，最小值被移动到桶中。最后这个列表或队列被添加到下一个桶。
在可用内存的情况下，运行ges 的数量应尽可能多，因为这样可以最大限度地减少拆分 运行ges 中的整数数量。有了巨大的输入，您可能需要将拆分 运行ges 保存到磁盘，然后分别查看它们中的每一个，找到最高的 x 值，并将它们相应地移动到桶中。
第一个 运行 的复杂度为 N，然后遍历 运行ges R，然后在再次遍历输入时为 N，然后是拆分 运行ges 你会有类似 M.logM 的东西来排序，M 来分发，所以总共有 2*N + R + M.LogM + M。使用大量的 运行 ges 以保持 split 中的整数数量 运行ges 低可能是加快进程的最佳策略。
其实分裂运行ges的整数个数M取决于桶B的个数和运行ges R的个数，M=N×B/R，所以那例如对于一千个桶和一百万个 运行ges，输入的 0.1% 将处于拆分 运行ges 中并且必须进行排序。 （这些是平均值，具体取决于实际分布。） 使得总复杂度为 2×N + R + (N×B/R).Log(N×B/R) + N×B/R.
另一个例子：
Input: N = 13,743,895,347,200 unsigned 64-bit integers
Ranges: 232 (using the highest 32 bits of each integer)
Integers per range: 3200 (average)
Count list: 232 16-bit integers = 8 GB
Lookup table: 232 16-bit integers = 8 GB
Split range table: B 16-bit integers = 2×B bytes
有 1024 个桶，这意味着 B/R = 1/222，并且有 1023 个拆分 运行ge，每个大约有 3200 个整数，或总共约 3,276,800 个整数；然后必须将这些分类并分发到桶中。
有 1,048,576 个桶，这意味着 B/R = 1/212，并且有 1,048,575 个拆分 运行ge，每个大约有 3200 个整数，或总共约 3,355,443,200 个整数。 （超过 65,536 个桶当然需要使用 32 位整数进行查找 table。）
(如果你发现每个运行ge的计数总和不等于输入的总大小，说明计数列表已经溢出，你应该为计数切换到更大的整数类型。）
让我们 运行 通过一个小例子：运行ge 1-100 中的 50 个整数必须分布在 5 个桶中。我们选择一些 运行ges，比如 20，并迭代输入以计算每个 运行ges:
中整数的数量 2 9 14 17 21 30 33 36 44 50 51 57 69 75 80 81 87 94 99
1 9 15 16 21 32 40 42 48 55 57 66 74 76 88 96
5 6 20 24 34 50 52 58 70 78 99
7 51 69
55
3 4 2 3 3 1 3 2 2 3 5 3 0 4 2 3 1 2 1 3
然后，知道每个桶应该容纳 10 个整数，我们迭代每个 运行ge 的计数列表，并将每个 运行ge 分配给一个桶：
3 4 2 3 3 1 3 2 2 3 5 3 0 4 2 3 1 2 1 3 <- count/range
1 1 1 1 2 2 2 2 3 3 3 4 4 4 4 5 5 5 5 5 <- to bucket
2 1 1 <- to next
当 运行ge 必须在两个桶之间拆分时，我们将应该进入下一个桶的整数数量存储在单独的 table.
中然后我们可以再次迭代输入，并将非拆分 运行ges 中的所有整数移动到桶中； split 运行ges 中的整数暂时移入单独的桶中：
bucket 1: 9 14 2 9 1 15 6 5 7
temp 1/2: 17 16 20
bucket 2: 21 33 30 32 21 24 34
temp 2/3: 36 40
bucket 3: 44 50 48 42 50
temp 3/4: 51 55 52 51 55
bucket 4: 57 75 69 66 74 57 57 70 69
bucket 5: 81 94 87 80 99 88 96 76 78 99
然后我们一个一个地查看临时存储桶，找到第二个 table 中指示的 x 个最高整数，将它们移至下一个存储桶，以及剩余到前一个存储桶的内容：
temp 1/2: 17 16 20 (to next: 2) bucket 1: 16 bucket 2: 17 20
temp 2/3: 36 40 (to next: 1) bucket 2: 36 bucket 3: 40
temp 3/4: 51 55 52 51 55 (to next: 1) bucket 3: 51 51 52 55 bucket 4: 55
最终结果是：
bucket 1: 9 14 2 9 1 15 6 5 7 16
bucket 2: 21 33 30 32 21 24 34 17 20 36
bucket 3: 44 50 48 42 50 40 51 51 52 55
bucket 4: 57 75 69 66 74 57 57 70 69 55
bucket 5: 81 94 87 80 99 88 96 76 78 99
因此，在 50 个整数中，我们必须对一组 3、2 和 5 个整数进行排序。
实际上，您不需要创建 table 拆分 运行ges 中应该进入下一个存储桶的整数数量。您知道应该将多少个整数放入每个桶中，因此在初始分配之后您可以查看每个桶中已经有多少个整数，然后从拆分中添加必要数量的（最小值）整数 运行格。在上面的示例中，每个桶需要 10 个整数，即：
3 4 2 3 3 1 3 2 2 3 5 3 0 4 2 3 1 2 1 3 <- count/range
1 1 1 / 2 2 2 / 3 3 / 4 4 4 4 5 5 5 5 5 <- to bucket
bucket 1: 9 14 2 9 1 15 6 5 7 <- add 1
temp 1/2: 17 16 20 <- 3-1 = 2 go to next bucket
bucket 2: 21 33 30 32 21 24 34 <- add 3-2 = 1
temp 2/3: 36 40 <- 2-1 = 1 goes to next bucket
bucket 3: 44 50 48 42 50 <- add 5-1 = 4
temp 3/4: 51 55 52 51 55 <- 5-4 = 1 goes to next bucket
bucket 4: 57 75 69 66 74 57 57 70 69 <- add 1-1 = 0
bucket 5: 81 94 87 80 99 88 96 76 78 99 <- add 0
计算有多少输入将被拆分 运行ges 并需要排序，上面给出的 M = N × B/R，是输入的平均值，大致是平均分配。轻微的偏差，在输入的特定部分有更多的值 space 不会有太大影响，但确实有可能设计最坏情况的输入来阻止算法。
让我们再看看这个例子：
Input: N = 13,743,895,347,200 unsigned 64-bit integers
Ranges: 232 (using the highest 32 bits of each integer)
Integers per range: 3200 (average)
Buckets: 1,048,576
Integers per bucket: 13,107,200
首先，如果 运行ges 包含超过 232 个整数，则必须使用 64 位整数来计算 table，因此它的大小为 32GB，这可能会迫使您使用更少的 运行ges，具体取决于可用内存。
此外，每个 运行ge 的整数比每个桶的目标大小都自动成为一个拆分 运行ge。因此，如果整数分布在很多局部簇中，您可能会发现大部分输入都在需要排序的 运行ges 中。
如果你有足够的内存来 运行 第一步使用 232 运行ges，那么每个 运行ge 有 232 个不同的值，您可以使用计数排序（具有线性复杂性）将分割 运行ges 分布在桶上。
如果你没有足够的内存来使用 232 运行ges，而你最终会得到有问题的大拆分 运行ges，你可以在拆分 运行ges 上再次使用完整的算法。假设您使用了 228 运行ges，期望每个 运行ge 包含大约 51,200 个整数，并且您最终得到了意想不到的大拆分 运行ge 有 5,120,000,000 个整数，需要分布在 391 个桶中。如果你对这个有限的 运行ge 再次 运行 算法，你将有 228 运行ges（每个平均持有 19 个整数最多 16 个不同的值）仅用于 391 个桶，并且再次出现大拆分的风险很小 运行ges。
注意：运行必须拆分为两个或更多存储桶的数据不一定要排序。你可以例如使用 Dijkstra 的荷兰国旗算法的递归版本将 运行ge 划分为具有 x 最小值的部分和具有最大值的部分。分区的平均复杂度是线性的（当使用 运行dom pivot 时），相对于排序的 O(N.LogN) 复杂度。