8

コンテキスト

この質問の文脈は、 Erlangを使用して、進化的アルゴリズムの形式であるGene Expression Programming （GEP）を試してみたいということです。GEPは、「Karva表記」と呼ばれる文字列ベースのDSLを利用します。Karva表記は、式解析ツリーに簡単に変換されますが、変換アルゴリズムは、可変オブジェクトを持つ実装を想定しています。不完全な部分式は、変換プロセスの早い段階で作成され、独自の部分式は、後で、次の値で埋められます。それらが作成された時点では不明です。

Karva表記の目的は、高価なエンコード手法や遺伝暗号の修正なしに、構文的に正しい式が作成されることを保証することです。問題は、Erlangのような単一代入プログラミング言語では、各サブ式が入力されるたびに式ツリーを継続的に再作成する必要があることです。これには安価な--O（n）？-操作を更新し、指数関数的な時間で完了するものに変換します（私が間違っていない限り）。K式を式ツリーに変換するための効率的な関数アルゴリズムが見つからない場合、GEPの魅力的な機能の1つが失われます。

質問

K式の変換の問題がかなりあいまいであることを理解しているので、本質的に機能しないアルゴリズム（可変データ構造を利用するアルゴリズム）を機能しないアルゴリズムに変換する方法についてのアドバイスが必要です。純粋な関数型プログラミング言語は、コンピューターサイエンスの初期に作成された、必要なパフォーマンス特性を得るために可変性に依存するアルゴリズムとデータ構造の多くをどのように適応させるのでしょうか。

4

4 に答える 4

3

これを行う方法は 1 つではなく、ケースバイケースで試行する必要があります。私は通常、折り畳みと展開を使用してそれらをより単純な操作に分解し、そこから最適化しようとします。他の人が指摘したように、Karva デコード ケースは幅優先のツリー展開であるため、treeUnfoldM_BF から始めました。おそらくErlangにも同様の関数があります。

デコード操作が不当に高価な場合は、デコードをメモ化し、サブツリーを共有/再利用できます...ただし、おそらく一般的なツリー展開フォルダーには収まらず、そのために特殊な関数を作成する必要があります。フィットネス関数が十分に遅い場合は、以下にリストしたような単純なデコーダーを使用しても問題ない場合があります。呼び出しごとにツリーを完全に再構築します。

import Control.Monad.State.Lazy
import Data.Tree

type MaxArity = Int
type NodeType = Char

treeify :: MaxArity -> [Char] -> Tree NodeType
treeify maxArity (x:xs) = evalState (unfoldTreeM_BF (step maxArity) x) xs
treeify _ [] = fail "empty list"

step :: MaxArity -> NodeType -> State [Char] (NodeType, [NodeType])
step maxArity node = do
  xs <- get
  -- figure out the actual child node count and use it instead of maxArity
  let (children, ys) = splitAt maxArity xs
  put ys
  return (node, children)

main :: IO ()
main = do
 let x = treeify 3 "0138513580135135135"
 putStr $ drawTree . fmap (:[]) $ x
 return ()
于 2011-08-06T00:31:08.047 に答える
2

Kツリーに関する特定の問題を解決する方法を理解したと思います（一般的な問題は難しすぎます:P）。私のソリューションは、ある種の恐ろしいハイブリッド Python ライク psudocode で提示されます (今日の私の FP では非常に遅いです)が、ノードを作成した後にノードを変更しません (トリックは、ツリーをボトムアップで構築することです)。

まず、どのノードがどのレベルに属しているかを見つける必要があります。

levels currsize nodes = 
    this_level , rest = take currsize from nodes, whats left
    next_size = sum of the arities of the nodes
    return [this_level | levels next_size rest]
(initial currsize is 1)

したがって+/*abcd、例では、これにより が得られるはずです[+, /*, abcd]。これをボトムアップのツリーに変換できます。

curr_trees = last level
for level in reverse(levels except the last)
    next_trees = []
    for root in level:
        n = arity of root
        trees, curr_trees = take n from curr_trees, whats left
        next_trees.append( Node(root, trees) )
    curr_trees = next_trees

curr_trees should be a list with the single root node now.

これを単一の代入 Erlang/Haskell に非常に簡単に変換できると確信しています。

于 2011-07-30T14:04:18.140 に答える
2

関数型プログラミングで変更可能な状態が必要な場合、いくつかの解決策があります。

  1. 同じ問題を解決する別のアルゴリズムを使用します。たとえば、クイックソートは一般に変更可能と見なされるため、機能的な設定ではあまり役に立たない可能性がありますが、マージソートは一般的に機能的な設定により適しています。このオプションが可能かどうか、またはあなたの場合に意味があるかどうかはわかりません。

  2. 関数型プログラミング言語でさえ、通常、状態を変更する何らかの方法を提供します。(このブログ投稿は、Erlang でそれを行う方法を示しているようです。) 一部のアルゴリズムとデータ構造では、これが実際に利用可能な唯一のオプションです (このトピックに関する活発な研究があると思います)。たとえば、関数型プログラミング言語のハッシュ テーブルは、通常、変更可能な状態で実装されます。

あなたの場合、不変性が実際にパフォーマンスのボトルネックにつながるかどうかはわかりません。そうです、(サブ) ツリーは更新時に再作成されますが、Erlang の実装はおそらく変更されていないすべてのサブツリーを再利用するため、変更可能な状態の O(1) ではなく、更新ごとに O(log n) の複雑さが生じます。 . また、ツリーのノードはコピーされませんが、代わりにノードへの参照がコピーされます。これは比較的効率的です。関数設定でのツリーの更新については、たとえば岡崎の論文や、その論文に基づいた彼の著書「Purely Functional Data Structures」で読むことができます。不変のデータ構造を使用してアルゴリズムを実装し、パフォーマンスの問題がある場合は可変のものに切り替えてみます。

また、関連する SO の質問のいくつかをこちらとこちらで参照してください。

于 2011-07-30T13:30:25.393 に答える