Zen言語の標準ライブラリ紹介〜sort①〜

はじめに

けっこう標準ライブラリが充実しているわけですが、ドキュメントがないのがもったいないですね。 まとまった時間が取れないので、ちょこちょこ書いていくシリーズです。

リクエストあれば、優先する、かも?

ソート関係です。 次の3つの関数を紹介します。

  • binarySearch
  • insertionSort
  • sort

binarySearchstd.sort下で良いのでしょうかね? ソート済みであることが前提ではありますが。

std.sort.binarySearch

ソート済みのスライスitemから、keyの値を検索します。 値の比較はcompareFnで与える比較関数を使用します。 見つかればスライスのインデックスが、見つからない場合nullが返ります。

pub fn binarySearch(comptime T: type, key: T, items: []const T, comptime compareFn: fn (lhs: T, rhs: T) math.Order) ?usize

math.Orderは次のEnumです。

pub const Order = enum {
    /// Less than (`<`)
    lt,

    /// Equal (`==`)
    eq,

    /// Greater than (`>`)
    gt,
};

<, >, ==演算子をサポートする型に対しては、math.orderジェネリック関数になっており、共通して使用できます。

binarySearchの使用方法は次の通りです。

test "std.sort.binarySearch" {
    const input = [_]i32{ -10, -4, 0, 3, 5, 20 };
    // std.math.orderはジェネリック関数なので、型を確定させる
    const Cmp = struct {
        fn order_i32(lhs: i32, rhs: i32) std.math.Order {
            return std.math.order(lhs, rhs); 
        } 
    };

    testing.equal(
        @to(?usize, 1),
        sort.binarySearch(i32, -4, &input, Cmp.order_i32),
    );
}

std.sort.insertionSort

挿入ソートです。 アロケータなしで動くのが嬉しいです。 入力するitemsを直接入れ替えるので、itemsvarでないといけません (constじゃだめ) 。

/// Stable in-place sort. O(n) best case, O(pow(n, 2)) worst case. O(1) memory (no allocator required).
pub fn insertionSort(comptime T: type, items: []T, lessThan: fn (lhs: T, rhs: T) bool) void

sort.asc(i32)はアイテムを昇順に並び替えるための比較関数です。 次回やるので、そういうもんだと納得して下さい。

test "std.sort.insertionSort" {
    var items = [_]i32{ 20, -4, 0, 5, -10, 3 };
    const expect = [_]i32{ -10, -4, 0, 3, 5, 20 };

    sort.insertionSort(i32, items[0..], sort.asc(i32));

    testing.equalSlices(i32, &expect, &items);
}

std.sort.sort

ブロックソートです。 アロケータなしで動くのが嬉しいです。 しかも、O(n*log(n))です。 最高じゃないですか。

/// Stable in-place sort. O(n) best case, O(n*log(n)) worst case and average case. O(1) memory (no allocator required).
/// Currently implemented as block sort.
pub fn sort(comptime T: type, items: []T, lessThan: fn (lhs: T, rhs: T) bool) void

insertionSortと使い方は同じです。

test "std.sort.sort" {
    var items = [_]i32{ 5, 3, 1, 2, 4 };
    sort.sort(i32, items[0..], sort.asc(i32));

    testing.equalSlices(i32, &[_]i32{ 1, 2, 3, 4, 5 }, &items);
}