抽象化されたアルゴリズムに見るプログラミングの面白さ

はじめに

みなさんプログラミング楽しんでますか？

作業的であったり、自分がやりたいことではなかったりすると面白くないことがあるかもしれませんが、日ごろ使う関数1つにも見出せる「プログラミングの面白さ」というテーマで1つ記事を書きたいと思った次第です。

そこで今回は、C++などの言語に見られるいわゆる「テンプレート」の機能を使い、プログラムの基礎であり重要な要素である「ソート」を抽象化して扱えるようにしたD言語の例をご紹介します。

何でも抽象化すれば良いというものでもありませんが、他の言語ではちょっと苦戦するロジックもあったりするので、これを見て少しでもプログラミング面白い！と思ってもらえれば幸いです！

前置き

以下、処理では基本的なテンプレートの機能に加え、ある程度D言語の「Range」の概念が必要な内容となっています。

Rangeにあまり馴染みがない方は、配列よりもう少し抽象度が高く、イテレーターとか呼ばれるものから更に一歩拡張したものだと思ってください。

公式のガイドや過去のわかりやすいアドベントカレンダー記事がありますので、不明なことがあれば下記のリンクも参照してみてください。

• DLang Tour（日本語）
  • https://tour.dlang.org/tour/ja/basics/templates
  • https://tour.dlang.org/tour/ja/basics/ranges
  • https://tour.dlang.org/tour/ja/gems/range-algorithms
• C++プログラマにお届けしたいD言語のテンプレート
  • https://qiita.com/k3_kaimu/items/5b2e0232cb94a42da6ae
• D言語で今始めるRange
  • https://qiita.com/umarider/items/e0936c6afdcdf4522cc7

sort

というわけで、最も単純な sort 関数を使ったちょっと珍しい例をいくつか紹介していきます。

基礎

まずはsort 関数の使い方をおさらいしておきます。
といっても std.algorithm モジュールで提供される普通の関数で、渡した配列を破壊的（インプレース）に並び替えし、昇順と降順を比較関数で切り替えたりできるよ、という程度です。

オンライン実行例 : https://run.dlang.io/is/blgAS8

import std.stdio;
import std.algorithm; // 使うときはこれをimport

int[] a = [9, 7, 1, 0, 4, 5, 8, 2, 6, 3];

// 昇順でソート
sort(a);
writeln(a); // [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

// 比較関数を指定して降順でソート
sort!"a > b"(a);
writeln(a); // [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

// SwapStrategyを指定して安定ソート
sort!("a < b", SwapStrategy.stable)(a);
writeln(a); // [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

補足

見慣れないとテンプレート引数の "a > b" というのが違和感あるかもしれません。
これは内部的にmixinの機能を使い、 a と b という2つの引数を受け取る関数として解釈されています。

以下のようにラムダ式を渡しているのと同じ動作ですが、記述量を減らすなどのメリットがあるので文字列指定をサポートしている感じです。

ラムダ式で指定

sort!((a, b) => a > b)(a);

以下、比較関数を使うときは文字数削減のために文字列指定で書いていきます。

また、UFCS（統一関数呼び出し構文）という方法を使えば、以下のように引数のメンバー関数のように使うこともできます。

UFCSを使う場合

// 同じ意味
sort(a);
a.sort();

// 同じ意味
sort!("a < b", SwapStrategy.stable)(a);
a.sort!("a < b", SwapStrategy.stable)();
a.sort!((a, b) => a < b, SwapStrategy.stable)();

他の多くの言語ではソートが配列オブジェクトのメソッドとして提供されたりするので、見た目が直観的なのはこちらかもしれません。

が、あくまでもアルゴリズムを抽象化した普通の「関数」であることを強調したいので、以降はあえて通常の関数呼び出し形式で記載しておきます。

解説

sort 関数はテンプレートで実装されていて、テンプレートパラメーターで挙動を操作します。
たとえば第1引数が比較関数、第2引数が安定/不安定を指定するフラグ、という感じです。

シグネチャは少しボリュームがあるものの、分解して整形すると以下のようになります。

sort 関数のシグネチャ : https://dlang.org/phobos/std_algorithm_sorting.html#.sort

// 戻り値と関数名
SortedRange!(Range, less) sort(
    // テンプレートパラメーター
    alias less = "a < b",
    SwapStrategy ss = SwapStrategy.unstable,
    Range
)(
    // 引数
    Range r
)
// テンプレート制約
if (
    (
        ss == SwapStrategy.unstable && (hasSwappableElements!Range || hasAssignableElements!Range) 
        || ss != SwapStrategy.unstable && hasAssignableElements!Range
    )
    && isRandomAccessRange!Range
    && hasSlicing!Range
    && hasLength!Range);

細かいところは省略しますが、戻り値はソート済みを表すRangeで、引数は配列に限りません。

引数の型がいくつかの制約によって縛られている、といったあたりが大きな特徴でしょうか

