std.sort.block.binaryFirst
函数
fn binaryFirst( comptime T: type, items: []T, value: T, range: Range, context: anytype, comptime lessThan: fn (@TypeOf(context), lhs: T, rhs: T) bool, ) usize
参数
std.sort.block.binaryLast
函数
fn binaryLast( comptime T: type, items: []T, value: T, range: Range, context: anytype, comptime lessThan: fn (@TypeOf(context), lhs: T, rhs: T) bool, ) usize
参数
std.sort.block.block
函数
稳定的原地排序。最佳情况 O(n),最坏与平均情况 O(n*log(n))。
使用 O(1) 内存,无需分配器。
按给定 lessThan 函数升序排序。
NOTE:算法仅适用于比较条件为小于或大于的情况。 参见 https://github.com/ziglang/zig/issues/8289。
pub fn block( comptime T: type, items: []T, context: anytype, comptime lessThanFn: fn (@TypeOf(context), lhs: T, rhs: T) bool, ) void
参数
T: type
items: []T
lessThanFn: fn (@TypeOf(context), lhs: T, rhs: T) bool
std.sort.block.block.lessThan
函数
fn lessThan(ctx: @TypeOf(context), lhs: T, rhs: T) bool
参数
ctx: @TypeOf(context)
lhs: T
rhs: T
std.sort.block.blockSwap
函数
fn blockSwap(comptime T: type, items: []T, start1: usize, start2: usize, block_size: usize) void
参数
T: type
items: []T
start1: usize
start2: usize
block_size: usize
std.sort.block.builtin
常量
std.sort.block.findFirstBackward
函数
fn findFirstBackward( comptime T: type, items: []T, value: T, range: Range, unique: usize, context: anytype, comptime lessThan: fn (@TypeOf(context), lhs: T, rhs: T) bool, ) usize
参数
T: type
items: []T
value: T
range: Range
unique: usize
lessThan: fn (@TypeOf(context), lhs: T, rhs: T) bool
std.sort.block.findFirstForward
函数
fn findFirstForward( comptime T: type, items: []T, value: T, range: Range, unique: usize, context: anytype, comptime lessThan: fn (@TypeOf(context), lhs: T, rhs: T) bool, ) usize
参数
T: type
items: []T
value: T
range: Range
unique: usize
lessThan: fn (@TypeOf(context), lhs: T, rhs: T) bool
std.sort.block.findLastBackward
函数
fn findLastBackward( comptime T: type, items: []T, value: T, range: Range, unique: usize, context: anytype, comptime lessThan: fn (@TypeOf(context), lhs: T, rhs: T) bool, ) usize
参数
T: type
items: []T
value: T
range: Range
unique: usize
lessThan: fn (@TypeOf(context), lhs: T, rhs: T) bool
std.sort.block.findLastForward
函数
fn findLastForward( comptime T: type, items: []T, value: T, range: Range, unique: usize, context: anytype, comptime lessThan: fn (@TypeOf(context), lhs: T, rhs: T) bool, ) usize
参数
T: type
items: []T
value: T
range: Range
unique: usize
lessThan: fn (@TypeOf(context), lhs: T, rhs: T) bool
std.sort.block.Iterator
容器
字段
size: usize
power_of_two: usize
numerator: usize
decimal: usize
denominator: usize
decimal_step: usize
numerator_step: usize
std.sort.block.Iterator.begin
函数
fn begin(self: *Iterator) void
参数
self: *Iterator
std.sort.block.Iterator.finished
函数
fn finished(self: *Iterator) bool
参数
self: *Iterator
std.sort.block.Iterator.init
函数
fn init(size2: usize, min_level: usize) Iterator
参数
size2: usize
min_level: usize
std.sort.block.Iterator.length
函数
fn length(self: *Iterator) usize
参数
self: *Iterator
std.sort.block.Iterator.nextLevel
函数
fn nextLevel(self: *Iterator) bool
参数
self: *Iterator
std.sort.block.Iterator.nextRange
函数
fn nextRange(self: *Iterator) Range
参数
self: *Iterator
std.sort.block.math
别名
别名目标 std.math
std.sort.block.mem
别名
别名目标 std.mem
std.sort.block.mergeExternal
函数
fn mergeExternal( comptime T: type, items: []T, A: Range, B: Range, cache: []T, context: anytype, comptime lessThan: fn (@TypeOf(context), lhs: T, rhs: T) bool, ) void
参数
std.sort.block.mergeInPlace
函数
fn mergeInPlace( comptime T: type, items: []T, A_arg: Range, B_arg: Range, context: anytype, comptime lessThan: fn (@TypeOf(context), lhs: T, rhs: T) bool, ) void
参数
std.sort.block.mergeInternal
函数
fn mergeInternal( comptime T: type, items: []T, A: Range, B: Range, buffer: Range, context: anytype, comptime lessThan: fn (@TypeOf(context), lhs: T, rhs: T) bool, ) void
参数
std.sort.block.mergeInto
函数
fn mergeInto( comptime T: type, from: []T, A: Range, B: Range, into: []T, context: anytype, comptime lessThan: fn (@TypeOf(context), lhs: T, rhs: T) bool, ) void
参数
std.sort.block.Pull
容器
字段
std.sort.block.Range
容器
字段
start: usize
end: usize
std.sort.block.Range.init
函数
fn init(start: usize, end: usize) Range
参数
start: usize
end: usize
std.sort.block.Range.length
函数
fn length(self: Range) usize
参数
self: Range
std.sort.block.sort
别名
别名目标 std.sort
std.sort.block.std
别名
别名目标 std
std.sort.block.swap
函数
fn swap( comptime T: type, items: []T, order: *[8]u8, x: usize, y: usize, context: anytype, comptime lessThan: fn (@TypeOf(context), lhs: T, rhs: T) bool, ) void
参数
T: type
items: []T
order: *[8]u8
x: usize
y: usize
lessThan: fn (@TypeOf(context), lhs: T, rhs: T) bool
源码
std/sort/block.zig
const builtin = @import("builtin");
const std = @import("../std.zig");
const sort = std.sort;
const math = std.math;
const mem = std.mem;
const Range = struct {
start: usize,
end: usize,
fn init(start: usize, end: usize) Range {
return Range{
.start = start,
.end = end,
};
}
fn length(self: Range) usize {
return self.end - self.start;
}
};
const Iterator = struct {
size: usize,
power_of_two: usize,
numerator: usize,
decimal: usize,
denominator: usize,
decimal_step: usize,
numerator_step: usize,
fn init(size2: usize, min_level: usize) Iterator {
const power_of_two = math.floorPowerOfTwo(usize, size2);
const denominator = power_of_two / min_level;
return Iterator{
.numerator = 0,
.decimal = 0,
.size = size2,
.power_of_two = power_of_two,
.denominator = denominator,
.decimal_step = size2 / denominator,
.numerator_step = size2 % denominator,
};
}
fn begin(self: *Iterator) void {
self.numerator = 0;
self.decimal = 0;
}
fn nextRange(self: *Iterator) Range {
const start = self.decimal;
self.decimal += self.decimal_step;
self.numerator += self.numerator_step;
if (self.numerator >= self.denominator) {
self.numerator -= self.denominator;
self.decimal += 1;
}
return Range{
.start = start,
.end = self.decimal,
};
}
fn finished(self: *Iterator) bool {
return self.decimal >= self.size;
}
fn nextLevel(self: *Iterator) bool {
self.decimal_step += self.decimal_step;
self.numerator_step += self.numerator_step;
if (self.numerator_step >= self.denominator) {
self.numerator_step -= self.denominator;
self.decimal_step += 1;
}
return (self.decimal_step < self.size);
}
fn length(self: *Iterator) usize {
return self.decimal_step;
}
};
const Pull = struct {
from: usize,
to: usize,
count: usize,
range: Range,
};
/// 稳定的原地排序。最佳情况 O(n),最坏与平均情况 O(n*log(n))。
/// 使用 O(1) 内存,无需分配器。
/// 按给定 `lessThan` 函数升序排序。
///
/// NOTE:算法仅适用于比较条件为小于或大于的情况。
/// 参见 https://github.com/ziglang/zig/issues/8289。
pub fn block(
comptime T: type,
items: []T,
context: anytype,
comptime lessThanFn: fn (@TypeOf(context), lhs: T, rhs: T) bool,
) void {
const lessThan = if (builtin.mode == .debug) struct {
fn lessThan(ctx: @TypeOf(context), lhs: T, rhs: T) bool {
const lt = lessThanFn(ctx, lhs, rhs);
const gt = lessThanFn(ctx, rhs, lhs);
std.debug.assert(!(lt and gt));
return lt;
}
}.lessThan else lessThanFn;
// 实现移植自 https://github.com/BonzaiThePenguin/WikiSort/blob/master/WikiSort.c
var cache: [512]T = undefined;
if (items.len < 4) {
if (items.len == 3) {
// 硬编码的插入排序
if (lessThan(context, items[1], items[0])) mem.swap(T, &items[0], &items[1]);
if (lessThan(context, items[2], items[1])) {
mem.swap(T, &items[1], &items[2]);
if (lessThan(context, items[1], items[0])) mem.swap(T, &items[0], &items[1]);
}
} else if (items.len == 2) {
if (lessThan(context, items[1], items[0])) mem.swap(T, &items[0], &items[1]);
}
return;
}
// 使用不稳定排序网络,每次对一组 4 至 8 个元素排序,
// 同时跟踪元素的原始顺序,强制保持稳定。
// http://pages.ripco.net/~jgamble/nw.html
var iterator = Iterator.init(items.len, 4);
while (!iterator.finished()) {
var order = [_]u8{ 0, 1, 2, 3, 4, 5, 6, 7 };
const range = iterator.nextRange();
const sliced_items = items[range.start..];
switch (range.length()) {
8 => {
swap(T, sliced_items, &order, 0, 1, context, lessThan);
swap(T, sliced_items, &order, 2, 3, context, lessThan);
swap(T, sliced_items, &order, 4, 5, context, lessThan);
swap(T, sliced_items, &order, 6, 7, context, lessThan);
swap(T, sliced_items, &order, 0, 2, context, lessThan);
swap(T, sliced_items, &order, 1, 3, context, lessThan);
swap(T, sliced_items, &order, 4, 6, context, lessThan);
swap(T, sliced_items, &order, 5, 7, context, lessThan);
swap(T, sliced_items, &order, 1, 2, context, lessThan);
swap(T, sliced_items, &order, 5, 6, context, lessThan);
swap(T, sliced_items, &order, 0, 4, context, lessThan);
swap(T, sliced_items, &order, 3, 7, context, lessThan);
swap(T, sliced_items, &order, 1, 5, context, lessThan);
swap(T, sliced_items, &order, 2, 6, context, lessThan);
swap(T, sliced_items, &order, 1, 4, context, lessThan);
swap(T, sliced_items, &order, 3, 6, context, lessThan);
swap(T, sliced_items, &order, 2, 4, context, lessThan);
swap(T, sliced_items, &order, 3, 5, context, lessThan);
swap(T, sliced_items, &order, 3, 4, context, lessThan);
},
7 => {
swap(T, sliced_items, &order, 1, 2, context, lessThan);
swap(T, sliced_items, &order, 3, 4, context, lessThan);
swap(T, sliced_items, &order, 5, 6, context, lessThan);
swap(T, sliced_items, &order, 0, 2, context, lessThan);
swap(T, sliced_items, &order, 3, 5, context, lessThan);
swap(T, sliced_items, &order, 4, 6, context, lessThan);
swap(T, sliced_items, &order, 0, 1, context, lessThan);
swap(T, sliced_items, &order, 4, 5, context, lessThan);
swap(T, sliced_items, &order, 2, 6, context, lessThan);
swap(T, sliced_items, &order, 0, 4, context, lessThan);
swap(T, sliced_items, &order, 1, 5, context, lessThan);
swap(T, sliced_items, &order, 0, 3, context, lessThan);
swap(T, sliced_items, &order, 2, 5, context, lessThan);
swap(T, sliced_items, &order, 1, 3, context, lessThan);
swap(T, sliced_items, &order, 2, 4, context, lessThan);
swap(T, sliced_items, &order, 2, 3, context, lessThan);
},
6 => {
swap(T, sliced_items, &order, 1, 2, context, lessThan);
swap(T, sliced_items, &order, 4, 5, context, lessThan);
swap(T, sliced_items, &order, 0, 2, context, lessThan);
swap(T, sliced_items, &order, 3, 5, context, lessThan);
swap(T, sliced_items, &order, 0, 1, context, lessThan);
swap(T, sliced_items, &order, 3, 4, context, lessThan);
swap(T, sliced_items, &order, 2, 5, context, lessThan);
swap(T, sliced_items, &order, 0, 3, context, lessThan);
swap(T, sliced_items, &order, 1, 4, context, lessThan);
swap(T, sliced_items, &order, 2, 4, context, lessThan);
swap(T, sliced_items, &order, 1, 3, context, lessThan);
swap(T, sliced_items, &order, 2, 3, context, lessThan);
},
5 => {
swap(T, sliced_items, &order, 0, 1, context, lessThan);
swap(T, sliced_items, &order, 3, 4, context, lessThan);
swap(T, sliced_items, &order, 2, 4, context, lessThan);
swap(T, sliced_items, &order, 2, 3, context, lessThan);
swap(T, sliced_items, &order, 1, 4, context, lessThan);
swap(T, sliced_items, &order, 0, 3, context, lessThan);
swap(T, sliced_items, &order, 0, 2, context, lessThan);
swap(T, sliced_items, &order, 1, 3, context, lessThan);
swap(T, sliced_items, &order, 1, 2, context, lessThan);
},
4 => {
swap(T, sliced_items, &order, 0, 1, context, lessThan);
swap(T, sliced_items, &order, 2, 3, context, lessThan);
swap(T, sliced_items, &order, 0, 2, context, lessThan);
swap(T, sliced_items, &order, 1, 3, context, lessThan);
swap(T, sliced_items, &order, 1, 2, context, lessThan);
},
else => {},
}
}
if (items.len < 8) return;
// 随后对更高层执行归并排序,可能为 8–15、16–31、32–63、64–127 等。
while (true) {
// 若每个 A 块和 B 块均能放入缓存,则采用
// 专门用于借助缓存合并的分支。
// (使用 < 而非 <=,因为块大小可能比
// iterator.length() 大一。)
if (iterator.length() < cache.len) {
// 若缓存能容纳四个子数组,则先将两对子数组
// 分别合并到缓存,再将缓存中的两个已合并子数组
// 合并回原数组会更快。
if ((iterator.length() + 1) * 4 <= cache.len and iterator.length() * 4 <= items.len) {
iterator.begin();
while (!iterator.finished()) {
// 将 A1 和 B1 合并到缓存
var A1 = iterator.nextRange();
var B1 = iterator.nextRange();
var A2 = iterator.nextRange();
var B2 = iterator.nextRange();
if (lessThan(context, items[B1.end - 1], items[A1.start])) {
// 两个范围顺序相反,因此按相反顺序将其复制到缓存
const a1_items = items[A1.start..A1.end];
@memcpy(cache[B1.length()..][0..a1_items.len], a1_items);
const b1_items = items[B1.start..B1.end];
@memcpy(cache[0..b1_items.len], b1_items);
} else if (lessThan(context, items[B1.start], items[A1.end - 1])) {
// 两个范围原先未按序排列,因此将其合并到缓存
mergeInto(T, items, A1, B1, cache[0..], context, lessThan);
} else {
// 若 A1、B1、A2、B2 均已按序排列,则无需继续处理
if (!lessThan(context, items[B2.start], items[A2.end - 1]) and !lessThan(context, items[A2.start], items[B1.end - 1])) continue;
// 按相同顺序将 A1 和 B1 复制到缓存
const a1_items = items[A1.start..A1.end];
@memcpy(cache[0..a1_items.len], a1_items);
const b1_items = items[B1.start..B1.end];
@memcpy(cache[A1.length()..][0..b1_items.len], b1_items);
}
A1 = Range.init(A1.start, B1.end);
// 将 A2 和 B2 合并到缓存
if (lessThan(context, items[B2.end - 1], items[A2.start])) {
// 两个范围顺序相反,因此按相反顺序将其复制到缓存
const a2_items = items[A2.start..A2.end];
@memcpy(cache[A1.length() + B2.length() ..][0..a2_items.len], a2_items);
const b2_items = items[B2.start..B2.end];
@memcpy(cache[A1.length()..][0..b2_items.len], b2_items);
} else if (lessThan(context, items[B2.start], items[A2.end - 1])) {
// 两个范围原先未按序排列,因此将其合并到缓存
mergeInto(T, items, A2, B2, cache[A1.length()..], context, lessThan);
} else {
// 按相同顺序将 A2 和 B2 复制到缓存中
const a2_items = items[A2.start..A2.end];
@memcpy(cache[A1.length()..][0..a2_items.len], a2_items);
const b2_items = items[B2.start..B2.end];
@memcpy(cache[A1.length() + A2.length() ..][0..b2_items.len], b2_items);
}
A2 = Range.init(A2.start, B2.end);
// 将缓存中的 A1 和 A2 合并到 items
const A3 = Range.init(0, A1.length());
const B3 = Range.init(A1.length(), A1.length() + A2.length());
if (lessThan(context, cache[B3.end - 1], cache[A3.start])) {
// 两个范围的顺序相反,因此反向复制到 items 中
const a3_items = cache[A3.start..A3.end];
@memcpy(items[A1.start + A2.length() ..][0..a3_items.len], a3_items);
const b3_items = cache[B3.start..B3.end];
@memcpy(items[A1.start..][0..b3_items.len], b3_items);
} else if (lessThan(context, cache[B3.start], cache[A3.end - 1])) {
// 这两个范围尚未按序排列,因此将其合并回 items 中
mergeInto(T, cache[0..], A3, B3, items[A1.start..], context, lessThan);
} else {
// 按相同顺序将 A3 和 B3 复制到 items 中。
const a3_items = cache[A3.start..A3.end];
@memcpy(items[A1.start..][0..a3_items.len], a3_items);
const b3_items = cache[B3.start..B3.end];
@memcpy(items[A1.start + A1.length() ..][0..b3_items.len], b3_items);
}
}
// 同时合并了两层,因此当前层已经完成
// (此外层合并循环底部会再次调用 iterator.nextLevel())
_ = iterator.nextLevel();
} else {
iterator.begin();
while (!iterator.finished()) {
const A = iterator.nextRange();
const B = iterator.nextRange();
if (lessThan(context, items[B.end - 1], items[A.start])) {
// 这两个范围顺序相反,因此简单旋转即可修复
mem.rotate(T, items[A.start..B.end], A.length());
} else if (lessThan(context, items[B.start], items[A.end - 1])) {
// 这两个范围尚未按序排列,因此需要合并!
const a_items = items[A.start..A.end];
@memcpy(cache[0..a_items.len], a_items);
mergeExternal(T, items, A, B, cache[0..], context, lessThan);
}
}
}
} else {
// 原地归并逻辑从此处开始!
// 1. 提取两个内部缓冲区,每个均包含 √A 个不同值。
// 1a. 若找不到足够多的不同值,则调整 block_size 和 buffer_size。
// 2. 遍历归并排序当前层的 A 和 B 子数组。
// 3. 将 A 和 B 分为大小为 'block_size' 的块。
// 4. 使用第一个内部缓冲区的值为各 A 块“打标签”。
// 5. 将 A 块在 B 块间滚动,在适当位置放下或旋转。
// 6. 利用缓存或第二个内部缓冲区,将各 A 块与其后的 B 值归并。
// 7. 若存在第二个内部缓冲区,则对其排序。
// 8. 将两个内部缓冲区的内容重新分配回元素序列。
var block_size: usize = math.sqrt(iterator.length());
var buffer_size = iterator.length() / block_size + 1;
// 作为优化,每一层合并仅需提取一次内部缓冲区;
// 此后可反复复用相同缓冲区,完成此层后再重新分布其中内容。
var A: Range = undefined;
var B: Range = undefined;
var index: usize = 0;
var last: usize = 0;
var count: usize = 0;
var find: usize = 0;
var start: usize = 0;
var pull_index: usize = 0;
var pull = [_]Pull{
Pull{
.from = 0,
.to = 0,
.count = 0,
.range = Range.init(0, 0),
},
Pull{
.from = 0,
.to = 0,
.count = 0,
.range = Range.init(0, 0),
},
};
var buffer1 = Range.init(0, 0);
var buffer2 = Range.init(0, 0);
// 查找两个各自大小为 'buffer_size' 的内部缓冲区
find = buffer_size + buffer_size;
var find_separately = false;
if (block_size <= cache.len) {
// 若每个 A 块都能装入缓存,则无需第二个内部缓冲区,因此只需要找到 buffer_size 个唯一值
//
find = buffer_size;
} else if (find > iterator.length()) {
// 两个缓冲区无法放入同一个 A 或 B 子数组,因此分别查找两个缓冲区
find = buffer_size;
find_separately = true;
}
// 需要找到包含 2√A 个不同值的单个连续空间(随后将其拆成两个各有 √A 个值的缓冲区),
// 或者找到一个包含少于 2√A 个不同值的缓冲区,以及第二个包含 √A 个不同值的缓冲区,
// 或者,如果找不到这么多不同值,则需要能获取到的最大缓冲区。
// 若找不到至少包含 √A 个不同值的单个缓冲区,
// 则必须使用其他合并算法(MergeInPlace)替换所有 Merge 步骤。
iterator.begin();
while (!iterator.finished()) {
A = iterator.nextRange();
B = iterator.nextRange();
// 只需记录值将从何处抽取、移至何处以及值的数量,即可创建两个内部缓冲区
//
// 检查 A 中能否找到填充内部缓冲区所需数量的不同值。
// 这些值将被抽取到 A 的开头。
last = A.start;
count = 1;
while (count < find) : ({
last = index;
count += 1;
}) {
index = findLastForward(T, items, items[last], Range.init(last + 1, A.end), find - count, context, lessThan);
if (index == A.end) break;
}
index = last;
if (count >= buffer_size) {
// 跟踪元素中需要“抽取”这些值的范围,以创建内部缓冲区。
pull[pull_index] = Pull{
.range = Range.init(A.start, B.end),
.count = count,
.from = index,
.to = A.start,
};
pull_index = 1;
if (count == buffer_size + buffer_size) {
// 已找到一个包含 2√A 个唯一值的连续区段,因此可用该区段容纳所需的两个内部缓冲区
//
buffer1 = Range.init(A.start, A.start + buffer_size);
buffer2 = Range.init(A.start + buffer_size, A.start + count);
break;
} else if (find == buffer_size + buffer_size) {
// 找到的缓冲区至少包含 √A 个不同值,但未包含全部 2√A 个不同值,
// 因此仍需找到第二个独立缓冲区,至少包含 √A 个不同值。
buffer1 = Range.init(A.start, A.start + count);
find = buffer_size;
} else if (block_size <= cache.len) {
// 已找到所需的第一个且唯一的内部缓冲区,因此完成!
buffer1 = Range.init(A.start, A.start + count);
break;
} else if (find_separately) {
// 已找到一个缓冲区,现在查找另一个
buffer1 = Range.init(A.start, A.start + count);
find_separately = false;
} else {
// 已在包含 √A 个唯一值的 'A' 子数组中找到第二个缓冲区,因此完成!
buffer2 = Range.init(A.start, A.start + count);
break;
}
} else if (pull_index == 0 and count > buffer1.length()) {
// 记录已找到的最大缓冲区
buffer1 = Range.init(A.start, A.start + count);
pull[pull_index] = Pull{
.range = Range.init(A.start, B.end),
.count = count,
.from = index,
.to = A.start,
};
}
// 检查 B 是否包含足够多的不同值,以填满内部缓冲区
// 这些值将被取出并移到 B 的末尾
last = B.end - 1;
count = 1;
while (count < find) : ({
last = index - 1;
count += 1;
}) {
index = findFirstBackward(T, items, items[last], Range.init(B.start, last), find - count, context, lessThan);
if (index == B.start) break;
}
index = last;
if (count >= buffer_size) {
// 跟踪元素中需要“抽取”这些值的范围,以创建内部缓冲区。
pull[pull_index] = Pull{
.range = Range.init(A.start, B.end),
.count = count,
.from = index,
.to = B.end,
};
pull_index = 1;
if (count == buffer_size + buffer_size) {
// 已找到一个包含 2√A 个唯一值的连续区段,因此可用该区段容纳所需的两个内部缓冲区
//
buffer1 = Range.init(B.end - count, B.end - buffer_size);
buffer2 = Range.init(B.end - buffer_size, B.end);
break;
} else if (find == buffer_size + buffer_size) {
// 找到的缓冲区至少包含 √A 个不同值,但未包含全部 2√A 个不同值,
// 因此仍需找到第二个独立缓冲区,至少包含 √A 个不同值。
buffer1 = Range.init(B.end - count, B.end);
find = buffer_size;
} else if (block_size <= cache.len) {
// 已找到所需的第一个且唯一的内部缓冲区,因此完成!
buffer1 = Range.init(B.end - count, B.end);
break;
} else if (find_separately) {
// 已找到一个缓冲区,现在查找另一个
buffer1 = Range.init(B.end - count, B.end);
find_separately = false;
} else {
// buffer2 将从一个“B”子数组中取出,因此如果第一个缓冲区来自对应的“A”子数组,
// 就必须调整该 A 子数组的终点,使其在重新分配值时知道应在 buffer2 之前停止。
if (pull[0].range.start == A.start) pull[0].range.end -= pull[1].count;
// 已在某个 'B' 子数组中找到包含 √A 个不同值的第二个缓冲区,因此完成!
buffer2 = Range.init(B.end - count, B.end);
break;
}
} else if (pull_index == 0 and count > buffer1.length()) {
// 记录已找到的最大缓冲区
buffer1 = Range.init(B.end - count, B.end);
pull[pull_index] = Pull{
.range = Range.init(A.start, B.end),
.count = count,
.from = index,
.to = B.end,
};
}
}
// 提取这两个范围,以便将其用作内部缓冲区。
pull_index = 0;
while (pull_index < 2) : (pull_index += 1) {
const length = pull[pull_index].count;
if (pull[pull_index].to < pull[pull_index].from) {
// 将值抽取到左侧,即 A 子数组的起始处
index = pull[pull_index].from;
count = 1;
while (count < length) : (count += 1) {
index = findFirstBackward(T, items, items[index - 1], Range.init(pull[pull_index].to, pull[pull_index].from - (count - 1)), length - count, context, lessThan);
const range = Range.init(index + 1, pull[pull_index].from + 1);
mem.rotate(T, items[range.start..range.end], range.length() - count);
pull[pull_index].from = index + count;
}
} else if (pull[pull_index].to > pull[pull_index].from) {
// 将值抽取到右侧,即 B 子数组的末尾
index = pull[pull_index].from + 1;
count = 1;
while (count < length) : (count += 1) {
index = findLastForward(T, items, items[index], Range.init(index, pull[pull_index].to), length - count, context, lessThan);
const range = Range.init(pull[pull_index].from, index - 1);
mem.rotate(T, items[range.start..range.end], count);
pull[pull_index].from = index - 1 - count;
}
}
}
// 根据成功提取的值调整 block_size 和 buffer_size。
buffer_size = buffer1.length();
block_size = iterator.length() / buffer_size + 1;
// 第一个缓冲区必须足够大,能够标记每个等长的 A 块,
// 因此此处原本用于测试上方调整 block_size 的计算。
// assert((iterator.length() + 1)/block_size <= buffer_size);
// 两个内部缓冲区已创建,现在合并归并排序当前层的每个 A+B 组合。
iterator.begin();
while (!iterator.finished()) {
A = iterator.nextRange();
B = iterator.nextRange();
// 移除 A 或 B 中被内部缓冲区使用的部分
start = A.start;
if (start == pull[0].range.start) {
if (pull[0].from > pull[0].to) {
A.start += pull[0].count;
// 如果内部缓冲区占满整个 A 或 B 子数组,就没有内容需要归并。
// 这仅发生在很小的子数组,例如 √4 = 2,2 *(2 个内部缓冲区)= 4,
// 而且仅在 cache.len 很小或为 0 时发生,否则会使用 MergeExternal。
if (A.length() == 0) continue;
} else if (pull[0].from < pull[0].to) {
B.end -= pull[0].count;
if (B.length() == 0) continue;
}
}
if (start == pull[1].range.start) {
if (pull[1].from > pull[1].to) {
A.start += pull[1].count;
if (A.length() == 0) continue;
} else if (pull[1].from < pull[1].to) {
B.end -= pull[1].count;
if (B.length() == 0) continue;
}
}
if (lessThan(context, items[B.end - 1], items[A.start])) {
// 这两个范围顺序相反,因此简单旋转即可修复
mem.rotate(T, items[A.start..B.end], A.length());
} else if (lessThan(context, items[A.end], items[A.end - 1])) {
// 这两个范围尚未按序排列,因此需要合并!
var findA: usize = undefined;
// 将 A 的剩余部分拆成块。firstA 为大小不均匀的首个 A 块
var blockA = Range.init(A.start, A.end);
var firstA = Range.init(A.start, A.start + blockA.length() % block_size);
// 将每个 A 块的首个值与 buffer1 中的值交换
var indexA = buffer1.start;
index = firstA.end;
while (index < blockA.end) : ({
indexA += 1;
index += block_size;
}) {
mem.swap(T, &items[indexA], &items[index]);
}
// 开始将 A 块滚动穿过 B 块!
// 每当留下一个 A 块时,都需要将前一个 A 块与其后的所有 B 块归并,因此也要跟踪此信息。
var lastA = firstA;
var lastB = Range.init(0, 0);
var blockB = Range.init(B.start, B.start + @min(block_size, B.length()));
blockA.start += firstA.length();
indexA = buffer1.start;
// 若第一个大小不均的 A 块可放入缓存,则将其复制到缓存,留待归并。
// 否则,若第二个缓冲区可用,则通过块交换将内容移入该缓冲区。
if (lastA.length() <= cache.len) {
const last_a_items = items[lastA.start..lastA.end];
@memcpy(cache[0..last_a_items.len], last_a_items);
} else if (buffer2.length() > 0) {
blockSwap(T, items, lastA.start, buffer2.start, lastA.length());
}
if (blockA.length() > 0) {
while (true) {
// 若存在前一个 B 块,且最小 A 块的首值 <= 前一个 B 块的末值,
// 则将该最小 A 块放到后面。若已无 B 块,则继续放下剩余 A 块。
if ((lastB.length() > 0 and !lessThan(context, items[lastB.end - 1], items[indexA])) or blockB.length() == 0) {
// 确定前一个 B 块的拆分位置,并在拆分处旋转它。
const B_split = binaryFirst(T, items, items[indexA], lastB, context, lessThan);
const B_remaining = lastB.end - B_split;
// 将最小 A 块交换到滚动 A 块序列的开头
var minA = blockA.start;
findA = minA + block_size;
while (findA < blockA.end) : (findA += block_size) {
if (lessThan(context, items[findA], items[minA])) {
minA = findA;
}
}
blockSwap(T, items, blockA.start, minA, block_size);
// 将前一个 A 块的首个元素与存储在 buffer1 中的原始值交换回来。
mem.swap(T, &items[blockA.start], &items[indexA]);
indexA += 1;
// 将前一个 A 块与其后 B 值局部合并。
// 若 lastA 能放入外部缓存,则通过 MergeExternal 使用外部缓存;
// 否则,若第二个内部缓冲区存在,则通过 MergeInternal 使用它;
// 若都不满足,则使用严格原地合并算法 MergeInPlace。
if (lastA.length() <= cache.len) {
mergeExternal(T, items, lastA, Range.init(lastA.end, B_split), cache[0..], context, lessThan);
} else if (buffer2.length() > 0) {
mergeInternal(T, items, lastA, Range.init(lastA.end, B_split), buffer2, context, lessThan);
} else {
mergeInPlace(T, items, lastA, Range.init(lastA.end, B_split), context, lessThan);
}
if (buffer2.length() > 0 or block_size <= cache.len) {
// 将前一个 A 块复制到缓存或 buffer2,因为合并时无论如何都需要它位于那里
if (block_size <= cache.len) {
@memcpy(cache[0..block_size], items[blockA.start..][0..block_size]);
} else {
blockSwap(T, items, blockA.start, buffer2.start, block_size);
}
// 这等同于旋转,但更快。
// 通常由 A 块占用的区域,要么是 buffer2 的内容,要么是已经复制、因而不再需要的数据。
// 两种情况下都无需保留这些元素的顺序,因此不必旋转,直接将 B 块交换到其正确位置即可。
blockSwap(T, items, B_split, blockA.start + block_size - B_remaining, B_remaining);
} else {
// 由于 buffer2 不存在,无法使用 'buffer2' 技巧加速旋转操作,因此执行普通旋转
mem.rotate(T, items[B_split .. blockA.start + block_size], blockA.start - B_split);
}
// 更新剩余 A 块的范围,以及 B 块拆分后剩余部分的范围
lastA = Range.init(blockA.start - B_remaining, blockA.start - B_remaining + block_size);
lastB = Range.init(lastA.end, lastA.end + B_remaining);
// 如果没有剩余的 A 块,则此步骤已完成!
blockA.start += block_size;
if (blockA.length() == 0) break;
} else if (blockB.length() < block_size) {
// 通过旋转,将大小不齐的最后一个 B 块移到剩余 A 块之前。
// 此处禁用缓存,因为其中可能包含前一个 A 块的内容。
mem.rotate(T, items[blockA.start..blockB.end], blockB.start - blockA.start);
lastB = Range.init(blockA.start, blockA.start + blockB.length());
blockA.start += blockB.length();
blockA.end += blockB.length();
blockB.end = blockB.start;
} else {
// 通过与下一个 B 块交换,将最左边的 A 块滚动到末尾
blockSwap(T, items, blockA.start, blockB.start, block_size);
lastB = Range.init(blockA.start, blockA.start + block_size);
blockA.start += block_size;
blockA.end += block_size;
blockB.start += block_size;
if (blockB.end > B.end - block_size) {
blockB.end = B.end;
} else {
blockB.end += block_size;
}
}
}
}
// 将最后一个 A 块与剩余 B 值合并
if (lastA.length() <= cache.len) {
mergeExternal(T, items, lastA, Range.init(lastA.end, B.end), cache[0..], context, lessThan);
} else if (buffer2.length() > 0) {
mergeInternal(T, items, lastA, Range.init(lastA.end, B.end), buffer2, context, lessThan);
} else {
mergeInPlace(T, items, lastA, Range.init(lastA.end, B.end), context, lessThan);
}
}
}
// 完成本次归并步骤后,应剩下一个
// 或两个内部缓冲区,其中第二个缓冲区完全无序。
// 先对第二个缓冲区进行插入排序,再使用与创建缓冲区相反的过程,
// 将缓冲区重新分配回条目中。
// 虽然这里可以使用快速排序等不稳定排序,但在基准测试中,
// 即使处理数千万个元素,也始终略慢于简单的插入排序。
// 这可能是因为数据已部分有序时,
// 插入排序相当快,而此处正是这种情况。
sort.insertion(T, items[buffer2.start..buffer2.end], context, lessThan);
pull_index = 0;
while (pull_index < 2) : (pull_index += 1) {
var unique = pull[pull_index].count * 2;
if (pull[pull_index].from > pull[pull_index].to) {
// 值已抽取到左侧,因此将其重新分配回右侧
var buffer = Range.init(pull[pull_index].range.start, pull[pull_index].range.start + pull[pull_index].count);
while (buffer.length() > 0) {
index = findFirstForward(T, items, items[buffer.start], Range.init(buffer.end, pull[pull_index].range.end), unique, context, lessThan);
const amount = index - buffer.end;
mem.rotate(T, items[buffer.start..index], buffer.length());
buffer.start += (amount + 1);
buffer.end += amount;
unique -= 2;
}
} else if (pull[pull_index].from < pull[pull_index].to) {
// 值被提取到了右侧,因此将其重新分布回左侧。
var buffer = Range.init(pull[pull_index].range.end - pull[pull_index].count, pull[pull_index].range.end);
while (buffer.length() > 0) {
index = findLastBackward(T, items, items[buffer.end - 1], Range.init(pull[pull_index].range.start, buffer.start), unique, context, lessThan);
const amount = buffer.start - index;
mem.rotate(T, items[index..buffer.end], amount);
buffer.start -= amount;
buffer.end -= (amount + 1);
unique -= 2;
}
}
}
}
// 将下一层待合并的各 A、B 子数组大小加倍
if (!iterator.nextLevel()) break;
}
}
// 不使用缓冲区的合并操作
fn mergeInPlace(
comptime T: type,
items: []T,
A_arg: Range,
B_arg: Range,
context: anytype,
comptime lessThan: fn (@TypeOf(context), lhs: T, rhs: T) bool,
) void {
if (A_arg.length() == 0 or B_arg.length() == 0) return;
// 此处仅反复在 B 中进行二分查找,并将 A 旋转到位。
// 论文建议在这里使用“基于旋转的 Hwang and Lin 算法”,
// 但我选择保留此实现,因为其在这里的性能更好。
//
// Hwang and Lin 针对大小差异很大的子数组归并而设计,
// 而 WikiSort 几乎总是使用大小近似相同的子数组。
//
// 通常此方法极其低效,但只有在所有子数组的
// A 块和 B 块均未包含 2√A 个不同值时,才会调用此函数,
// 这为实际所需的二分查找和
// 旋转次数施加了严格上限。
//
// 根据我的分析,忽略常数因子后,最坏情况是对 √A 个元素
// 执行 √A 次旋转,因此最终复杂度为 O(n)。
//
// 再次强调,这*不是*通用解决方案,仅在此场景下表现良好!
// 这类似于某些地方仍使用 O(n^2) 插入排序。
var A = A_arg;
var B = B_arg;
while (true) {
// 查找 A 的首项在 B 中需要插入的第一个位置
const mid = binaryFirst(T, items, items[A.start], B, context, lessThan);
// 将 A 旋转到位
const amount = mid - A.end;
mem.rotate(T, items[A.start..mid], A.length());
if (B.end == mid) break;
// 计算新的 A 与 B 范围
B.start = mid;
A = Range.init(A.start + amount, B.start);
A.start = binaryLast(T, items, items[A.start], A, context, lessThan);
if (A.length() == 0) break;
}
}
// 使用内部缓冲区的合并操作
fn mergeInternal(
comptime T: type,
items: []T,
A: Range,
B: Range,
buffer: Range,
context: anytype,
comptime lessThan: fn (@TypeOf(context), lhs: T, rhs: T) bool,
) void {
// 每当找到要添加到最终数组的值,就将其与该位置已有的值交换。
// 算法结束时,'buffer' 将包含原有内容,但顺序不同。
var A_count: usize = 0;
var B_count: usize = 0;
var insert: usize = 0;
if (B.length() > 0 and A.length() > 0) {
while (true) {
if (!lessThan(context, items[B.start + B_count], items[buffer.start + A_count])) {
mem.swap(T, &items[A.start + insert], &items[buffer.start + A_count]);
A_count += 1;
insert += 1;
if (A_count >= A.length()) break;
} else {
mem.swap(T, &items[A.start + insert], &items[B.start + B_count]);
B_count += 1;
insert += 1;
if (B_count >= B.length()) break;
}
}
}
// 将 A 的剩余部分交换到最终数组
blockSwap(T, items, buffer.start + A_count, A.start + insert, A.length() - A_count);
}
fn blockSwap(comptime T: type, items: []T, start1: usize, start2: usize, block_size: usize) void {
var index: usize = 0;
while (index < block_size) : (index += 1) {
mem.swap(T, &items[start1 + index], &items[start2 + index]);
}
}
// 将线性查找与二分查找结合,以便在大致知道不同值的数量
// 以及下一个值可能所在位置时,减少比较次数。
fn findFirstForward(
comptime T: type,
items: []T,
value: T,
range: Range,
unique: usize,
context: anytype,
comptime lessThan: fn (@TypeOf(context), lhs: T, rhs: T) bool,
) usize {
if (range.length() == 0) return range.start;
const skip = @max(range.length() / unique, @as(usize, 1));
var index = range.start + skip;
while (lessThan(context, items[index - 1], value)) : (index += skip) {
if (index >= range.end - skip) {
return binaryFirst(T, items, value, Range.init(index, range.end), context, lessThan);
}
}
return binaryFirst(T, items, value, Range.init(index - skip, index), context, lessThan);
}
fn findFirstBackward(
comptime T: type,
items: []T,
value: T,
range: Range,
unique: usize,
context: anytype,
comptime lessThan: fn (@TypeOf(context), lhs: T, rhs: T) bool,
) usize {
if (range.length() == 0) return range.start;
const skip = @max(range.length() / unique, @as(usize, 1));
var index = range.end - skip;
while (index > range.start and !lessThan(context, items[index - 1], value)) : (index -= skip) {
if (index < range.start + skip) {
return binaryFirst(T, items, value, Range.init(range.start, index), context, lessThan);
}
}
return binaryFirst(T, items, value, Range.init(index, index + skip), context, lessThan);
}
fn findLastForward(
comptime T: type,
items: []T,
value: T,
range: Range,
unique: usize,
context: anytype,
comptime lessThan: fn (@TypeOf(context), lhs: T, rhs: T) bool,
) usize {
if (range.length() == 0) return range.start;
const skip = @max(range.length() / unique, @as(usize, 1));
var index = range.start + skip;
while (!lessThan(context, value, items[index - 1])) : (index += skip) {
if (index >= range.end - skip) {
return binaryLast(T, items, value, Range.init(index, range.end), context, lessThan);
}
}
return binaryLast(T, items, value, Range.init(index - skip, index), context, lessThan);
}
fn findLastBackward(
comptime T: type,
items: []T,
value: T,
range: Range,
unique: usize,
context: anytype,
comptime lessThan: fn (@TypeOf(context), lhs: T, rhs: T) bool,
) usize {
if (range.length() == 0) return range.start;
const skip = @max(range.length() / unique, @as(usize, 1));
var index = range.end - skip;
while (index > range.start and lessThan(context, value, items[index - 1])) : (index -= skip) {
if (index < range.start + skip) {
return binaryLast(T, items, value, Range.init(range.start, index), context, lessThan);
}
}
return binaryLast(T, items, value, Range.init(index, index + skip), context, lessThan);
}
fn binaryFirst(
comptime T: type,
items: []T,
value: T,
range: Range,
context: anytype,
comptime lessThan: fn (@TypeOf(context), lhs: T, rhs: T) bool,
) usize {
var curr = range.start;
var size = range.length();
if (range.start >= range.end) return range.end;
while (size > 0) {
const offset = size % 2;
size /= 2;
const mid_item = items[curr + size];
if (lessThan(context, mid_item, value)) {
curr += size + offset;
}
}
return curr;
}
fn binaryLast(
comptime T: type,
items: []T,
value: T,
range: Range,
context: anytype,
comptime lessThan: fn (@TypeOf(context), lhs: T, rhs: T) bool,
) usize {
var curr = range.start;
var size = range.length();
if (range.start >= range.end) return range.end;
while (size > 0) {
const offset = size % 2;
size /= 2;
const mid_item = items[curr + size];
if (!lessThan(context, value, mid_item)) {
curr += size + offset;
}
}
return curr;
}
fn mergeInto(
comptime T: type,
from: []T,
A: Range,
B: Range,
into: []T,
context: anytype,
comptime lessThan: fn (@TypeOf(context), lhs: T, rhs: T) bool,
) void {
var A_index: usize = A.start;
var B_index: usize = B.start;
const A_last = A.end;
const B_last = B.end;
var insert_index: usize = 0;
while (true) {
if (!lessThan(context, from[B_index], from[A_index])) {
into[insert_index] = from[A_index];
A_index += 1;
insert_index += 1;
if (A_index == A_last) {
// 将 B 的剩余内容复制到最终数组
const from_b = from[B_index..B_last];
@memcpy(into[insert_index..][0..from_b.len], from_b);
break;
}
} else {
into[insert_index] = from[B_index];
B_index += 1;
insert_index += 1;
if (B_index == B_last) {
// 将 A 的剩余部分复制到最终数组中
const from_a = from[A_index..A_last];
@memcpy(into[insert_index..][0..from_a.len], from_a);
break;
}
}
}
}
fn mergeExternal(
comptime T: type,
items: []T,
A: Range,
B: Range,
cache: []T,
context: anytype,
comptime lessThan: fn (@TypeOf(context), lhs: T, rhs: T) bool,
) void {
// A 能放入缓存,因此使用缓存而非内部缓冲区。
var A_index: usize = 0;
var B_index: usize = B.start;
var insert_index: usize = A.start;
const A_last = A.length();
const B_last = B.end;
if (B.length() > 0 and A.length() > 0) {
while (true) {
if (!lessThan(context, items[B_index], cache[A_index])) {
items[insert_index] = cache[A_index];
A_index += 1;
insert_index += 1;
if (A_index == A_last) break;
} else {
items[insert_index] = items[B_index];
B_index += 1;
insert_index += 1;
if (B_index == B_last) break;
}
}
}
// 将 A 的剩余部分复制到最终数组中
const cache_a = cache[A_index..A_last];
@memcpy(items[insert_index..][0..cache_a.len], cache_a);
}
fn swap(
comptime T: type,
items: []T,
order: *[8]u8,
x: usize,
y: usize,
context: anytype,
comptime lessThan: fn (@TypeOf(context), lhs: T, rhs: T) bool,
) void {
if (lessThan(context, items[y], items[x]) or ((order.*)[x] > (order.*)[y] and !lessThan(context, items[x], items[y]))) {
mem.swap(T, &items[x], &items[y]);
mem.swap(u8, &(order.*)[x], &(order.*)[y]);
}
}