最佳性能評估者f＃

Question

我已經實現了一些天真的評估者的一些功能。我剛剛進入了f＃的世界，所以它會問你是否存在（如果是，如何實現）一個更快的評估器。我必須得到一個包含（variableName，（condition + newVariableName））的數據結構。這兩個字段是字符串。以下是我評估版本的一部分：

let env = new Dictionary<_,_>(HashIdentity.Structural) 
//eval: expr -> Prop 
let rec eval = function 
//Val of string -- is a variable name or a string value 
| Val e -> if e.Equals("TRUE") then True  // True is a Prop type used for BDD Algorithm 
      elif e.Equals("FALSE") then False // False is a Prop type used for BDD Algorithm 
      else var e //var of string --- is a Prop type used for BDD Algorithm 
| Int i -> var (i.ToString()) 
| Float e -> var (e.ToString()) 
| Const c -> var c //Const of string --- is a constant name (ex. "$foo" is a constant) 
| Path (e, s) -> var ((eval e).ToString() + "." + s) 
| Lookup(s, el) -> var s 
| Integer(ex) -> eval ex 
| FromTo (e, el) ->var ((eval e).ToString() + (eval el.Head).ToString() + (eval el.Tail.Head).ToString()) 
| Str(e) -> eval e 
| Equality (v, e) -> let evalV = eval v 
        let evalE = eval e 
        match evalE with 
        | Var e -> 
          let sndKey = "Equality" + evalE.ToString() 
          if env.ContainsKey (evalV.ToString()) then 
           if env.[(evalV.ToString())].Equals(sndKey) then 
            var env.[(evalV.ToString())] 
           else ~~~ (var env.[(evalV.ToString())]) 
          else 
           env.Add((evalV.ToString()), (evalV.ToString()) + sndKey) 
           var ((evalV.ToString()) + sndKey) 
        | _ as k -> if bddBuilder.Equiv k False then 
            let sndKey = "Equality" + "False" 
            if env.ContainsKey (evalV.ToString()) then 
             if env.[(evalV.ToString())].Equals(sndKey) then 
              var env.[(evalV.ToString())] 
             else ~~~ (var env.[(evalV.ToString())]) 
            else 
             env.Add((evalV.ToString()), (evalV.ToString()) + sndKey) 
             var ((evalV.ToString()) + sndKey) 
           else let sndKey = "Equality" + "True" 
             if env.ContainsKey (evalV.ToString()) then 
              if env.[(evalV.ToString())].Equals(sndKey) then 
               var env.[(evalV.ToString())] 
              else ~~~ (var env.[(evalV.ToString())]) 
             else 
              env.Add((evalV.ToString()), (evalV.ToString()) + sndKey) 
              var ((evalV.ToString()) + sndKey) 
| Inequality (v, e) -> let evaluatedV = (eval v).ToString() 
         let evaluatedE = (eval e).ToString() 
         let sndKey = "Inequality" + evaluatedE 
         if env.ContainsKey (evaluatedV.ToString()) then 
          if env.[(evaluatedV.ToString())].Equals(sndKey) then 
            var env.[(evaluatedV.ToString())] 
          else ~~~ (var env.[(evaluatedV.ToString())]) 
         else env.Add((evaluatedV.ToString()), (evaluatedV.ToString()) + sndKey) 
          var ((evaluatedV.ToString()) + sndKey) 
| IfThenElse (e1, e2, e3) -> (eval e1 &&& eval e2) ||| ((~~~ (eval e1)) &&& eval e3) 
| FindString(e1, e2) -> var ("FS" + (eval e1).ToString() + (eval e2).ToString()) 
| GreaterThan(e1, e2) -> let evaluatedV = (eval e1).ToString() 
         let evaluatedE = (eval e2).ToString() 
         let sndKey = "GreaterThan" + evaluatedE 
         if env.ContainsKey (evaluatedV.ToString()) then 
          if env.[(evaluatedV.ToString())].Equals(sndKey) then 
            var env.[(evaluatedV.ToString())] 
          else ~~~ (var env.[(evaluatedV.ToString())]) 
         else env.Add((evaluatedV.ToString()), (evaluatedV.ToString()) + sndKey) 
           var ((evaluatedV.ToString()) + sndKey) 
| GreaterThanOrEqual(e1, e2) -> let evaluatedV = (eval e1).ToString() 
           let evaluatedE = (eval e2).ToString() 
           let sndKey = "GreaterThanOrEqual" + evaluatedE 
           if env.ContainsKey (evaluatedV.ToString()) then 
            if env.[(evaluatedV.ToString())].Equals(sndKey) then 
             var env.[(evaluatedV.ToString())] 
            else ~~~ (var env.[(evaluatedV.ToString())]) 
           else env.Add((evaluatedV.ToString()), (evaluatedV.ToString()) + sndKey) 
            var ((evaluatedV.ToString()) + sndKey) 
| Null(e) -> var ("Null" + (eval e).ToString()) 
| GetToken(e1, e2, e3) -> var ((eval e1).ToString() + (eval e2).ToString()) 
| Mod(e1, e2) -> var ((eval e1).ToString() + (eval e2).ToString()) 
| Match(e1, e2) -> let evaluatedV = (eval e1).ToString() 
        let evaluatedE = (eval e2).ToString() 
        let sndKey = "Match" + evaluatedE 
        if env.ContainsKey (evaluatedV.ToString()) then 
         if env.[(evaluatedV.ToString())].Equals(sndKey) then 
           var env.[(evaluatedV.ToString())] 
         else ~~~ (var env.[(evaluatedV.ToString())]) 
        else env.Add((evaluatedV.ToString()), (evaluatedV.ToString()) + sndKey) 
         var ((evaluatedV.ToString()) + sndKey) 
| LessThenOrEqual(e1, e2) -> let evaluatedV = (eval e1).ToString() 
          let evaluatedE = (eval e2).ToString() 
          let sndKey = "LessThen" + evaluatedE 
          if env.ContainsKey (evaluatedV.ToString()) then 
           if env.[(evaluatedV.ToString())].Equals(sndKey) then 
            var env.[(evaluatedV.ToString())] 
           else ~~~ (var env.[(evaluatedV.ToString())]) 
          else env.Add((evaluatedV.ToString()), (evaluatedV.ToString()) + sndKey) 
            var ((evaluatedV.ToString()) + sndKey) 
| LessThen(e1, e2) -> let evaluatedV = (eval e1).ToString() 
         let evaluatedE = (eval e2).ToString() 
         let sndKey = "LessThen" + evaluatedE 
         if env.ContainsKey (evaluatedV.ToString()) then 
          if env.[(evaluatedV.ToString())].Equals(sndKey) then 
            var env.[(evaluatedV.ToString())] 
          else ~~~ (var env.[(evaluatedV.ToString())]) 
         else env.Add((evaluatedV.ToString()), (evaluatedV.ToString()) + sndKey) 
          var ((evaluatedV.ToString()) + sndKey) 
| Length(e) -> var ("Len" + (eval e).ToString()) 
| Full(e) -> var ("Full" + (eval e).ToString()) 
| Minus(e1, e2) -> var ((eval e1).ToString() + (eval e2).ToString()) 
| Times(e1, e2) -> var ((eval e1).ToString() + (eval e2).ToString()) 
| Plus (e1, e2) -> var ((eval e1).ToString() + (eval e2).ToString()) 
| Duration(e) -> eval e 
| Minutes(e) -> eval e 
| Trim(e) -> var ("Tri" + (eval e).ToString()) 
| Reverse(e) -> var ("Rev" + (eval e).ToString()) 
| Ast.And (v1, v2) -> eval v1 &&& eval v2 
| Ast.Or (v1, v2) -> eval v1 ||| eval v2 
| Ast.Not(v1) -> ~~~ (eval v1) 
| _ as a-> failwithf "Expression %A not found" a 

編輯：此評估器用於驗證布爾條件。在這個版本中，只有一個解釋，這是更好的性能，但我怎麼可以模擬，如以下幾種情況：

1. VAR1 ==「foo1」 & & VAR1 ==「foo2的」 --->可滿足：假
2. VAR2> = 0 & & VAR2> 0 --->滿足的：真正的
3. （！VAR3 == 「foo2的」 & & VAR3 = NULL）|| var3 ==「foo1」 - >可以滿足：true

Answer 1

答案是：取決於。

有些情況下，最好天真地走樹評估你去。當你的表情很小並且評估一次或者僅僅幾次時，這可能是最好的策略。

如果你的表情很大，也許評估過的時間可能是最好的嘗試和做一些優化。任何優化都會產生相關成本，需要進行攤銷，所以這就是爲什麼最好針對需要多次執行的大型表達式。有許多類型的優化，你可以嘗試的，這裏有一些建議（良好的編譯器教科書無疑有更多更好的建議）：

• 走你的樹尋找案件 可能是預先執行。例如，如果兩個常量是鄰近的 ，則可能能夠執行 操作（即，將它們一起添加到 ），併產生更簡單的新樹 。同樣，如果您發現任何乘以零的常數，那麼您可以簡單地用零代替這個 ，因爲任何東西 乘以零都是零。
• 你可以走你的樹尋找 分支即是完全等價的， 如果這個分支具有無副作用， 您可以緩存其結果 只有一次執行它（這可能 甚至不同之間完成 表達式）。
• 你可能想看看編譯 你的數據結構。在.NET中您可以使用Relection.Emit命名空間 或 通過CodeDom生成代碼至 生成的代碼與您的數據結構等效的 。這將使 的加速執行速度巨大，但 的編譯將會有很高的成本，所以它的策略是使用 仔細。

您實施的任何優化都應該根據「天真」基準仔細衡量，在某些情況下，您的優化可能不像預期的那樣運行，並可能導致執行速度降低。

其他任何非常簡單的優化可能會相當棘手的實現，所以祝你好運！

Answer 2

也許對您的代碼的最簡單的優化可能會產生顯着的收益，取代使用（horrid）F＃擴展方法搜索Dictionary與不分配的.NET替代方法。所以這個：

match env.TryGetValue evaluatedV with 
| true, v1 -> 
    match v1.TryGetValue sndKey with 
    | true, v2 -> v2 
    | _ -> 
     v1.[sndKey] <- evaluetedV + sndKey 
     env.[evaluatedV] <- v1 
     evaluatedV + sndKey 
| _ -> 
    if value.Count <> 0 then value.Clear() 
    value.[sndKey] <- evaluetedV + sndKey 
    env.[evaluatedV] <- value 
    evaluatedV + sndKey 

變爲：

let mutable v1 = Unchecked.defaultof<_> 
if env.TryGetValue(evaluatedV, &v1) then 
    let mutable v2 = Unchecked.defaultof<_> 
    if v1.TryGetValue(sndKey, &v2) then v2 else 
    v1.[sndKey] <- evaluetedV + sndKey 
    env.[evaluatedV] <- v1 
    evaluatedV + sndKey 
else 
    if value.Count <> 0 then value.Clear() 
    value.[sndKey] <- evaluetedV + sndKey 
    env.[evaluatedV] <- value 
    evaluatedV + sndKey 

但是，這些哈希表查找可能正在殺死你的表現。有多種技術可以避免這些問題，但它們不是F＃特定的：

• 將您的兩個散列表查找合併爲一個散列表查找。
• 用更高效的類型替換字符串，例如哈希consed符號。
• 用每個符號中的可變引用代替外部哈希表，給出在value或env字典中查找該符號的結果。