2

目標: 組み込みsorted(..)関数を使用せずに機能的な方法でシーケンスを並べ替えます。

def my_sorted(seq):
    """returns an iterator"""
    pass

動機: FP のやり方では、私は制約を受けています。

  • 変更しないseq(イテレータまたは実現リストの可能性があります)
  • 暗黙的に、インプレースソートはありません。

質問 1 mutate できないためseq、ソートされたシーケンスを格納するために別の可変データ構造を維持する必要があります。in-place に比べて無駄に思えlist.sort()ます。他の関数型プログラミング言語はこれをどのように処理しますか?

質問 2変更可能なシーケンスを返す場合、機能パラダイムでは問題ありませんか?

4

5 に答える 5

1

インプレースミューテーションは、他の誰もデータへの参照を持っていない場合にのみ安全であり、ソート前のデータであることが期待されます。したがって、一般に、ソートされた結果の新しい構造を持つことは実際には無駄ではありません。インプレース最適化は、データを線形的に使用している場合にのみ安全です。

したがって、新しい構造を割り当てるだけです。これは、より一般的に役立つためです。インプレースバージョンは特殊なケースです。

于 2012-05-22T12:02:47.653 に答える
1

適切な防御的プログラミングは無駄になることもありますが、それに対してできることも何もありません。

これが、機能的な使用をゼロからサポートするために構築された言語が、ネイティブで不変の型に対して構造的な共有を使用する理由です。関数型プログラミング用に構築されていない言語 (Python など) での関数型スタイルのプログラミングは、当然ながら十分にサポートされません。とはいえ、並べ替え操作は必ずしも構造共有の良い候補ではありません (マイナーな変更以上の変更が必要な場合)。

そのため、他の関数型言語であっても、ソートには少なくとも 1 つのコピー操作が含まれることがよくあります。たとえば、Clojure は、Java のネイティブな (高度に最適化された) 並べ替え操作を一時的な変更可能な配列に委譲し、その配列をラップする seq を返します (したがって、同じデータを入力するために使用された入力と同じように結果を不変にします)。入力が不変で、出力が不変で、その間に何が起こるかが外部の世界 (特に、他のスレッド) から見えない場合、一時的な可変性はしばしば必要かつ適切なものです。

于 2012-05-22T12:10:03.573 に答える
1

もちろん、並べ替えは完全に遅延することはできません (入力の最後の要素が出力の最初の要素になる可能性があります) が、シーケンス全体を読み取った後、要求された要素ごとに正確に並べ替えられた出力のみを生成する計算遅延並べ替えを実装できます。少なくとも 1 つの出力が要求されるまで入力の読み取りを遅らせることもできるため、並べ替えや結果の無視に計算は必要ありません。

この計算的に怠惰なアプローチの場合、私が知っている最良の候補はヒープソート アルゴリズムです (事前にヒープ構築ステップのみを実行します)。

于 2012-05-22T10:25:29.170 に答える
0

何の無駄？ビット？電気？壁時計の時間？十分な CPU と大量のデータがある場合は、並列マージソートが最も速く完了する可能性がありますが、多くの中間表現が生成される可能性があります。

一般に、アルゴリズムを並列化すると、逐次アルゴリズムとは非常に異なる最適化戦略になる可能性があります。たとえば、アムダールの法則により、共有を避けるために冗長な作業をローカルで再実行します。これは、シリアル コンテキストでは「無駄」と見なされる場合がありますが、はるかにスケーラブルなアルゴリズムにつながります。

于 2012-05-23T21:39:35.887 に答える
0

ヒープソートやマージソートなど、新しいデータ構造を作成する方法で実行できるソート アルゴリズムを使用します。

于 2012-05-22T10:24:57.587 に答える