範囲内包表記

前回範囲について書いて以来、私は忙しい。私はたくさん持っています 共有するニュースの数ですが、この投稿では、私が非常に興奮している最近の開発に焦点を絞ります.これは私が範囲内包表記と呼んでいる新機能です 、カスタム範囲を作成するビジネスを大幅に簡素化することを約束します.

リスト内包表記

Haskell や Python のリスト内包表記に精通している場合は、「範囲内包表記」という言葉に耳を傾けたかもしれません。リスト内包表記を使用すると、既存のリストから新しいリストを簡単に生成できます。たとえば、nm を変換したり、フィルター処理したり、組み合わせたりすることができます。たとえば、最初の 10 個のピタゴラスのトリプルを生成する Haskell プログラムは次のとおりです。

main = print (take 10 triples)

triples = [(x, y, z) | z <- [1..]
                     , x <- [1..z]
                     , y <- [x..z]
                     , x^2 + y^2 == z^2]

triples の読み方 行はこれです:タプルのリストを生成します (x, y, z) どこで z 1 から無限大まで、x 1 から z まで (包括的)、および y x から z まで 、ただし x^2 + y^2 == z^2 のトリプルのみを生成します 本当です。次に、コードは x のすべての組み合わせを生成します 、 y 、および z 指定された範囲をある順序で並べてフィルタリングし、ピタゴラスのトリプルのリストを生成します。美しい。特に興味深いのは、Haskell は怠惰であるため、無限リストを生成する内包表記に問題がないという事実です。

裏話

10 月に、API 設計と std::getline に関するブログ投稿を公開しました。 その中で、範囲ベースのインターフェースが既存のものより優れていることを示しました。私の友人である Bartosz Milewski は、範囲を扱うのは難しいとコメントし、上記の簡潔な Haskell プログラムの範囲ベースの同等物を示すように私に挑戦しました。当時、私はバルトシュに対して何の答えも持っていなかったことを認めます.

最近、Bartosz がこの問題についてのブログ投稿を公開しました。 Bartosz は彼の投稿で、圏論からの非常に単純な結果について説明しています (もし 圏論は「単純」と表現できます)、C++ でピタゴラスのトリプルを遅延生成する問題にそれを適用します。素晴らしい投稿です。ぜひお読みください。ここに、最終的に、私の答えがありました。 Bartosz のコードは非常に非効率的で、推論がやや難しく、STL 風の概念で定式化されていませんでしたが、私は自分が取るべき方向性を知っていました.

範囲内包表記の紹介

これ以上苦労することなく、これがピタゴラスのトリプル問題に対する私の解決策です:

using namespace ranges;

// Lazy ranges for generating integer sequences
auto const intsFrom = view::iota;
auto const ints = [=](int i, int j)
    {
        return view::take(intsFrom(i), j-i+1);
    };

// Define an infinite range of all the Pythagorean
// triples:
auto triples =
    view::for_each(intsFrom(1), [](int z)
    {
        return view::for_each(ints(1, z), [=](int x)
        {
            return view::for_each(ints(x, z), [=](int y)
            {
                return yield_if(x*x + y*y == z*z,
                    std::make_tuple(x, y, z));
            });
        });
    });

// Display the first 10 triples
for(auto triple : triples | view::take(10))
{
    std::cout << '('
        << std::get<0>(triple) << ','
        << std::get<1>(triple) << ','
        << std::get<2>(triple) << ')' << '\n';
}

4行目と5行目は intsFrom を定義しています と ints 、整数のシーケンスを生成するための遅延範囲です。 triples の定義がある 12 行目までは面白くありません .それが範囲理解です。 view::for_each を使用しています そして yield_if すべてのピタゴラス数の遅延範囲を定義します。

view::for_each

view::for_each とは ? std::for_each のように 、その範囲内の各要素で動作する範囲と関数を取ります。しかし view::for_each 怠惰です。別の範囲を返します。 view::for_each に渡す関数 また、範囲を返す必要があります。まだ混乱していますか?

非常に多くの範囲がありますが、何が起こっているのでしょうか?概念的には、それほど難しいことではありません。 view::for_each を呼び出すとしましょう 範囲 {1,2,3} で および関数 f(x) 範囲 {x,x*x} を返します .結果の範囲は次の要素で構成されます:{1,1,2,4,3,9} .パターンが見えますか? f によって返される範囲 すべて平らになりました。本当に、範囲の平坦化がすべてです。

上記の 12 行目をもう一度見てください。

auto triples =
    view::for_each(intsFrom(1), [](int z)
    {
        return view::for_each(ints(1, z), [=](int x)
        {
            return view::for_each(ints(x, z), [=](int y)
            {
                return yield_if(x*x + y*y == z*z,
                    std::make_tuple(x, y, z));
            });
        });
    });

