5

簡単なコードは次のとおりです。

import std.algorithm;
import std.array;
import std.file;

void main(string[] args)
{
    auto t = args[1].readText()
        .splitter('\n')
        .split("---")
    ;
}

動作するように見えますが、コンパイルされません。DMD 2.068.2 は次のエラーで失敗します。

Error: template std.algorithm.iteration.splitter cannot deduce function from
argument types !()(Result, string), candidates are:
...
Error: template instance std.array.split!(Result, string) error instantiating

.array前に挿入するとコンパイルされます.split。

何か不足していますか？それともバグですか？バグトラッカーで簡単な検索を試みましたが、何も見つかりませんでした。

4

1 に答える 1

19

結論: このような問題は、多くの場合.array、問題のある関数の直前に呼び出しを固定することで修正できます。これにより、アルゴリズムを実行するのに十分な機能を備えたバッファーが提供されます。

以下は、ライブラリの背後にある理由と、これを実装するために使用できる他のいくつかのアイデアです。

これがコンパイルされない理由は、std.algorithm と範囲の背後にある哲学と関係があります。つまり、コストの決定をトップレベルに押し上げるために、それらは可能な限り安価であるということです。

std.algorithm (および最も適切に記述された範囲と範囲を使用するアルゴリズム) では、テンプレートの制約は、必要なものを無料で提供しない入力を拒否します。同様に、フィルター、スプリッターなどの変換範囲は、最小限のコストで提供できる機能のみを返します。

コンパイル時にそれらを拒否することにより、プログラマーはそれらのコストをどのように支払うかについて最高レベルで決定する必要があります。関数を書き直して別の方法で動作させるか、コストを前払いするためのさまざまな手法を使用して自分でバッファリングするか、または他の動作するものを見つけることができます。

したがって、コードで何が起こるかは次のとおりreadTextです。ほぼフル機能の範囲である配列を返します。(UTF-8 で作成された を返すためstring、Phobos に関する限り、実際にはランダム アクセスを提供しません (ただし、紛らわしいことに、言語自体はそれを別の方法で認識しています。D フォーラムで「自動デコード」論争を検索してください詳細を知りたい) 可変長の utf-8 文字のリストで Unicode コード ポイントを見つけるには、すべてをスキャンする必要があるため. すべてをスキャンするのは最小限のコストではないため、特に要求しない限り、Phobos はそれを試みません.)

とにかく、必要な保存性readTextを含む多くの機能を備えた範囲を返しsplitterます。なぜsplitter節約が必要なの？それが約束する結果を考えてみましょう: 最後の分割ポイントから始まり、次の分割ポイントまで続く文字列の範囲。安価にできる最も一般的な範囲でこれを書くと、実装はどのようになりますか?

これらの線に沿った何か：最初に、save後で戻すことができるように開始位置。次に、 を使用してpopFront、分割点が見つかるまで進みます。その場合、保存された範囲を分割点のポイントまで戻します。次に、popFront分割点を過ぎて、すべてを消費するまでプロセスを繰り返します ( while(!input.empty))。

splitterということで、 の実装には出発点までの​​能力が必要だったのでsave、少なくとも前方範囲 (これは保存可能な範囲です) が必要です。アンドレイは今、名前がたくさんあるので、このような名前付けは少しばかげていると感じていますが、当時は彼は書いていましたがstd.algorithm、彼はまだそれらにすべての名前を付けることを信じていました)。

すべての範囲が前方範囲であるとは限りません! 配列は、現在の位置からスライスを返すのと同じくらい簡単に保存できます。多くの数値アルゴリズムも同様です。それらを保存することは、現在の状態のコピーを保持することを意味します。ほとんどの変換範囲は、変換している範囲が保存可能であれば保存可能です。繰り返しますが、必要なのは現在の状態を返すことだけです。

...私がこれを書いているとき、実際には、あなたの例は保存可能であるべきだと思います. 実際、述語を取ってコンパイルするオーバーロードがあります。

http://dlang.org/phobos/std_algorithm_iteration.html#.splitter.3

    import std.algorithm;
    import std.array;
    import std.stdio;

    void main(string[] args)
    {
            auto t = "foo\n---\nbar"
                    .splitter('\n')
                    .filter!(e => e.length)
                    .splitter!(a => a == "---")
            ;
            writeln(t);
    }

出力：[["foo"], ["bar"]]

はい、それは特定のものに等しい行でコンパイルおよび分割されました。もう 1 つのオーバーロード は.splitter("---")コンパイルに失敗します。そのオーバーロードにはスライス機能 (または Phobos が一般的にスライスすることを拒否する狭い文字列) が必要なためです。図書館の上。）

しかし、保存するだけでなく、スライスする必要があるのはなぜですか? 正直なところ、わかりません。多分私も何かを見逃しているかもしれませんが、機能するオーバーロードの存在は、アルゴリズムの私の概念が正しいことを意味します。このようにできます。スライスの方が少し安いと思いますが、保存バージョンも十分に安いです（スプリッターに到達するために過去にポップしたアイテムの数を数えてから戻ってきsaved.take(that_count)ます....おそらくそれが理由です：項目を 2 回反復し、1 回はアルゴリズムの内側に、次にもう 1 つは外側にあると、ライブラリはレベルを上げるのに十分なコストがかかると見なします (述語バージョンは、関数がスキャンを実行するため、Phobos はそれをもはや問題ではないと見なし、自分の関数が何をしているかを認識します。)

私はその論理を見ることができます。実際にもう一度轢かれるという決定はまだ外側にあるので、私は両方の方法で行くことができますが、考えずにそれを行うことが望ましくない理由を理解しています.

splitter最後に、出力のインデックス作成やスライスを提供しないのはなぜですか? なぜfilterそれも提供しないのですか？なぜmapそれを提供するのですか？

まあ、それは再びその低コストの哲学と関係があります. map実際には要素の数を変更しないため、それを提供できます (その入力がそうであると仮定します) map。出力の最初の要素は、結果に対して何らかの関数が実行されるだけで、入力の最初の要素でもあります。最後についても同様です。

filterしかし、それを変更します。[1,2,3] の奇数を除外すると、ちょうど [2] が得られます。長さが異なり、2 は途中ではなく最初に見つかります。しかし、実際にフィルターを適用するまで、それがどこにあるかを知ることはできません。結果をバッファリングせずに移動することはできません。

splitterフィルターに似ています。要素の配置が変更され、実際に要素を通過するまで、アルゴリズムはどこで分割されるかを知りません。したがって、反復するときにわかりますが、反復の前にはわかりません。そのため、インデックス作成はO(n)高速になり、計算コストが高すぎます。インデックス作成は非常に安価であると考えられています。

とにかく、原理がそこにある理由を理解したので、バッファリング (無料よりも多くのメモリを必要とする) や追加の反復 (コストがかからないよりも多くの CPU 時間を必要とする) などのコストのかかることについてエンドプログラマーが決定できるようにするためです。アルゴリズム)、そしてsplitterその実装について考えることによってなぜそれが必要なのかについていくつかの考えを持っているので、アルゴリズムを満たす方法を見ることができます: もう少し CPU サイクルを消費するバージョンを使用し、カスタム比較でそれを書く必要があります。関数 (上記のサンプルを参照)、または何らかの方法でスライスを提供します。最も簡単な方法は、結果を配列にバッファリングすることです。

import std.algorithm;
import std.array;
import std.file;

void main(string[] args)
{
    auto t = args[1].readText()
        .splitter('\n')
        .array // add an explicit buffering call, understanding this will cost us some memory and cpu time
        .split("---")
    ;
}

割り当てのコストを削減するために、ローカルにバッファリングするか、自分で何かをバッファリングすることもできますが、どのように実行しても、コストはどこかで支払う必要があり、Phobos は、プログラムのニーズを理解しているプログラマーを優先します。これらの費用を支払うかどうか、あなたに言わずにあなたに代わって支払うのではなく、その決定を下します。

于 2015-10-28T01:57:41.320 に答える