std.sort.pdq.breakPatterns
函数
fn breakPatterns(a: usize, b: usize, context: anytype) void
参数
a: usize
b: usize
std.sort.pdq.chosePivot
函数
在 items[a..b] 中选择枢轴。
当 items[a..b] 看起来已排序时,交换 likely_sorted。
fn chosePivot(a: usize, b: usize, pivot: *usize, context: anytype) Hint
参数
a: usize
b: usize
pivot: *usize
std.sort.pdq.Hint
容器
字段
increasing
decreasing
unknown
std.sort.pdq.lessThan
函数
pub fn lessThan(ctx: @This(), a: usize, b: usize) bool
参数
ctx: @This()
a: usize
b: usize
std.sort.pdq.math
别名
别名目标 std.math
std.sort.pdq.mem
别名
别名目标 std.mem
std.sort.pdq.partialInsertionSort
函数
通过移动若干乱序元素,对切片进行部分排序。
若最终切片已排序,则返回 true。此函数最坏时间复杂度为 O(n)。
fn partialInsertionSort(a: usize, b: usize, context: anytype) bool
参数
a: usize
b: usize
std.sort.pdq.partition
函数
将 items[a..b] 划分为小于 items[pivot] 的元素,
后接大于或等于 items[pivot] 的元素。
设置新的枢轴。
若原本已完成划分,则返回 true。
fn partition(a: usize, b: usize, pivot: *usize, context: anytype) bool
参数
a: usize
b: usize
pivot: *usize
std.sort.pdq.partitionEqual
函数
将元素划分为等于 items[pivot] 的元素,
后接大于 items[pivot] 的元素。
假定 items[a..b] 中不存在小于 items[pivot] 的元素。
fn partitionEqual(a: usize, b: usize, pivot: usize, context: anytype) usize
参数
a: usize
b: usize
pivot: usize
std.sort.pdq.pdq
函数
不稳定的原地排序。最佳时间复杂度为 n,最坏和平均为 n*log(n)。 内存复杂度为 log(n),不需要分配器。
按给定 lessThan 函数定义的关系升序排序。
pub fn pdq( comptime T: type, items: []T, context: anytype, comptime lessThanFn: fn (context: @TypeOf(context), lhs: T, rhs: T) bool, ) void
参数
T: type
items: []T
lessThanFn: fn (context: @TypeOf(context), lhs: T, rhs: T) bool
std.sort.pdq.pdq.lessThan
函数
pub fn lessThan(ctx: @This(), a: usize, b: usize) bool
参数
ctx: @This()
a: usize
b: usize
std.sort.pdq.pdq.swap
函数
pub fn swap(ctx: @This(), a: usize, b: usize) void
参数
ctx: @This()
a: usize
b: usize
std.sort.pdq.pdqContext
函数
不稳定的原地排序。最佳时间复杂度为 O(n),最坏和平均为 O(n*log(n))。
内存复杂度为 O(log(n)),不需要分配器。
context 必须具有 swap 和 lessThan 方法,
每个方法接受两个表示条目索引的 usize 参数。
按 lessThan 定义的关系升序排序。
pub fn pdqContext(a: usize, b: usize, context: anytype) void
参数
a: usize
b: usize
std.sort.pdq.Range
容器
字段
a: usize
b: usize
limit: usize
leftmost: bool
balanced: bool
partitioned: bool
std.sort.pdq.reverseRange
函数
fn reverseRange(a: usize, b: usize, context: anytype) void
参数
a: usize
b: usize
std.sort.pdq.sort
别名
别名目标 std.sort
std.sort.pdq.sort3
函数
fn sort3(a: usize, b: usize, c: usize, swaps: *usize, context: anytype) void
参数
a: usize
b: usize
c: usize
swaps: *usize
std.sort.pdq.std
别名
别名目标 std
std.sort.pdq.swap
函数
pub fn swap(ctx: @This(), a: usize, b: usize) void
参数
ctx: @This()
a: usize
b: usize
std.sort.pdq.testing
别名
别名目标 std.testing
std.sort.pdq.unguardedInsertionContext
函数
插入排序,假定 items[a-1] 存在且 <= [a, b) 中所有元素,因此内层循环可省略边界检查。
fn unguardedInsertionContext(a: usize, b: usize, context: anytype) void
参数
a: usize
b: usize
源码
std/sort/pdq.zig
const std = @import("../std.zig");
const sort = std.sort;
const mem = std.mem;
const math = std.math;
const testing = std.testing;
/// 不稳定的原地排序。最佳时间复杂度为 n,最坏和平均为 n*log(n)。
/// 内存复杂度为 log(n),不需要分配器。
///
/// 按给定 `lessThan` 函数定义的关系升序排序。
pub fn pdq(
comptime T: type,
items: []T,
context: anytype,
comptime lessThanFn: fn (context: @TypeOf(context), lhs: T, rhs: T) bool,
) void {
const Context = struct {
items: []T,
sub_ctx: @TypeOf(context),
pub fn lessThan(ctx: @This(), a: usize, b: usize) bool {
return lessThanFn(ctx.sub_ctx, ctx.items[a], ctx.items[b]);
}
pub fn swap(ctx: @This(), a: usize, b: usize) void {
return mem.swap(T, &ctx.items[a], &ctx.items[b]);
}
};
pdqContext(0, items.len, Context{ .items = items, .sub_ctx = context });
}
const Hint = enum {
increasing,
decreasing,
unknown,
};
const Range = struct {
a: usize,
b: usize,
limit: usize,
leftmost: bool,
balanced: bool,
partitioned: bool,
};
/// 不稳定的原地排序。最佳时间复杂度为 O(n),最坏和平均为 O(n*log(n))。
/// 内存复杂度为 O(log(n)),不需要分配器。
/// `context` 必须具有 `swap` 和 `lessThan` 方法,
/// 每个方法接受两个表示条目索引的 `usize` 参数。
/// 按 `lessThan` 定义的关系升序排序。
pub fn pdqContext(a: usize, b: usize, context: anytype) void {
// 长度不超过此值的切片使用插入排序。
const max_insertion = 24;
// 切换到堆排序前允许的不平衡分区次数。
const max_limit = if (b > a) math.log2_int(usize, b - a) else 0;
// 由于每次迭代都将较长的分区压栈,栈使用量以 log_2(n) 为界。
var stack: [@bitSizeOf(usize)]Range = undefined;
var range = Range{
.a = a,
.b = b,
.limit = max_limit,
.leftmost = true,
.balanced = true,
.partitioned = true,
};
var top: usize = 0;
while (true) {
while (true) {
const len = range.b - range.a;
// 很短的切片使用插入排序。
if (len <= max_insertion) {
if (range.leftmost) {
break sort.insertionContext(range.a, range.b, context);
} else {
break unguardedInsertionContext(range.a, range.b, context);
}
}
// 如果过多次选择了不合适的枢轴,直接回退到堆排序,
// 保证最坏时间复杂度为 O(n*log(n))。
if (range.limit == 0) {
break sort.heapContext(range.a, range.b, context);
}
// 如果上一次分区不平衡,则通过打乱部分元素
// 来尝试破坏切片中的模式,希望此次选到更好的枢轴。
if (!range.balanced) {
breakPatterns(range.a, range.b, context);
range.limit -= 1;
}
// 选择枢轴,尝试判断切片是否已经有序。
var pivot: usize = 0;
var hint = chosePivot(range.a, range.b, &pivot, context);
if (hint == .decreasing) {
// 已执行最大允许交换次数,因此项目很可能按逆序排列。将其反转以加速排序。
//
reverseRange(range.a, range.b, context);
pivot = (range.b - 1) - (pivot - range.a);
hint = .increasing;
}
// 若上次分区相当均衡且未打乱元素,并且枢轴选择
// 预测切片很可能已经排序……
if (range.balanced and range.partitioned and hint == .increasing) {
// 尝试找出几个乱序元素,并将它们移至正确
// 位置。如果切片已完全有序,便已完成。
if (partialInsertionSort(range.a, range.b, context)) break;
}
// 若所选枢轴等于前驱,则它是切片中的最小元素。
// 将切片划分为等于枢轴和大于枢轴的元素。
// 切片包含大量重复元素时,通常会进入此分支。
if (range.a > a and !context.lessThan(range.a - 1, pivot)) {
range.a = partitionEqual(range.a, range.b, pivot, context);
continue;
}
// 对切片进行分区。
var mid = pivot;
const was_partitioned = partition(range.a, range.b, &mid, context);
const left_len = mid - range.a;
const right_len = range.b - (mid + 1);
const balanced_threshold = len / 8;
const left_is_smaller = left_len < right_len;
const smaller_len = if (left_is_smaller) left_len else right_len;
const was_balanced = smaller_len >= balanced_threshold;
const smaller_start_offset = if (left_is_smaller) range.a else mid + 1;
const larger_start_offset = if (left_is_smaller) mid + 1 else range.a;
const smaller_end_exclusive_offset = if (left_is_smaller) mid else range.b;
const larger_end_exclusive_offset = if (left_is_smaller) range.b else mid;
const smaller_is_leftmost = if (left_is_smaller) range.leftmost else false;
const larger_is_leftmost = if (left_is_smaller) false else range.leftmost;
// 推迟排序较大的范围,确保栈占用始终小于 log_2(n):
// 如果每次都将超过一半的范围压栈,则每次压栈
// 都会使后续迭代可压栈的元素数量至少减少 n/2,
// 因此栈中元素数绝不会超过 log_2(n)。
stack[top] = .{
.a = larger_start_offset,
.b = larger_end_exclusive_offset,
.limit = range.limit,
.leftmost = larger_is_leftmost,
.balanced = was_balanced,
.partitioned = was_partitioned,
};
top += 1;
// 立即对较小范围排序
range.a = smaller_start_offset;
range.b = smaller_end_exclusive_offset;
range.leftmost = smaller_is_leftmost;
range.balanced = true; // 此条件要么已经成立,要么范围很小,无需在意。
range.partitioned = was_partitioned;
}
top = math.sub(usize, top, 1) catch break;
range = stack[top];
}
}
/// 插入排序,假定 `items[a-1]` 存在且 <= `[a, b)` 中所有元素,因此内层循环可省略边界检查。
///
fn unguardedInsertionContext(a: usize, b: usize, context: anytype) void {
var i = a + 1;
while (i < b) : (i += 1) {
var j = i;
while (context.lessThan(j, j - 1)) : (j -= 1) {
context.swap(j, j - 1);
}
}
}
/// 将 `items[a..b]` 划分为小于 `items[pivot]` 的元素,
/// 后接大于或等于 `items[pivot]` 的元素。
///
/// 设置新的枢轴。
/// 若原本已完成划分,则返回 `true`。
fn partition(a: usize, b: usize, pivot: *usize, context: anytype) bool {
// 将枢轴移到首位
context.swap(a, pivot.*);
var i = a + 1;
var j = b - 1;
while (i <= j and context.lessThan(i, a)) i += 1;
while (i <= j and !context.lessThan(j, a)) j -= 1;
// 检查元素是否已完成分区(没有需要交换的元素)
if (i > j) {
// 将枢轴放回中间
context.swap(j, a);
pivot.* = j;
return true;
}
context.swap(i, j);
i += 1;
j -= 1;
const block_size = 64;
var offsets_l: [block_size]u8 align(std.atomic.cache_line) = undefined;
var offsets_r: [block_size]u8 align(std.atomic.cache_line) = undefined;
var offsets_l_base = i;
var offsets_r_base = j;
var num_l: usize = 0;
var num_r: usize = 0;
var start_l: usize = 0;
var start_r: usize = 0;
while (i <= j) {
const num_unknown = j + 1 - i;
const left_split = if (num_l == 0)
@min(block_size, if (num_r == 0) num_unknown / 2 else num_unknown)
else
0;
const right_split = if (num_r == 0)
@min(block_size, num_unknown - left_split)
else
0;
for (0..left_split) |k| {
offsets_l[num_l] = @intCast(k);
num_l += @intFromBool(!context.lessThan(i + k, a));
}
i += left_split;
for (0..right_split) |k| {
offsets_r[num_r] = @intCast(k);
num_r += @intFromBool(context.lessThan(j - k, a));
}
j -= right_split;
const num = @min(num_l, num_r);
for (0..num) |m| {
context.swap(
offsets_l_base + offsets_l[start_l + m],
offsets_r_base - offsets_r[start_r + m],
);
}
num_l -= num;
num_r -= num;
start_l += num;
start_r += num;
if (num_l == 0) {
start_l = 0;
offsets_l_base = i;
}
if (num_r == 0) {
start_r = 0;
offsets_r_base = j;
}
}
if (num_l > 0) {
while (num_l > 0) {
num_l -= 1;
context.swap(offsets_l_base + offsets_l[start_l + num_l], j);
j -= 1;
}
i = j + 1;
}
if (num_r > 0) {
while (num_r > 0) {
num_r -= 1;
context.swap(offsets_r_base - offsets_r[start_r + num_r], i);
i += 1;
}
j = i - 1;
}
context.swap(j, a);
pivot.* = j;
return false;
}
/// 将元素划分为等于 `items[pivot]` 的元素,
/// 后接大于 `items[pivot]` 的元素。
///
/// 假定 `items[a..b]` 中不存在小于 `items[pivot]` 的元素。
fn partitionEqual(a: usize, b: usize, pivot: usize, context: anytype) usize {
// 将枢轴移到首位
context.swap(a, pivot);
var i = a + 1;
var j = b - 1;
while (true) {
while (i <= j and !context.lessThan(a, i)) i += 1;
while (i <= j and context.lessThan(a, j)) j -= 1;
if (i > j) break;
context.swap(i, j);
i += 1;
j -= 1;
}
return i;
}
/// 通过移动若干乱序元素,对切片进行部分排序。
///
/// 若最终切片已排序,则返回 `true`。此函数最坏时间复杂度为 `O(n)`。
fn partialInsertionSort(a: usize, b: usize, context: anytype) bool {
@branchHint(.cold);
// 将要移位的相邻逆序对的最大数量
const max_steps = 5;
// 若切片短于此值,则不移动任何元素
const shortest_shifting = 50;
var i = a + 1;
for (0..max_steps) |_| {
// 查找下一对相邻的乱序元素。
while (i < b and !context.lessThan(i, i - 1)) i += 1;
// 是否已完成?
if (i == b) return true;
// 短数组上不移动元素,因为这会带来性能开销。
if (b - a < shortest_shifting) return false;
// 交换找到的元素对,使其处于正确顺序。
context.swap(i, i - 1);
// 将较小的元素左移。
if (i - a >= 2) {
var j = i - 1;
while (j > a) : (j -= 1) {
if (!context.lessThan(j, j - 1)) break;
context.swap(j, j - 1);
}
}
// 将较大的元素右移。
if (b - i >= 2) {
var j = i + 1;
while (j < b) : (j += 1) {
if (!context.lessThan(j, j - 1)) break;
context.swap(j, j - 1);
}
}
}
return false;
}
fn breakPatterns(a: usize, b: usize, context: anytype) void {
@branchHint(.cold);
const len = b - a;
if (len < 8) return;
var rand = @as(u64, @intCast(len));
const modulus = math.ceilPowerOfTwoAssert(u64, len);
var i = a + (len / 4) * 2 - 1;
while (i <= a + (len / 4) * 2 + 1) : (i += 1) {
// xorshift64
rand ^= rand << 13;
rand ^= rand >> 7;
rand ^= rand << 17;
var other = @as(usize, @intCast(rand & (modulus - 1)));
if (other >= len) other -= len;
context.swap(i, a + other);
}
}
/// 在 `items[a..b]` 中选择枢轴。
/// 当 `items[a..b]` 看起来已排序时,交换 likely_sorted。
fn chosePivot(a: usize, b: usize, pivot: *usize, context: anytype) Hint {
// 使用 Tukey 九数中位数方法的最小长度
const shortest_ninther = 50;
// max_swaps 是此函数中允许的最大交换次数
const max_swaps = 4 * 3;
const len = b - a;
const i = a + len / 4 * 1;
const j = a + len / 4 * 2;
const k = a + len / 4 * 3;
var swaps: usize = 0;
if (len >= 8) {
if (len >= shortest_ninther) {
// 在 `i`、`j` 和 `k` 的邻域中查找中位数
sort3(i - 1, i, i + 1, &swaps, context);
sort3(j - 1, j, j + 1, &swaps, context);
sort3(k - 1, k, k + 1, &swaps, context);
}
// 查找 `i`、`j` 和 `k` 三者的中位数,并存入 `j`
sort3(i, j, k, &swaps, context);
}
pivot.* = j;
return switch (swaps) {
0 => .increasing,
max_swaps => .decreasing,
else => .unknown,
};
}
fn sort3(a: usize, b: usize, c: usize, swaps: *usize, context: anytype) void {
if (context.lessThan(b, a)) {
swaps.* += 1;
context.swap(b, a);
}
if (context.lessThan(c, b)) {
swaps.* += 1;
context.swap(c, b);
}
if (context.lessThan(b, a)) {
swaps.* += 1;
context.swap(b, a);
}
}
fn reverseRange(a: usize, b: usize, context: anytype) void {
var i = a;
var j = b - 1;
while (i < j) {
context.swap(i, j);
i += 1;
j -= 1;
}
}
test "pdqContext respects arbitrary range boundaries" {
// 问题 #25250 的回归测试。
// pdqsort 绝不应访问指定 [a, b) 范围之外的索引。
var data: [2000]i32 = @splat(0);
// 填入能触发 partialInsertionSort 路径的数据
for (0..data.len) |i| {
data[i] = @intCast(@mod(@as(i32, @intCast(i)) * 7, 100));
}
const TestContext = struct {
items: []i32,
range_start: usize,
range_end: usize,
pub fn lessThan(ctx: @This(), a: usize, b: usize) bool {
// 断言索引位于预期范围内
testing.expect(a >= ctx.range_start and a < ctx.range_end) catch @panic("index a out of range");
testing.expect(b >= ctx.range_start and b < ctx.range_end) catch @panic("index b out of range");
return ctx.items[a] < ctx.items[b];
}
pub fn swap(ctx: @This(), a: usize, b: usize) void {
// 断言索引位于预期范围内
testing.expect(a >= ctx.range_start and a < ctx.range_end) catch @panic("index a out of range");
testing.expect(b >= ctx.range_start and b < ctx.range_end) catch @panic("index b out of range");
mem.swap(i32, &ctx.items[a], &ctx.items[b]);
}
};
// 测试排序一个起点不为 0 的子范围。
const start = 1118;
const end = 1764;
const ctx = TestContext{
.items = &data,
.range_start = start,
.range_end = end,
};
pdqContext(start, end, ctx);
// 验证范围已排序
for ((start + 1)..end) |i| {
try testing.expect(data[i - 1] <= data[i]);
}
}