跳转到内容
标准库Zig 0.17.1官方原文
源码std/sort/pdq.zig

第 1 行

std.sort.pdq.breakPatterns

函数

第 360 行

fn breakPatterns(a: usize, b: usize, context: anytype) void

参数

a: usize
b: usize

std.sort.pdq.chosePivot

函数

第 384 行

在 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

容器

第 32 行

字段

increasing
decreasing
unknown

std.sort.pdq.lessThan

函数

第 458 行

pub fn lessThan(ctx: @This(), a: usize, b: usize) bool

参数

ctx: @This()
a: usize
b: usize

std.sort.pdq.math

别名

第 4 行

别名目标 std.math

std.sort.pdq.mem

别名

第 3 行

别名目标 std.mem

std.sort.pdq.partialInsertionSort

函数

第 316 行

通过移动若干乱序元素,对切片进行部分排序。

若最终切片已排序,则返回 true。此函数最坏时间复杂度为 O(n)。

fn partialInsertionSort(a: usize, b: usize, context: anytype) bool

参数

a: usize
b: usize

std.sort.pdq.partition

函数

第 189 行

将 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

函数

第 293 行

将元素划分为等于 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

函数

第 11 行

不稳定的原地排序。最佳时间复杂度为 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

函数

第 21 行

pub fn lessThan(ctx: @This(), a: usize, b: usize) bool

参数

ctx: @This()
a: usize
b: usize

std.sort.pdq.pdq.swap

函数

第 25 行

pub fn swap(ctx: @This(), a: usize, b: usize) void

参数

ctx: @This()
a: usize
b: usize

std.sort.pdq.pdqContext

函数

第 52 行

不稳定的原地排序。最佳时间复杂度为 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

容器

第 38 行

字段

a: usize
b: usize
limit: usize
leftmost: bool
balanced: bool
partitioned: bool

std.sort.pdq.reverseRange

函数

第 433 行

fn reverseRange(a: usize, b: usize, context: anytype) void

参数

a: usize
b: usize

std.sort.pdq.sort

别名

第 2 行

别名目标 std.sort

std.sort.pdq.sort3

函数

第 416 行

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

别名

第 1 行

别名目标 std

std.sort.pdq.swap

函数

第 465 行

pub fn swap(ctx: @This(), a: usize, b: usize) void

参数

ctx: @This()
a: usize
b: usize

std.sort.pdq.testing

别名

第 5 行

别名目标 std.testing

std.sort.pdq.unguardedInsertionContext

函数

第 174 行

插入排序,假定 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]);
    }
}