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

はじめに

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

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

ソート関係ですが、ソート本体以外にstd.sortにあるものを紹介します。

std.sort.asc

<演算子が定義されている型Tに対して、fn (a: T, b: T) bool { return a < b } を計算する関数ポインタを返します。 コメントにあるように、sort()関数呼び出し時に引数渡しする比較関数を生成するために使います。

// Use these to generate a comparator function for a given type. e.g. `sort(u8, slice, asc(u8))`.
pub fn asc(comptime T: type) fn (T, T) bool
const std = @import("std");
const sort = std.sort;
const testing = std.testing;

test "std.sort.asc" {
    const asc_u8 = sort.asc(u8);
    // true if `a` is less than `b`
    testing.ok(asc_u8(1, 2));
    testing.ok(!asc_u8(2, 2));
    testing.ok(!asc_u8(2, 1));
}

実装は次の通りなのですが、a < bを返さずに、generic.lessThanを使えば、構造体にも使えるようになる気が…?

pub fn asc(comptime T: type) fn (T, T) bool {
    const impl = struct {
        fn inner(a: T, b: T) bool {
            return a < b;
        }
    };

    return impl.inner;
}

現状では、構造体の型を渡すとコンパイルエラーになります。 次はコンパイルエラーです。

test "std.sort.asc for struct" {
    const S = struct {
        a: usize,
        b: f64,
    };
    const asc_s = sort.asc(S);
}
error[E09063]: operator not allowed for type 'S'
            return a < b;
                     ~

後で修正リクエスト投げてみましょう。

std.sort.desc

ascの逆版です。 fn (a: T, b: T) bool { return a > b } を計算する関数ポインタを返します。

pub fn desc(comptime T: type) fn (T, T) bool
test "std.sort.desc" {
    const asc_u8 = sort.desc(u8);
    // true if `a` is bigger than `b`
    testing.ok(asc_u8(2, 1));
    testing.ok(!asc_u8(2, 2));
    testing.ok(!asc_u8(1, 2));
}

std.sort.min / std.sort.argMin

任意型のスライスの中で最も小さい値を返します。 スライスの要素数0の場合のみ、nullを返します。

pub fn min(comptime T: type, items: []const T, lessThan: fn (lhs: T, rhs: T) bool) ?T

最も小さい値が格納されているインデックスを返します。

pub fn argMin(comptime T: type, items: []const T, lessThan: fn (lhs: T, rhs: T) bool) ?usize

使い方は、次のような感じです。

test "std.sort.min" {
    const inputs = [_]i32{ 10, -5, 3, 20, -4 };
    testing.equal(@to(?i32, -5), sort.min(i32, &inputs, sort.asc(i32)));

    const position = sort.argMin(i32, &inputs, sort.asc(i32));
    testing.equal(@to(?usize, 1), position);
    testing.equal(@to(i32, -5), inputs[position.?]);
}

std.sort.max / std.sort.argMax

minのmax版です。

std.sort.isSorted

与えたスライスがソート済みかどうかをブール値で返します。

pub fn isSorted(comptime T: type, items: []const T, lessThan: fn (lhs: T, rhs: T) bool) bool
test "std.sort.isSorted" {
    const sorted = [_]i32{ -1, 0, 1, 2, 3, 4, 5 };
    const unsorted = [_]i32{ 2, 0, 1, -1, 3, 4, 5 };

    testing.ok(sort.isSorted(i32, &sorted, sort.asc(i32)));
    testing.ok(!sort.isSorted(i32, &unsorted, sort.asc(i32)));
}

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);
}

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

はじめに

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

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

今日は時間関係です。

std.time.

std.time.sleep

普通のスリープ関数です。 引数は、スリープする秒数をナノ秒単位で与えます。

/// Spurious wakeups are possible and no precision of timing is guaranteed.
pub fn sleep(nanoseconds: u64) void
test "sleep" {
    // sleep 1 second
    time.sleep(1 * time.second);
}

ナノ秒単位で真面目に指定するのは大変ですが、定数が次のように定義されているので、必要に応じて使います。

/// Multiples of a base unit (nanoseconds)
pub const nanosecond = 1;
pub const microsecond = 1000 * nanosecond;
pub const millisecond = 1000 * microsecond;
pub const second = 1000 * millisecond;
pub const minute = 60 * second;
pub const hour = 60 * minute;

/// Divisions of a second
pub const ns_per_s = 1000000000;
pub const us_per_s = 1000000;
pub const ms_per_s = 1000;
pub const cs_per_s = 100;

