Help us understand the problem. What is going on with this article?

RangeでもLINQがしたい!

More than 5 years have passed since last update.

D言語 Advent Calendar 2012の21日目の記事です。
D言語のRangeの事を軽くと、D言語でLINQをどう実現するかというお話をします。

Rangeって?

RangeというのはD言語で扱われるコレクションのこと。
コレクションの例としては、ListとかMapとかQueueとかあります。

D言語の場合、クラスや構造体に特定のメソッド・メンバを実装すればOKです。
Rangeには幾つかの種類があって、下の表の通りです。

Rangeの種類 説明
InputRange empty、front、popFrontが実装されてる
OutputRange putが実装されてる
ForwardRange InputRange+saveが実装されてる
BidirectionalRange ForwardRange+back、popBackが実装されてる
RandomAccessRange BidirectionalRange+length、opIndexが実装されている

最低でもInputRangeとして実装されていればforeachで回す事ができます。
また、std.rangeをincludeすればisXXXXRangeでコンパイル時に各種Rangeの条件を満たしてるかコンパイル時に判別してくれます。

他にも色々判別出来て、isInfinitで無限リストかどうかとか、hasSlicingでスライシング(range[3..5]みたいなの)が提供されているか判別してくれます。もちろん、全部コンパイル時に!

LINQって?

LINQっていうのはLanguage INtegrated Query(統合言語クエリ)の略です。
.NET Framework3.5から提供された機能の事で、C#やVisual Basicで色んなデータ構造に対して同じクエリでデータの操作を可能にしようっていう奴です。

扱うデータも、IEnumerable・IEnumerable<T>コレクションを扱うLINQ to Objects、XMLを扱うLINQ to XML、RDBを扱うLINQ to SQLやLINQ to Entities等々色々あります。
変わり種として非同期やイベントの操作を行うReactive Extensionsなんてなんてものもあったり。
LINQってO/Rマッパーなのでは、とか言われるのですがO/RマッパーなはあくまでLINQのほんの一部なのです。

では、そのLINQの特徴を以下に軽く。

2つの記述方法

LINQにはクエリ記法とメソッドチェイン記法があります。
以下に1〜100の中から偶数の数字の二乗の値を取り出す操作を2つの記法で書きます。

LINQの記法
// クエリ記法
var query = from x in Enumerable.Range(1, 100)
            where x % 2 == 0
            select x * x;

// メソッドチェイン記法
var methodChain = Enumerable.Range(1, 100).Where(x => x % 2 == 0).Select(x => x * x);

統一的な操作

LINQ to ObjectsやLINQ to XML、LINQ to SQLやLINQ to Entities等など、扱うデータの種類は色々あります。

だけど、Whereだと記載した条件のものだけ取り出すし、Selectだとコレクションの要素から好きな形式に整形して出力するし、Countだと要素の数を数えるし、OrderByならソートするし、GroupByなら特定の要素でグループ分けしてくれます。

扱うデータが変われど、LINQで目的のデータを扱うやり方が統一されることで、覚えることが少なくて済むし、いちいちリファレンス調べなくてよくなります。

遅延評価

LINQは、LINQで記載したデータに対しその要素にアクセスしようとしない限りデータへの操作を行わない様に実装されています。

上記の記載例だと、queryやmethodChainの箇所ではまだ偶数の判別やxの二乗計算は行われてません。
queryやmethodChainの最初の要素にアクセスしたり、 foreachで各要素を取得したりした時に、初めて判別や計算が実行されます。

RangeでLINQしよう!

先ほど挙げた通り、コレクションに関してはRangeがあります。
クエリ記法は流石にコンパイラ自体のサポートがいるので無理ですが、メソッドチェイン記法ならば2.059で使えるようになったUFCSで可能になります。
他にも、D言語にはラムダ式があったりと実装しやすそうなので、LINQ to Rangeをやってみようかなと思ったのです。

というか、JavaScriptでのLINQ実装であるlinq.jsのリファレンスとかコード見ながらD言語に落とし込んだ感じです。

例としてwhereのコードを以下に。

LINQ_to_Rangeのwhere
template where(alias pred) if (is(typeof(unaryFun!pred)))
{
    auto where(Range)(Range r) if (isInputRange!(Unqual!Range))
    {
        return WhereRange!(unaryFun!pred, Range)(r);
    }
}

private struct WhereRange(alias pred, Range)
{
    alias Unqual!Range R;
    R _prevSource;
    bool _isAccess;

    // コンストラクタ
    this(R r)
    {
        _prevSource = r;
        _isAccess = false;
    }

    // empty(空かどうか)の提供
    static if (isInfinite!Range)
    {
        enum bool empty = false;
    }
    else
    {
        @property bool empty() { return _prevSource.any!(pred); }
    }

