0

我已经实现了一些功能的天真的评估器。我刚刚进入 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

编辑：此评估器用于验证布尔条件。在此版本中，只有一个 Dictionary 并且性能更高，但是我如何模拟以下情况：

  1. var1 == "foo1" && var1=="foo2" ---> 可满足：假
  2. var2>=0 && var2>0 ---> 可满足：真
  3. (var3 == "foo2" && var3 != null) || var3 == "foo1" --> 可满足：真
4

2 回答 2

1

答案是：视情况而定。

在某些情况下，最好天真地走在树上进行评估。当您的表达式很小并且只评估一次或只评估几次时，这可能是最好的策略。

如果您的表达式很大并且可能会被评估，那么最好尝试做一些优化。任何优化都会有相关的成本需要摊销，因此这就是为什么最好针对需要执行多次的大型表达式。您可以尝试许多类型的优化，这里有一些建议（一本好的编译器教科书无疑会有更多更好的建议）：

  • 走你的树，寻找可以提前执行的案例。例如，如果两个常量相邻，您可以执行操作（即将它们相加）并生成一个新的更小更简单的树。同样，如果你发现任何乘以零常数的东西，那么你可以简单地用零替换它，因为任何乘以零的东西都是零。
  • 你可以在你的树中寻找完全相同的分支，如果这个分支没有副作用，你可以缓存它的结果并且只执行一次（如果需要，这甚至可以在不同的表达式之间完成）。
  • 你可能想看看编译你的数据结构。在 .NET 中，您可以使用 Relection.Emit 命名空间，或通过 CodeDom 生成代码以生成与您的数据结构等效的代码。这将极大地加快执行速度，但编译成本会非常高，因此需要谨慎使用。

您实施的任何优化都应根据“naïve”基线仔细衡量，在某些情况下，您的优化可能无法按预期运行，并可能导致执行速度变慢。

任何其他非常简单的优化都可能很难实现，祝你好运！

于 2011-06-22T14:47:21.660 回答
0

也许最简单的代码优化可能会产生显着的收益，就是用Dictionary不分配的 .NET 替代方法替换您使用（可怕的）F# 扩展方法来搜索 a 。所以这：

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 symbols。
  • value用每个符号中的可变引用替换外部哈希表，给出在orenv字典中查找该符号的结果。
于 2011-06-25T16:18:58.580 回答