/// Common time divisions
pub const s_per_min = 60;
pub const s_per_hour = s_per_min * 60;
pub const s_per_day = s_per_hour * 24;
pub const s_per_week = s_per_day * 7;

std.time.timestamp

秒単位のPOSIXタンムスタンプを取得します。

/// Get the posix timestamp, UTC, in seconds
pub fn timestamp() u64
test "timestamp" {
    debug.warn("timestamp = {}\n", .{ time.timestamp() });
    // sleep 1 second
    time.sleep(1 * time.second);

    debug.warn("timestamp = {}\n", .{ time.timestamp() });
}

出力は次のような感じです。タイムスタンプが1増えてますね。

timestamp = 1582431127
timestamp = 1582431128

std.time.milliTimestamp

ミリ秒版です。

pub fn milliTimestamp() u64

std.timer.Timer

簡易タイマーです。 イベントのハンドリングなどはできません。

Timer.start() もしくは Timer.reset() から経過した時間を計測できます。

pub const Timer = struct {
    /// Initialize the timer structure.
    pub fn start() Error!Timer

    /// Reads the timer value since start or the last reset in nanoseconds
    pub fn read(self: *Timer) u64

    /// Resets the timer value to 0/now.
    pub fn reset(self: *Timer) void

    /// Returns the current value of the timer in nanoseconds, then resets it
    pub fn lap(self: *Timer) u64
test "timer" {
    var timer = try time.Timer.start();

    const time_0 = timer.read();
    time.sleep(50 * time.millisecond);
    const time_1 = timer.read();
    testing.ok((time_1 - time_0) > 50 * time.millisecond);

    timer.reset();
    for ([_]u8 {0} ** 10) |_| {
        debug.warn("lap = {}\n", .{ timer.lap() });
    }
}

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

はじめに

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

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

どんな型でも比較できる便利な奴ら、genericを紹介します。

std.generic.equal

2つの引数、a, b が一致しているかどうかをブール値で返します。 この関数は任意の型に対して使用できますが、abとは同じ型でなければなりません。

型パラメータが不要なので、とっても便利です。

///Compares two of any type for equality. Containers are compared on a field-by-field basis,
/// where possible. Pointers are not followed.
pub fn equal(a: var, b: @TypeOf(a)) bool

利用例です。 整数型だろうが、配列だろうが、構造体だろうが、型だろうが、雑に突っ込めば善きに計らってくれます。

test "generic equal" {
    // integer
    testing.ok(generic.equal(10, 10));
    // floating point
    testing.ok(generic.equal(5.7, 5.7));
    // slice []const u8
    testing.ok(generic.equal("hello"[0..], "hello"[0..]));
    // type
    testing.ok(generic.equal(usize, usize));

    var a: usize = 10;
    // pointer
    testing.ok(generic.equal(&a, &a));

    const S = struct {
        a: u32 = 10,
        b: f64 = 5.7,
        c: []const u8 = "hello"[0..],
    };
    // struct
    testing.ok(generic.equal(S{}, S{}));

    const RefS = struct {
        ptr: *S,
    };
    // `s1` と `s2` は同じ値を持つ
    var s1 = S{};
    var s2 = S{};
    const ref_s1 = RefS{ .ptr = &s1 };
    const ref_s2 = RefS{ .ptr = &s2 };
    // Pointer is not followed.
    testing.ok(!generic.equal(ref_s1, ref_s2));
}

ただし、最後に示しているように、ポインタの指し先の値が一致しているかどうか、までは見てくれません。

std.generic.lessThan

a < bであるかどうかをブール値で返します。 equalと大体同じです。

///Compares two of any type for a lessThan order. Containers are compared on a field-by-field basis,
/// where possible. Pointers are not followed.
pub fn lessThan(a: var, b: @TypeOf(a)) bool

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

はじめに

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

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

MarkdownをパースしてHTML出力します。

std.markdown

適当なMarkdownを用意して、parse関数を呼び出します。

const std = @import("std");
const heap = std.heap;
const fs = std.fs;
const io = std.io;
const markdown = std.markdown;

pub fn main() anyerror!void {
    const in =
\\ # Subject
\\
\\- one
\\- two
\\
\\```zen
\\ pub fn main() void {
\\    
\\}
\\```
;

    var alloc_bytes: [1024 * 4]u8 = undefined;
    var out_bytes: [1024]u8 = undefined;
    var stdout = try fs.getStdOut();
    var fba = heap.FixedBufferAllocator{ .buffer = &alloc_bytes };

    try markdown.parse(&fba, in, &stdout, markdown.renderHtml(fs.File.WriteError));
}

parse関数は次のようなAPIになっています。

pub fn parse(allocator: heap.Allocator, text: []const u8, callback_ctx: var, callback: var) !void

callbackは次の関数シグネチャを満たす関数ポインタであることが期待されています。

fn func(out_stream: *vtable io.OutStream(E), res: Result) E!void

callback_ctxは自然と、io.OutStream(E)を満たすことが求められます。

markdown.renderHtml(fs.File.WriteError)はそのような関数ポインタを返す関数になっています。

実行結果を見てみましょう。

$ zen build run
<h1>Subject</h1>
<ul>
<li><p>one</p>
</li>
<li><p>two</p>
</li>
</ul>
<pre><code class="language-zen"> pub fn main() void {
    
}
</code></pre>

ちゃんとHTMLが出力されていますね!

Zen言語の標準ライブラリ紹介〜コンソール出力の着色〜

はじめに

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

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

用事していたら時間なくなったので、くっそしょーもないやつを1つ紹介してお茶を濁します。

std.fmt.setTtyColor

コンソールに出力する文字の色を設定します。

下でプロジェクトを作成し、

$ zen init-exe

src/main.zenを次の通り編集します。

const std = @import("std");
const fs = std.fs;
const fmt = std.fmt;
const debug = std.debug;

pub fn main() anyerror!void {
    const stderr = try fs.getStdErr();
    try fmt.setTtyColor(stderr, .Red);
    try stderr.write("Red\n");
    debug.warn("RED warning!\n", .{});
}

文字が赤くなります。やったね!

f:id:tomo-wait-for-it-yuki:20200220215146p:plain

文字色は、次から選べます。

pub const TtyColor = enum {
    Red,
    Green,
    Yellow,
    Blue,
    Cyan,
    White,
    Dim,
    Bold,
    Reset,
};

標準出力を着色したければ、標準出力のファイルを取得して下さい。

    const stdout = try fs.getStdOut();

Zen言語の標準ライブラリ紹介〜排他制御①〜

はじめに

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

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

排他制御系も色々揃ってございます。 ①としましたが、②があるかどうかは、私の気分次第です。

本記事では、基本のatomic Integerとスピンロックをやります。

std.atomic.Int

整数のアトミック操作を保証します。 プリミティブにやるのであれば、組込み関数のatomicLoad, @atomicStore, @atomicRmwなどを使います。

get(), set(), incr(), decr(), xchg()とか、一通りあります。 内部的には上述の組込み関数を呼び出しているだけです。

test "atomic Int" {
    var count = atomic.Int(usize).init(0);
    testing.ok(count.get() == 0);

    // 前の値が返ってくる
    testing.ok(count.incr() == 0);
    testing.ok(count.get() == 1);

    // 前の値が返ってくる
    testing.ok(count.decr() == 1);
    testing.ok(count.get() == 0);

    count.set(10);
    testing.ok(count.get() == 10);

    // 前の値が返ってくる
    testing.ok(count.xchg(5) == 10);
    testing.ok(count.get() == 5);

    // 前の値が返ってくる
    testing.ok(count.fetchAdd(5) == 5);
    testing.ok(count.get() == 10);
}

ターゲットアーキテクチャがアトミック操作を提供するビット幅であれば、任意の整数型に対して使用できます。 x86_64では、8, 16, 32, 64, 128ビット幅の整数ならOKです。

test "atomic arbitary Int" {
    var count = atomic.Int(u8).init(0);
    testing.ok(count.get() == 0);

    // ダメ!8以上の2の累乗ビットじゃないと
    // var count = atomic.Int(u11).init(0);
    // testing.ok(count.get() == 0);

    // ダメ!128ビットまで
    // var count = atomic.Int(u256).init(0);
    // testing.ok(count.get() == 0);
}

std.threading.SpinLock

スピンロックです。 ロックはブロック内で取得して、deferでリリースしましょう。

acquire()はロックが取得できるまでループします。 tryAcquire()はロックが取得できなければ、nullが返ってきます。

const SpinLock = std.threading.SpinLock;
test "SpinLock" {
    var lock = SpinLock.init();
    defer lock.deinit();

    {
        const held = lock.acquire();
        defer held.release();
        testing.ok(lock.tryAcquire() == null);
    }

    if (lock.tryAcquire()) |held| {
        defer held.release();
        // critical section
    } else unreachable;
}