Zig言語におけるソート処理
Zig言語で標準ライブラリを利用してソートする方法を調べたので、その調べた結果を記事に残しておきたいと思います。
まずは、標準ライブラリより提供されているソート関数についての説明をして、その後に具体例として数値、文字列、構造体におけるソート処理を紹介したいと思います。また、標準ライブラリより提供されるソート関数には他の言語ではあまり見ないContextを使ったソートというものがあるので、最後にそちらも紹介します。
前提
想定読者
- Zigを使っていて、ソート処理をどのように実装すれば良いか疑問に思った人
- Zig標準ライブラリより提供されている、ソート関数のContextの使い道が分からない人
話さないこと
- Zig標準ライブラリより提供されているソート関数の内部実装について
- ソートアルゴリズムについて
環境（Zigバージョン）
$ zig version
0.16.0-dev.747+493ad58ff
標準ライブラリより提供されているsort関数について
Zigの標準ライブラリ（std.memモジュール）より提供されているsort関数は以下の4つです。
- sort
- sortContext
- sortUnstable
- sortUnstableContext
関数名から推測できるとは思いますがStableか否か、Contextがあるか否かの2軸でそれぞれの特徴を分類できます。
| Context無し | Context有り | |
|---|---|---|
| Stable | sort | sortContext |
| Unstable | sortUnstable | sortUnstableContext |
ソートが安定か否かはZig固有の話ではないので既にご存知の方がいるかもしれないですが、順位が同じ場合に元々の並び順を保つか否かで安定か否かが分かれます。元々の並び順が保たれたソートは安定ソートであるとみなされます。
ソート対象となるスライスの要素が単純な数値や文字列の場合では元々の並び順を保証したいケースは少ないかもしれないです。一方で要素が構造体といった複合的なデータ構造である場合は、元々の並び順を保証したいような場合があるかと思うので、そういったケースにおいて安定ソートを利用するのが良いでしょう。
Contextについては後続の説明、具体例を見てもらうのが良いと思いますが、簡単に触れておくとソート対象となるデータ列の他に、ソート処理（並び順を判断する処理）に際して与えたいデータがここでいうContextに該当します。
Contextに関連して一点補足しておくと、後続の具体例を見てもらえれば分かると思いますが、Context無しのsort関数だからと言ってContextを利用できないという訳では決してないです。Context有りの関数だと、引数として渡すContextにソート処理に必要なあらゆるデータ、ロジックを記載するようなイメージです。
数値に対するソート処理
ソート対象となるスライスの要素が数値の場合は特に難しいことをする必要はありません。標準ライブラリを呼びだすだけでソート処理を実装できます。
まずは具体例を見ていきましょう。
const std = @import("std");
pub fn main() void {
var arr = [_]u8{ 5, 3, 8, 1, 2 };
std.mem.sort(u8, &arr, {}, comptime std.sort.asc(u8));
std.debug.print("Sorted array: {any}\n", .{arr});
// Sorted array: { 1, 2, 3, 5, 8 }
}
sort関数の関数シグネチャは
pub fn sort(
comptime T: type, // ソート対象となる要素の型
items: []T, // ソート対象となるスライス
context: anytype, // Context
comptime lessThanFn: fn (@TypeOf(context), lhs: T, rhs: T) bool, // 並び順ルールに関するロジック
) void
となっています。
第三引数のcontextについては一番最後に「Contextを利用したソート処理」という章を設けているので、そこで詳しく説明します。
第四引数のlessThanFnについては、並び順ルールに関する関数を指定します。上の例でも使用した標準ライブラリより提供されている昇順ソート、降順ソート用の実装を見てみると意味が分かるかと思います。
/// Use to generate a comparator function for a given type. e.g. `sort(u8, slice, {}, asc(u8))`.
pub fn asc(comptime T: type) fn (void, T, T) bool {
return struct {
pub fn inner(_: void, a: T, b: T) bool {
return a < b;
}
}.inner;
}
/// Use to generate a comparator function for a given type. e.g. `sort(u8, slice, {}, desc(u8))`.
pub fn desc(comptime T: type) fn (void, T, T) bool {
return struct {
pub fn inner(_: void, a: T, b: T) bool {
return a > b;
}
}.inner;
}
昇順ソートの場合、値が小さいものから大きいものに並べることになるので、aとbという二つの要素を比較する際に値が小さい方がtrueになるような関数を指定することになります。
文字列に対するソート処理
第四引数に渡す関数について、文字列を対象とした関数は数値の時とは異なり標準ライブラリより提供されていないので自分で実装する必要があります。ただ、アルファベットの並び順を比較する関数は提供されているので、そちらの関数を利用すれば簡単に実装できます。
実際に実装した例が以下になります。
const std = @import("std");
fn stringLessThan(_: void, lhs: []const u8, rhs: []const u8) bool {
return std.mem.order(u8, lhs, rhs) == .lt;
}
pub fn main() void {
var str_arr = [_][]const u8{ "banana", "apple", "pineapple", "cherry", "grape" };
std.mem.sort([]const u8, &str_arr, {}, stringLessThan);
for (str_arr) |s| {
std.debug.print("{s}\n", .{s});
}
// apple
// banana
// cherry
// grape
// pineapple
}
因みに、大文字小文字を区別せずにソートしたい場合にはstd.ascii.orderIgnoreCase関数を利用すると良いでしょう。
fn stringLessThan(_: void, lhs: []const u8, rhs: []const u8) bool {
return std.ascii.orderIgnoreCase(lhs, rhs) == .lt;
}
構造体に対するソート処理
構造体に対するソート処理についても先程の文字列に対するソート処理のように、並び順ルールを記述した関数を自分で用意する必要があります。
const std = @import("std");
const User = struct {
name: []const u8,
age: u8,
fn nameLessThan(_: void, lhs: User, rhs: User) bool {
return std.ascii.orderIgnoreCase(lhs.name, rhs.name) == .lt;
}
fn ageLessThan(_: void, lhs: User, rhs: User) bool {
return lhs.age < rhs.age;
}
};
pub fn main() void {
var users = [_]User{
.{ .name = "Dave", .age = 28 },
.{ .name = "charlie", .age = 35 },
.{ .name = "Alice", .age = 30 },
.{ .name = "bob", .age = 25 },
};
var users2 = users;
std.mem.sort(User, &users, {}, User.nameLessThan);
for (users) |user| {
std.debug.print("Name: {s}, Age: {d}\n", .{ user.name, user.age });
}
// Name: Alice, Age: 30
// Name: bob, Age: 25
// Name: charlie, Age: 35
// Name: Dave, Age: 28
std.mem.sort(User, &users2, {}, User.ageLessThan);
for (users2) |user| {
std.debug.print("Name: {s}, Age: {d}\n", .{ user.name, user.age });
}
// Name: bob, Age: 25
// Name: Dave, Age: 28
// Name: Alice, Age: 30
// Name: charlie, Age: 35
}
Contextを利用したソート処理
冒頭でも説明した通りsort関数には関数名にContextが入っているものとそうでないものがありますが、関数名にContextの文字がない関数でもContextを利用したソート処理は可能です。
関数名のContext有無で関数のインターフェースが異なるので、それぞれ分けて説明します。
関数名にContextが無いsort関数でのContextを利用したソート
ソート対象以外のデータを使って並び順を決定したいようなケースでContextが必要になってきます。
ここでは具体例として、スライス内各要素の値を利用して、各要素のインデックス（元々の並び順）を並び替えるようなケースを想定してみます。
まずは実装を見てみましょう。
const std = @import("std");
const Context = struct {
values: []const u8,
fn lessThan(self: Context, lhs: usize, rhs: usize) bool {
return self.values[lhs] < self.values[rhs];
}
};
fn sortIndices(indices: []usize, values: []const u8) void {
const ctx = Context{ .values = values };
std.mem.sort(usize, indices, ctx, Context.lessThan);
}
pub fn main() void {
var arr = [_]u8{ 8, 3, 5, 1, 4, 7, 6, 2 };
var indices: [arr.len]usize = undefined;
for (0..arr.len) |i| {
indices[i] = i;
}
sortIndices(&indices, &arr);
std.debug.print("Sorted indices: {any}\n", .{indices});
std.debug.print("Sorted values: ", .{});
for (indices) |idx| {
std.debug.print("{d} ", .{arr[idx]});
}
std.debug.print("\n", .{});
// Sorted indices: { 3, 7, 1, 4, 2, 6, 5, 0 }
// Sorted values: 1 2 3 4 5 6 7 8
}
この例では、ソート対象となる変数indicesは並び順を判定する際に利用する各要素の値についてのデータを持っていません。
そこでContextとして、並び順を判定するロジックで必要となるデータを渡してあげます。
const Context = struct {
values: []const u8, // contextの中身
...
};
fn sortIndices(indices: []usize, values: []const u8) void {
const ctx = Context{ .values = values }; // contextの作成
std.mem.sort(usize, indices, ctx, Context.lessThan); // sort関数の第三引数にcontextを渡す
}
そして、sort関数の第四引数で渡す関数の第一引数でContextを受け取り、そのContextを使用した並び順判定ロジックを実装します。
const Context = struct {
values: []const u8,
// 第一引数でcontextを受け取る
fn lessThan(self: Context, lhs: usize, rhs: usize) bool {
// contextを利用した並び順判定ロジックを実装
return self.values[lhs] < self.values[rhs];
}
};
今回はContextとlessThanFnの繋がりをイメージしやすい形で表現するために、ContextとlessThanFnを同一構造体にまとめましたが、構造体にまとめる必要はありません。つまり、sortIndices関数を以下のような実装にしても全く問題ありません。重要なのは、Contextとして渡す値を利用する形でlessThanFn関数を実装することにあります。
fn lessThan(values: []const u8, lhs: usize, rhs: usize) bool {
return values[lhs] < values[rhs];
}
fn sortIndices(indices: []usize, values: []const u8) void {
std.mem.sort(usize, indices, values, lessThan);
}
関数名にContextが有るsort関数でのContextを利用したソート
Contextについての考え方自体は先程までと変わりありませんが、関数の使い方、呼び出し方等で少し違いがあります。
まずはsortContext関数の関数シグネチャを見てみましょう。
sortContext(a: usize, b: usize, context: anytype) void
第一、第二引数はスライスのインデックスを指していて、どこからどこの区間にある要素がソート対象であるかを指定するための変数です。また、区間は左閉右開区間[a, b)になっているので、スライス全体に対してソート処理を適用したい場合はaに0をbにスライスの長さを指定することになります。
そして第三引数のContextにソート対象となるスライスや並び順を指定するためのロジックを持つ構造体を渡します。注意点としては、ここまで登場してきた並び順を判定するための関数であるlessThan関数の他に、要素を入れ替えるためのswap関数も実装する必要があります。
実装例は以下のようなものになります。
const std = @import("std");
const Context = struct {
values: []u8,
pub fn lessThan(self: Context, lhs: usize, rhs: usize) bool {
return self.values[lhs] < self.values[rhs];
}
pub fn swap(self: Context, lhs: usize, rhs: usize) void {
std.mem.swap(u8, &self.values[lhs], &self.values[rhs]);
}
};
pub fn main() void {
var arr = [_]u8{ 8, 3, 5, 1, 4, 7, 6, 2 };
const context = Context{ .values = &arr };
std.mem.sortContext(0, 4, context);
for (0..arr.len) |i| {
std.debug.print("{d} ", .{arr[i]});
}
std.debug.print("\n", .{});
// 1 3 5 8 4 7 6 2
}
出力結果をみると、ソート対象として指定したスライス前半についてはソートされていて、範囲外のスライス後半については並び順が変わっていないことが分かります。
参考資料
Discussion