9

次のような関数があります。

let isInSet setElems normalize p = 
        normalize p |> (Set.ofList setElems).Contains

この関数を使用して、要素が意味的に何らかのセットの一部であるかどうかをすばやく確認できます。たとえば、ファイル パスが html ファイルに属しているかどうかを確認するには、次のようにします。

let getLowerExtension p = (Path.GetExtension p).ToLowerInvariant()
let isHtmlPath = isInSet [".htm"; ".html"; ".xhtml"] getLowerExtension

ただし、上記のような関数を使用すると、「isInSet」に記述されている関数本体の評価が、すべてのパラメーターが判明するまで遅れるように見えるため、パフォーマンスが低下します。特に、(Set.ofList setElems).Containsの実行ごとに再評価されるなどの不変ビットisHtmlPath。

F# の簡潔で読みやすい性質を維持しながら、セットの構築が事前に評価されるより効率的な動作を維持するにはどうすればよいでしょうか。

上記は単なる例です。実装の詳細で行き詰まるのを回避する一般的なアプローチを探しています。実装の実行順序などの詳細に気を取られないようにしたいのですが、それは通常私にとって重要ではなく、主要なセールスポイントを損なうようなものだからです。関数型プログラミングの。

4

4 に答える 4

9

F# が純粋なコードと純粋でないコードを区別しない限り、そのような最適化が見られるとは思えません。ただし、カリー化を明示的にすることはできます。

let isInSet setElems =
    let set = Set.ofList setElems
    fun normalize p -> normalize p |> set.Contains

isHtmlSetは、クロージャーを取得するために 1 回だけ呼び出しisInSet、同時に を実行するようになりましたofList。

于 2010-04-24T11:19:20.733 に答える
5

@Khaの答えは的を射ています。F# は書き直せない

// effects of g only after both x and y are passed
let f x y =
    let xStuff = g x
    h xStuff y

の中へ

// effects of g once after x passed, returning new closure waiting on y
let f x =
    let xStuff = g x
    fun y -> h xStuff y

効果がないことがわかっている場合を除き、g現在の .NET Framework では、通常、すべての式の 99% の効果について推論することは不可能です。つまり、プログラマーは、上記のように評価順序を明示的にコーディングする責任があります。

于 2010-04-24T12:29:21.070 に答える
5

Khaからの回答は、クロージャを直接使用して手動でコードを最適化する方法を示しています。これが頻繁に使用する必要がある頻繁なパターンである場合は、2 つの関数から効率的なコードを構築する高階関数を定義することもできます。残りの引数を取得した後の実際の処理。

コードは次のようになります。

let preProcess finit frun preInput =  
  let preRes = finit preInput
  fun input -> frun preRes input

let f : string list -> ((string -> string) * string) -> bool =
  preProcess 
    Set.ofList                           // Pre-processing of the first argument
    (fun elemsSet (normalize, p) ->      // Implements the actual work to be 
      normalize p |> elemsSet.Contains) // .. done once we get the last argument

これがよりエレガントかどうかは問題ですが...

もう 1 つの (クレイジーな) アイデアは、これに計算式を使用できるというものです。これを可能にする計算ビルダーの定義は非常に標準的ではありません (これは人々が通常行うものではなく、モナドやその他の理論とはまったく関係ありません)。ただし、次のように記述できるはずです。

type CurryBuilder() = 
  member x.Bind((), f:'a -> 'b) = f
  member x.Return(a) = a
let curry = new CurryBuilder()

curry計算では、関数の次の引数を取得することを示すために使用できます(let!前のコードを評価した後)。

let f : string list -> (string -> string) -> string -> bool = curry {
  let! elems = ()
  let elemsSet = Set.ofList elems
  printf "elements converted"
  let! normalize = ()
  let! p = ()
  printf "calling"
  return normalize p |> elemsSet.Contains }

let ff = f [ "a"; "b"; "c" ] (fun s -> s.ToLower()) 
// Prints 'elements converted' here
ff "C"
ff "D"
// Prints 'calling' two times

計算式の詳細については、次のリソースを参照してください。

于 2010-04-24T14:10:25.043 に答える
2

  1. カレーは悪くない。カリー化は、クロージャーを導入することもあります。それらは通常効率的でもあります。私が以前に尋ねたこの質問を参照してください。必要に応じて、インラインを使用してパフォーマンスを向上させることができます。

  2. ただし、この例でのパフォーマンスの問題は、主にコードが原因です。

    normalize p |> (Set.ofList setElems).Contains

Set.ofList setElemsここでは、それをカレーにしても実行する必要があります。O(n log n) 時間かかります。setElemsのタイプをList ではなく F# Set に変更する必要があります。ところで、小さなセットの場合、クエリを実行する場合でも、リストを使用する方がセットよりも高速です。

于 2010-04-24T09:34:49.553 に答える