    // 一番最初の要素に移動(1回目だけ)
    private void popFirst()
    {
        if(!_isAccess)
        {
            while(!_prevSource.empty && !pred(_prevSource.front))
            {
                _prevSource.popFront();
            }
            _isAccess = true;
        }
    }

    // popFront(取り出す要素を前に一つ先に移動)の提供
    void popFront()
    {
        this.popFirst();
        do
        {
            _prevSource.popFront();
        }while(!_prevSource.empty && !pred(_prevSource.front));
    }

    // front(要素の取得)の提供
    @property auto ref front()
    {
        this.popFirst();
        return _prevSource.front;
    }

    // whereの連打を提供
    public auto where(alias newPred)()
    if (is(typeof(unaryFun!newPred)))
    {
        return WhereRange!(delegate bool(typeof(_prevSource.front) x) { return unaryFun!newPred(x) && pred(x);}, Range)(_prevSource);   
    }
}

std.algorithmを見たりしながら実装しました。
std.algorithmのfilterとほぼ同じ機能なのですが、あっちはfilter用の構造体を作成する際にpredの判定とか実行するので、それも遅延させてみました。

あと、WhereRangeにwhereメソッドがあるのを見て分かる通り、whereにwhereを繋げても、それぞれのpredの論理積の式からWhereRangeを作るので、whereを何回も繋げる、みたいなよくやる書き方をしてもパフォーマンスに影響がありません。
これもlinq.jsや元々のLINQで同じ様になっています。

その他にこんなのを実装してみました。

実装した機能 説明
any!(pred,Range)(Range r) Rangeに要素があるかどうか判定する。predを書けばその条件を満たす要素があるか分かる。
count!(Range)(Range r) Rnageにいくつ要素があるか数える。
skip!(Range)(Range r, size_t count) Rangeの要素の頭count個を飛ばしたRangeを取得する。
chois!(Range)(Range r) Rangeの中からランダムで要素を取り出す。
selectMany!(pred, Range)(Range r) Rangeの各要素を一つのRangeに射影して平坦化する。

selectManyについてはよく分からないと思います。図解 SelectManyが図が載ってて分かりやすいので、こちらを見ていただければいいかなと。

LINQにはまだまだいろんな操作があって、linq.jsのリファレンスページのように色々あります。
.Net Framework側のLIQN to Objectsの一覧は「LINQの拡張メソッド一覧と、ほぼ全部のサンプルを作ってみました。(地平線に行く)」が分かりやすいです。

私、気になります!

では最後に、千反田えるを上記のLINQ to Rangeとstd.rangeとstd.algorithmを使って求めてみます。

千反田えるを求める
import std.stdio;
import std.algorithm;
import std.range;
import linq;    //LINQ to Rangeを実装してるモジュール

void main()
{
    0.iota(1000).map!(n => (a => a[3].repeat.selectMany!"a".skip(n+1).front ~ a[2].repeat.selectMany!"a".skip(n+1).front ~ a[1].repeat.selectMany!"a".skip(n+1).front ~ a[0].repeat.selectMany!"a".skip(n+1).front ~ "反田" ~ ["えー","びー","しー","でぃー","いー","えふ","じー","えいち","あい","じぇー","けー","える","えむ","えぬ","おー","ぴー","きゅー","あーる","えす","てぃー","ゆー","ぶい","だぶる","えっくす","わい","ぜっと"].cycle.skip(n).front)(["", "十", "百","千"].map!(x => ["", "一", "二", "三", "四", "五", "六", "七", "八", "九"].map!(y => ((x!="" && y=="一")? "" : y) ~ ((x!="" && y=="")? "" : x))).map!(x => x.map!(y => y.repeat.take(10 ^^ ["一", "十", "百","千"].countUntil(x.skip(1).front))).selectMany!(x => x)))).skip(1000-1).front.writeln; // 千反田える
}

中途半端極まりねぇぇぇええええええ! (遅延とか諸々)
selectとかrepeatとかcylceとかzip(2つの配列を同時に回しながらselectする操作)とか実装する時間がなかった……orz。
std.rangeとstd.algorithmを使ってるのは、元からあるmapやrepoeatやcycleである程度は代用出来るので、それを使ってなんとか作りました。
特にzipがあれば1〜1000の数字配列(0.iota(1000)の所)からn反田コレクション(0<n<=1000)を作成しなくてもいいのですが……
なんで俺zip先に実装せんかったんや……

次回予告

というわけで、RangeとLINQに関する説明と、LINQ to Rangeの説明をしました。
LINQ to Rangeだけでなく、D言語でJSONやXMLに対してもLINQ出来たりするとより面白いですね。

次回の22日目は@mono_shooさんです。一足早いですが誕生日おめでとうございます!

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした