15

dataさまざまなパフォーマンスの問題を回避するために厳密なフィールドを含める必要がある多くの講演を見たり、ブログ投稿を読んだりしました。

data Person = Person
    { personName     :: !Text
    , personBirthday :: !UTCTime
    }

これは私にとって完全に理にかなっています。そのデータに対する関数操作は遅延するため、構成可能性は犠牲になりません。

しかし、Maybeフィールドを追加すると:

data Person = Person
    { personName     :: !Text
    , personBirthday :: !UTCTime
    , personAddress  :: !(Maybe Address)
    }

私はデータ構造に怠惰を導入しています。結局のところ、これMaybeは制御構造です。評価されていないサンクをJustコンストラクタの後ろに隠すことはできませんか?

ただし、厳密Maybeにはstrictor スルーがありstrict-base-typesます。しかし、逆の依存関係 ( strict、strict-base-types ) によると、それらは広く使用されていません。

Maybeでは、質問:非制御データ定義でstrict を使用する必要があるのはなぜですか?

4

2 に答える 2

3

「strict は速く、lazy は遅い」という単純なものではありません。

怠惰と厳格の両方がパフォーマンスの向上に役立ちます。怠惰がどのようになるか見てみましょう：

  • リストが厳密な場合は明らかsum $ take 10 $ [1..]に無限の時間と無限のメモリが必要ですが、リストが遅延している場合は有限の時間と一定のメモリが必要です。

  • 通常、関数データ構造は適切な償却境界を認めません。「償却された」バウンドとは何ですか? O( n ) の他の完全に無関係なステップの後にのみ O( f ( n ))のコストを支払う場合、これらのステップのそれぞれに対して O( f ( n )/ n )を支払うこととして、これを想像力で再概念化できます。たとえば、リストにn 個の要素を追加し、それをn log n時間で 1 回ソートすると、すべての追加に log n時間かかるように再概念化できます。(リストの代わりに自己平衡二分探索木でそれを裏付けると、それは起こりますが、私たちはそれを言うことができますリストを使用しても、コストは log n償却されます。)

    これを関数型プログラミングと組み合わせることの問題点は、新しいデータ構造を与えたときに、古いデータ構造は変更されないという一般的な約束があることです。次に、以前のように X を構築するためにn回の努力を費やすが、それをさまざまな方法でm回使用する有効な使用パターンが存在します (変更されていないため!) 毎回 O( f ( n )) のコストが発生します。償却しようとすると、O( m f ( n )/ n ) しか得られず、mがnに比例してスケーリングする場合、構造全体に対してこのコストが1回発生することから、基本的にデータ構造への追加ごとに1回発生するようになりました。データ構造を作成しているときに、「ああ、それは私のユース ケースではありません」とは言えません。

    Okasaki は (彼の論文 (PDF)で) 怠惰 (メモ化による) が実際にこのギャップを埋めるために必要なものであると指摘しています: Xが後処理されたバージョンを遅延値として格納していると仮定すると、 X を変換するたびに、同じ遅延値で、同じメモ化された回答が得られます。したがって、このようなものを巧みにサンクに移動できれば、Haskell がサンクを再計算しないという事実を利用して、メモ化の引数を作成できます。

  • 別の例として、++Haskell では O(1) 操作があります。厳密なリストでは、サイズmのリストの末尾にサイズnのリストを追加すると、フロント リストを完全に再構築する必要があるため、事前にO( m ) 個のメモリ割り当てが必要になります。ストリーム連結は、これを O( m ) 条件付き操作 (幸いなことに、プロセッサ内の分岐予測子と非常にうまく機能します!) に変換し、このコストをリストの読み取りごとに分散します。

  • 大量のデータを使用していない場合、怠惰には大きな可能性がありますが、使用しているものと使用していないものはわかりません。簡単な例を挙げると、有界区間で予測するのが難しい高価な単調関数を繰り返し逆変換する必要がある場合、逆関数の閉じた形式または関数またはその導関数の高速な式がない可能性があります ( Newton-Raphsonを使用します)。代わりに、ノードにf ( x ) の注釈が付けられ、葉がxを表す一定の深さの大きな二分探索ツリーを構築することができます。次に、f ( xを計算して、入力xのfを反転します。) およびxのバイナリ検索。各クエリは自動的にメモ化されるため、他の値に近い値を検索すると、同じキャッシュにより漸近的に高速化されます (メモリが増加し続けるという潜在的なコストがかかります)。

では、厳格さが役立つのはどのような場合でしょうか。

遅延を取り除きたい実際のケースは再帰的なデータ構造であり、その場合でも、データ構造全体をメモリで利用できるようにしたい (つまり、すべてを使用する) ことがわかっている場合にのみ適用されます。このようなデータ構造は、通常、スパイン厳密です。たとえば、実際の値のサンクを含むリストですが、他のリスト ノードへのポインタはすべて 100% 厳密です。

これらの条件が両方とも真の場合、これらのノードのそれぞれに遅延を設定しても意味がありません。これらのサンクをすべて評価するために追加の O( n ) コストが発生し、コール スタックが再帰制限まで爆破される可能性があるためです。それを抑えるために厳密性アノテーションを使用しないでください。これについて 100% 明確でない場合、これがどのように発生するかについて私が見た最良の説明は次のようなものであり、さまざまな理由で と の両方がコール スタックをオーバーフローする場合の必要性を正当化します。foldl'foldrfoldlこれらの説明は通常、非常に実用的です。

ゲームを作りたいときのように、厳格さは多くのコストを前払いすることもできます。しかし、これらのものを厳密に前もって生成できる場合は、早い段階でコストを支払う必要がありますが、後で利益を得ることができます。人々は「ゲームをロード」ボタンを押すのを待つことを気にしません。ストーリーへの没頭を中断するのを待つのは本当に嫌いです。(実際には、並列遅延はこれに最適です。必要になる前に、アクションが少し軽くなるまでバックグラウンドでサンクを強制できるようにして、必要な時間までに結果を利用できるようにする必要があります。しかし、つまり、それが TES3: Morrowind の仕組みでした。しかし、それらにはギャグとしてスクロールのセットが含まれており、着陸を生き残ることができれば、ゲームの世界の途中でジャンプすることができます。システムはそれらをロードできるため、この方法でゲームの世界を横切ると、「ロード中...」と言うために2回停止する前に、常に3秒間の空中飛行が行われます。その問題を実際に防ぐことはできません。)

修理が必要な場合、どのように修理すればよいですか?

つまり、典型的なMaybeどこかでは、アプリケーションにかなりのコストが発生しないことがわかりました。だから誰も気にしない。

data NonNullList x = NNL x !(Maybe (NonNullList x))常に少なくとも 1 つの要素を持たなければならない代替リスト型のような再帰的なデータ構造を作成する場合はどうでしょうか? この場合、再帰は Maybeの中にあります。どうすればそれを修正できますか?

はい、厳密な Maybe を使用できます。ただし、構造をインライン化して厳密にすることもできます。この場合、次のように記述します。

data NonNullList x = End x | Continue x !(NonNullList x)

データ構造に繰り返される情報が多すぎて (データ構造に大量のメタデータを保存しているMaybe (MyDataStructure x)可能性があります)、呼び出しが多すぎる場合、最終的には、data MyDataStructureDescriptor = MDSD { property1 :: !String, property2 :: !Int, ...}この記述子の多くの繰り返しを減らすことができるようにする必要があります。 1つの一般的な形式。これは実際、コードを整理するのにも非常に役立ちます。

于 2016-01-07T17:11:28.030 に答える
2

厳密などちらか/多分/タプル型を使用する理由:

  • コードをプロファイリングしてスペース リークに気付いた場合、それがリークを塞ぐ方法である可能性があります

  • 厳密なデータ型は、最新の GHC 8.0 言語拡張によってさえ、高性能コードにとって有用なものとして広く認識されています。

  • 他の人もそれを行っています (これらの厳密なパッケージは人気がないかもしれませんが、理由があって存在します。これらの厳密なパッケージが必要な種類のアプリケーションは、おそらく Hackage にアップロードされないだろうと主張することもできます)。

できない理由:

  • Preludeには入っていないのでエクストラパッケージです

  • 高性能なコードを書いていない可能性があります

  • 強打を 1 レベル内側に押し込んだからといって、プログラムが速くなることはないでしょう。

  • 高性能のコードを書いている場合は、とにかく手動でサンクの評価を強制することができますMaybe

全体として、ドグマが何らかの方向に進んでいるとは思いません。それは単に便宜上の問題です。

于 2016-01-07T15:43:53.113 に答える