performance - インテリジェントな純粋機能セット

Question

和集合、交点、差で構成される集合計算は、多くの場合、さまざまな方法で表現できます。与えられた答えに到達するために必要な計算量を最小限に抑えようとする理論や具体的な実装はありますか?

たとえば、非晶質材料のシミュレーションで原子を隣接シェルに分解しようとしたときに、これの実用的なアプリケーションに最初に出会いました。最初のシェルは、特定の元の原子のすぐ隣にあり、2 番目のシェルは隣接している原子です。最初のシェルにもその前のシェルにもない最初のシェル:

nth 0 = singleton i
nth 1 = neighbors i
nth n = reduce union (map neighbors (nth(n-1))) - nth(n-1) - nth(n-2)

これを解決するには、さまざまな方法があります。結果を構成しながら各セットのメンバーシップを段階的にテストするか、3 つの隣接するシェルの結合を計算し、交差を使用して前の 2 つのシェルを削除し、最も外側のシェルを残すことができます。実際には、大きな中間セットの構築を必要とするソリューションは遅くなります。

おそらく、インテリジェントなセットの実装は、評価される式を構成し、それを評価する前に (中間セットのサイズを縮小するために) 最適化して、パフォーマンスを向上させることができます。そのようなセットの実装は存在しますか?

Answer 1

あなたの質問は、この論文で説明されているHaskellのストリーム融合をすぐに思い出させました。一般的な原則は非常に簡単に要約できます。リストを保存する代わりに、リストを作成する方法を保存します。次に、リスト変換関数はリストジェネレーターで直接動作します。つまり、すべての操作は、中間構造なしで単一世代のデータに融合されます。次に、作成操作が完了したら、ジェネレーターを実行してデータを生成します。

したがって、あなたの質問に対する答えは、計算を融合し、中間データ構造を排除する同様のインテリジェントなメカニズムが必要な場合、セットを「共同構造」に変換する方法を見つける必要があるということだと思います（それが論文ですセットを生成し、それを直接操作し、完了したら実際にセットを生成します。

この概念の背後には、この論文が示唆しているが、決して詳しく説明していないという非常に深い理論があると思います。ここにいる誰かがそれが何であるかを知っている場合は、私に知らせてください。これは私が行っている他のことにも非常に関連しているからです。