Sort function for chunks of a slice

Help
1

Hello,
so I made a little Gauss Matrix solver because I was bored and rewrote it to instead of being a [][]f32 be a []f32. The problem is the following function:

    fn sort(matrix: [][]f32) void {
        const lt = struct {
            fn f(_: void, lhs: []f32, rhs: []f32) bool {
                std.debug.assert(lhs.len == rhs.len);
                return std.mem.indexOfNone(f32, lhs, &.{0}) orelse lhs.len <
                    std.mem.indexOfNone(f32, rhs, &.{0}) orelse rhs.len;
            }
        }.f;
        std.sort.pdq([]f32, matrix, {}, lt);
    }

Is there a way to rewrite this so that the function signature looks like this:

    /// n is the width of the matrix
    fn sort(matrix: []f32, n: usize) void { ... }

while still using the standard libraries sorting functions and no allocator?

2

Is n the width of the matrix?

3

Yes, Im sorry I forgot to mention that in the original question

4

After some more thinking about how to do things I decided to make the matrix size comptime known and just save it internally as a [m][n]f32, which achieves the fewer allocations very nicely lol

I still wonder how to do the sorting the way i originally asked, though.

5

You can do it by using a Context object with pdqContext (or other sort functions of the *Context variant), it allows you to map the usize a and b indexes, which are passed to the lessThan and swap functions, in a way where these indexes represent the row that is currently being sorted.

const std = @import("std");

fn sort(matrix: []f32, n: usize) void {
    const Context = struct {
        items: []f32,
        columns: usize,

        pub fn lessThan(ctx: @This(), a: usize, b: usize) bool {
            const c = ctx.columns;
            const lhs = ctx.items[a*c..][0..c];
            const rhs = ctx.items[b*c..][0..c];
            return std.mem.indexOfNone(f32, lhs, &.{0}) orelse lhs.len <
                std.mem.indexOfNone(f32, rhs, &.{0}) orelse rhs.len;
        }

        pub fn swap(ctx: @This(), a: usize, b: usize) void {
            const c = ctx.columns;
            const lhs = ctx.items[a*c..][0..c];
            const rhs = ctx.items[b*c..][0..c];
            for(lhs, rhs) |*l, *r| std.mem.swap(f32, l, r);
        }
    };

    const rows = matrix.len / n;
    std.debug.assert(rows * n == matrix.len);
    std.sort.pdqContext(0, rows, Context{.items = matrix, .columns = n});
}

pub fn printMatrix(matrix:[]f32, n:usize) void {
    for(0..n) |i| {
        for(0..n) |j| {
            std.debug.print("{} ",.{matrix[4*i+j]});
        }
        std.debug.print("\n",.{});
    }
}

pub fn main() !void {
    var test_matrix = [_]f32{
        0.0, 0.0, 3.0, 0.0,
        0.0, 4.0, 0.0, 0.0,
        0.0, 0.0, 0.0, 2.0,
        7.0, 0.0, 0.0, 0.0,
    };

    printMatrix(&test_matrix, 4);
    std.debug.print("\n",.{});

    sort(&test_matrix, 4);

    std.debug.print("\n",.{});
    printMatrix(&test_matrix, 4);
}
2 Likes
6

Oh thats why the context versions exist :sweat_smile:, the more you know. The more I work with the zig std lib the more i think its better thought through than honestly most of the “big” languages.

1 Like
7

Same here! I worked with not too much languages, but quite extensive. Zig beats them all by miles.

1 Like