条件の部分をざっくり読めば、値が入れ替えまたは代入可能、ランダムアクセスが可能、スライスが取れる、lengthプロパティがある、といった性質を求めています。

ポイント

この sort 関数のシグネチャの重要な点は、**「これらの性質を満たしてさえいれば、どんなものでもソートしてみせよう！」**という強力な抽象化です。

どのくらいソートできるのか、ちょっと試してみたいですね…？

sort + chain

配列がソートできるだけではあまりに普通なので、Rangeの強みを見るために少し変わったソートをしてみます。

まずはわかりやすいところで、D言語の学習資料である DLang Tour のトップにあるサンプルから抜粋です。
DLang Tour(日本語) : https://tour.dlang.org/tour/ja/welcome/welcome-to-d

これはずばり「複数の配列をつなげてソートする」というものです。

オンライン実行例 : https://run.dlang.io/is/QjprKH

ソースコード

// 3つの配列を取り、新しいメモリ割り当てなしで、
// インプレースですべての配列をソート
int[] arr1 = [4, 9, 7];
int[] arr2 = [5, 2, 1, 10];
int[] arr3 = [6, 8, 3];
sort(chain(arr1, arr2, arr3));
writefln("%s\n%s\n%s\n", arr1, arr2, arr3);

実行結果

[1, 2, 3]
[4, 5, 6, 7]
[8, 9, 10]

解説

ここでは std.range にある、複数のRangeをつなげて1つのRangeを作る chain という関数を使っています。
配列もRangeなので、これらを1つのRangeにまとめてしてしまえばソートするだけですね。簡単！

結果として、用意した配列の長さなどはまったく変わらず、中身だけが書き換わっていることがわかります。
まったく関係のない複数配列間で要素が入れ替えられているのがちょっと面白いですね！

また chain も sort も一切GCが働かず、特別なメモリ割り当ても起こらないという特性があります。
新しい配列にコピーしてソートしているわけでもないので、中では何かすごいことになっていそうですね…

と、どちらかといえばすごいのは chain の方かもしれません。
もし仕組みが気になった方は以下を参照してみてください。

ドキュメント : https://dlang.org/phobos/std_range.html#chain
実装 : https://github.com/dlang/phobos/blob/master/std/range/package.d#L893

参考

個人的にこれを使った例としては、メタヒューリスティクスと呼ばれるタイプのアルゴリズムである「遺伝的アルゴリズム」の実装です。

これ自体は数十年前からある理論なのですが、アルゴリズムを簡単に説明すると、

1. たくさんの個体を用意して、それぞれを評価してスコアを付ける
2. 評価した個体を混ぜたりして新しい個体を一定数作る（交叉・変異）
3. 作った個体も評価してスコアを付ける
4. 元の個体と作った個体の中から次の世代の一覧を作って2に戻る（選択）

というステップを繰り返すことで、よりスコアが高い個体を作り出す、というものです。

生物の進化や遺伝の仕組みを参考としていて、問題の複雑さによらない計算量で近似解が求まるため色々な分野で利用されています。

特に交叉や選択のフェーズでは多様な手法があるのですが、この選択を行うときに chain と sort の組み合わせを知っているとすこーしだけ楽ができます。

イメージとしては、「元の個体の一覧」「作った個体の一覧」をそれぞれ適当な配列としてやると、それらに上記の chain と sort を適用してスコアの降順にするだけで「『元の個体の一覧』にスコアの高い個体が入る」という動作が非常に簡単に実装できます。

実際にコードとして書いてみると以下のようなイメージです。

struct Agent {
    float[] gene;
    float score;
}

auto basePool = new Agent[100]; // 元となる一覧
auto childPool = new Agent[100]; // 子世代の一覧

// basePoolをランダムに初期化してスコアを評価する
foreach (ref agent; basePool) {
    agent.randomize();
    agent.evaluate();
}
// 子世代の一覧を生成する
fillChildren(basePool, childPool);
// 子世代を評価する
foreach (ref agent; childPool) {
    agent.evaluate();
}

// スコアの降順に並び替える
sort!"a.score > b.score"(chain(basePool, childPool));

と、ここまでやりましたが、現実ではここまでやったあとに「全部を1つの配列に入れてスライスで区分けして扱えば良い」ということに気づくわけです。

auto pool = new Agent[100 + 100];
auto basePool = pool[0 .. 100];
auto childPool = pool[100 .. $];

// 初期化したり評価したり生成したり

// 単なる配列のソートなので、抽象的なRangeより高速で効率が良い
sort!"a.score > b.score"(pool);

実際に活用するには至りませんでしたが、実行時にあれこれ異なる配列に入れ替えて同じことをするときには有効ですので、そういうときに思い出したいですね。

こんな書き方もできるよ！ということで、他ではあまり見ないちょっと面白いソートの一例でした。

sort + zip