整数 z ごとに 1 から無限大の範囲では、view::for_each を呼び出します (これは平坦化された範囲を返すことを思い出してください)。内側の view::for_each すべての整数 x で動作します 1 から z まで z をキャプチャするラムダを呼び出します 値によって。 それ 関数は3番目の結果を返します view::for_each の呼び出し .最終的に x を持つその最も内側のラムダ 、 yz 、挑発的な名前のyield_ifという不思議な見た目の関数を呼び出します .それは何ですか?

yield_if

yield_if のセマンティクス タプル (x,y,z) を「注入」することです ただし、 がピタゴラスのトリプルである場合に限ります。難しそうに見えますが、実はとてもシンプルです。関数が view::for_each に渡されたことを思い出してください。 範囲を返す必要があります。したがって、yield_if 範囲を返す必要があります。条件 x*x + y*y == z*z の場合 が false の場合、空の範囲を返します。 true の場合、1 つの要素を含む範囲を返します:(x,y,z) .私が言ったように、単純です。 yield という関数もあります 無条件に単一要素の範囲を返します。

それがどのように機能するかがわかったので、それを忘れることができます。 view::for_each を使用できます と yield_if yield を呼び出したときに自身をサスペンドするステートフル関数を書いているかのように または yield_if 、コルーチンのようなものです。結局、yield を連想させるために「yield」という名前を選びました C# のキーワード。そのキーワードは、まさにそれらのコルーチン風のセマンティクスに現れる機能を提供します。さらに、yield を持つ C# 関数 ステートメントは C# の IEnumerable を自動的に実装します インターフェース。 IEnumerable 以前の投稿で説明した Iterable の概念と同じニッチを満たします。つまり、要素をループできます。

たとえば、C# では次のことができます (ウィキペディアから引用):

// Method that takes an iterable input (possibly an
//  array) and returns all even numbers.
public static IEnumerable<int>
GetEven(IEnumerable<int> numbers) {
    foreach(int i in numbers) {
        if((i % 2) == 0) {
            yield return i;
        }
    }
}

範囲内包表記を使用すると、同等のコードは次のようになります:

auto GetEvens =
    view::for_each(numbers, [](int i)
    {
        return yield_if((i % 2) == 0, i);
    });

これはほとんど同じことであり、特別なキーワードやコンパイラ マジックは必要ありません。

パフォーマンス

範囲を返す範囲 範囲を返す範囲、おいおい。実行時のパフォーマンスはどれほどひどいものですか?結局のところ、まったく恐ろしいことではありませんが、オプティマイザがどれだけ優れているかに大きく依存しています。

最初の 3000 個のトリプルを反復処理し、それらを使って簡単な計算を行う単純なベンチマーク プログラムを作成しました。私はこれを2つの方法で行います。 1 つは上記の範囲内包表記を使用したもので、もう 1 つはこの 3 重にネストされた for を使用したものです。 ループ:

for(int z = 1;; ++z)
{
    for(int x = 1; x <= z; ++x)
    {
        for(int y = x; y <= z; ++y)
        {
            if(x*x + y*y == z*z)
            {
                result += (x + y + z);
                ++found;
                if(found == 3000)
                    goto done;
            }
        }
    }
}
done:    

このソリューションは飛行し、範囲ベースのソリューションは這うことを期待するでしょう。しかし、ここでは -O3 で最新の gcc-4.9 を使用した数値を示します。 :

Raw loop:             2.2s
Range comprehension:  2.3s

それだけ?! はい、範囲内包表記によって行われるすべての余分な作業は、最適に近いコードを生成するオプティマイザーに対して完全に透過的です。すごいですね。

ただし、選択したコンパイラが clang である場合は、悪いニュースがあります。範囲理解は (待って) 15 倍遅い .神様、それはひどいです。これは、ほとんどの点で clang の驚異的な素晴らしさにもかかわらず、そのオプティマイザーにはまだ改善の余地があることを示していると思います.

まとめ

Haskell と Python にはリスト内包表記があります。 C# には LINQ と yield があります .そして今、C++ には範囲内包表記があります。すべての STL アルゴリズムで適切に機能する方法で、重要なシーケンスをオンザフライで遅延して効率的に生成することは、今では非常に簡単です。私が言ったように、私はとても興奮しています.

謝辞

Bartosz Milewski に 90% の道のりを歩ませてくれたことに深く感謝します。彼の洞察と、それ以前のすべての関数型プログラマーと圏理論家の洞察がなければ、私はこれを行うことができませんでした。数学 FTW!

"\e"
"\e"
"\e"