もう1つRangeのソートで例を挙げます。今度は std.range の zip と組み合わせます。

chain がRangeを直列につなぐのに対して、zipは横に並べるイメージになるでしょうか。
もっと言ってしまえば「インデックスを揃えて束ねてソートする」という感じです。

先の例よりは幾分実践的なので早速例を見ていきます。

オンライン実行例 : https://run.dlang.io/is/wZQbKb

ソースコード

import std.algorithm;
import std.range;

string[] a = ["Apple", "Banana", "Cookie", "Doughnut", "Egg"];
int[] b = [10, 4, 3, 7, 1];

sort!"a[1] < b[1]"(zip(a, b));

writeln(a);
writeln(b);

出力結果

["Egg", "Cookie", "Banana", "Doughnut", "Apple"]
[1, 3, 4, 7, 10]

解説

これは「食べ物の配列と数値が入った配列があり、食べ物を対応した数値に基づいてソートしたい」という要求を簡単に実現する例です。
配列の添え字毎に対応付けられたデータの一例ということで、数値に意味はないので読み流してください。

ポイントは「2つの配列が要素ごとに対応している」という部分で、これを1つの配列のように扱うために zip で束ねてしまおう、ということです。

結果を見ると配列 b が綺麗に昇順になるのに合わせて、配列 a が入れ替えられているのがわかります。

配列を2つ揃えて列挙できる、という言語は多いですが、2つ揃えてソートできる、という言語は結構稀だと思ったのでこちらを紹介してみました。¹

参考

これもまた遺伝的アルゴリズムの実装でなかなか使える手法です。

遺伝的アルゴリズムを無難に実装する場合、先の例のように「個体のデータとスコアをまとめた構造体」を作り、それを1つの配列に格納しておくことで簡単にソートできるようにすることが多いと思います。
（これは Array of Struct と呼ばれる自然な実装方法です）

しかし実際に実装が進んで機能が増えてくると、

• 個体の配列をテストデータで評価する
• スコアの分布を見て評価する

といった「個体のデータかスコアのいずれか一方の情報にしか用がない」というロジックが出てくることが多いです。

そういったロジックに受け渡すのは個体の配列やスコアの配列で十分なわけですが、前述の実装だと「管理のための構造体の配列しかない」という状況になります。

これを個々のロジックに「そのまま渡す」か「必要なデータだけ取り出して渡す」という加工の手間が発生するので、同じような機能が増えてくるとその分処理のオーバーヘッドにつながります。

コードに落とすと以下のような感じです。

struct Agent {
    float[] gene;
    float score;
}

// 手元にあるもの
Agent[] pool;

// 使いたい関数
void plotScore(float[] socres);

// 使うときに変換する手間がかかる
plotScore(pool.map!"a.score".array());

そこで今回扱った zip を活用すれば、別々に宣言して最適な実装をし、ソートのときに束ねれば良い、という選択が可能になります。
（ zip を使うことでソートに掛かるコストは増えるので、トレードオフとしてちゃんと計測すべきですが）

alias Gene = float[];
// Agentのリスト自体を構造体として定義する
struct AgentPool {
    // 添え字毎に対応づけたデータを持つ
    Gene[] genes;
    float[] scores;
}

AgentPool pool;

// ソートのときに zip で束ねる
sort!"a > b"(zip(pool.genes, pool.scores));

// 使いたい関数
void plotScore(float[] socres);

// 使うときのオーバーヘッドがない
plotScore(pool.scores);

ここまで抽象化されたソートアルゴリズムがない場合、上記のロジックを思いついたら最悪ソートを手書きすることになると思います。
それ自体は面白いと思うのですが、個人的にはパフォーマンスが気になったり、バグのリスクを考えると躊躇してしまう面があるのではないでしょうか？

こういった再利用性の高い汎用アルゴリズムがあれば、バグのリスクはほぼゼロに抑えられ、後から設計を変えることができるなど幾分柔軟な開発が可能になります。

まとめ

プログラミングにおける基礎でありとても身近なソートですが、日ごろ使っている関数でもちょっと面白いと思った使い方がある、という例をご紹介しました。

再利用可能なアルゴリズムというのは単なる品質の保証だけでなく、使う人を必要以上に縛らず、プログラムの構造を柔軟にする力があります。

仕事で安全なプログラムを書くということも当然重要ですが、多くのプログラミング言語に採用されるに至ったテンプレートやジェネリクスの機能がどういった課題を解決するのか、またその価値を広く知ってもらえれば幸いです。

というわけで、今後もロジックを抽象化する技術を磨き、便利な汎用的なライブラリを書けるように精進していきたいと思います！

プログラミングは面白いぞ！！！

1. たとえばC#はLinqにZipとOrderByがあるので、「束ねて並び替えた配列を得る」こと自体は容易です。しかしこれは「揃えてソートした結果を列挙して新しい配列を作る」という方法であり、今回の処理例とはかなり異なります。 ↩