0
我的解析器通過首先從中綴轉換爲後綴來評估PEMDAS表達式，然後使用標準後綴評估規則。我解析表達式並將令牌存儲在列表中。這個預編譯對我來說可以，因爲我打算緩存預編譯的函數。幫助優化我的RPN評估函數
我想優化評估函數（請參閱代碼中的Evaluate04）。在我的硬件上，我可以在不到600毫秒內獲得1,000,000次評估。說實話，我相信這已經足夠快了。遠快於數據庫訪問調用來獲取表達式。
我想看看你們是否可以讓它變得更快。微優化，完全重構類。如何完成並不重要。
這是一樣快，我已經能夠得到它，你能改善它嗎？
using System;
using System.Collections.Generic;
using System.Linq;
using System.Windows.Forms;
namespace ParseTest2
{
public partial class Form1 : Form
{
public Form1()
{
InitializeComponent();
}
enum Operator {Add, Subtract, Multiply, Divide}
enum TokenType { Variable, Value, Add, Subtract, Multiply, Divide };
private class TokenFactory
{
public static Token Add
{
get { return new Token(TokenType.Add); }
}
public static Token Subtract
{
get { return new Token(TokenType.Subtract); }
}
public static Token Multiply
{
get { return new Token(TokenType.Multiply); }
}
public static Token Divide
{
get { return new Token(TokenType.Divide); }
}
public static Token Val(float value)
{
return new Token(value);
}
public static Token Var(string variable)
{
return new Token(variable);
}
}
private class Token
{
public readonly TokenType TokenType;
public float Value;
public readonly string Variable;
public Token(TokenType tokenType)
{
TokenType = tokenType;
//Value = 0;
//Variable = null;
}
public Token(float value)
{
TokenType = TokenType.Value;
Value = value;
//Variable = null;
}
public Token(string variable)
{
//TokenType = TokenType.Variable;
Variable = variable;
//Value = 0;
}
public override string ToString()
{
return
Expression.IsOperand(this) ?
string.Format("{0} {1} {2}", TokenType, Variable ?? "", Value) :
string.Format("{0}", TokenType);
}
}
class Expression
{
List<Token> _tokens;
public Action<Token> SetVariableValue;
public Expression(string expression)
{
//time to convert to postfix from infix
var infix = expression.Split(' ');
string postfix = string.Empty;
Action<string> add = s => {postfix += " " + s;};
var ops = new Stack<string>();
Func<string, int> getPrecedence = value =>
{
switch(value)
{
case "*":
case "/":
return 1;
case "+":
case "-":
return 0;
}
return -1;
};
Func<string, bool> isLowerOrEqualPrecedence = val =>
{
if (ops.Count == 0) return false;
var op = ops.Peek();
int cur = getPrecedence(val);
int top = getPrecedence(op);
return cur <= top;
};
foreach (string val in infix)
{
if ("-+*/".Contains(val))
{
if (ops.Count == 0)
ops.Push(val);
else
{
if (!isLowerOrEqualPrecedence(val))
{
ops.Push(val);
}
else
{
while (isLowerOrEqualPrecedence(val))
{
add(ops.Pop());
}
ops.Push(val);
}
}
}
else if (val == "(")
ops.Push(val);
else if (val == ")")
{
while (true)
{
var op = ops.Pop();
if (op == "(") break;
add(op);
}
}
else
{
add(val);
}
}
while (ops.Count > 0)
{
add(ops.Pop());
}
_tokens = new List<Token>();
foreach (string x in postfix.Trim().Split(' '))
{
switch(x)
{
case "*":
_tokens.Add(TokenFactory.Multiply);
break;
case "/":
_tokens.Add(TokenFactory.Divide);
break;
case "+":
_tokens.Add(TokenFactory.Add);
break;
case "-":
_tokens.Add(TokenFactory.Subtract);
break;
default:
_tokens.Add(TokenFactory.Var(x));
break;
}
}
}
public static bool IsOperand(Token tk)
{
return tk.TokenType == TokenType.Variable || tk.TokenType == TokenType.Value;
}
public float Evaluate04()
{
Token[] tokens = _tokens.ToArray();
int i;
for (i = tokens.Length - 1; i >= 0; --i)
if (tokens[i].TokenType == TokenType.Variable)
SetVariableValue(tokens[i]);
int tokenCount = tokens.Length;
while (true)
{
int i1 = 0, i2 = 0, i3 = 0;
//i1 = i2 = i3 = -1;
int j;
Token t1, t2, t3;
//looking for operator preceded by two operands
for (i = 0; i < tokens.Length - 2; ++i)
//i = 0;
//while(true)
{
t1 = null;
t2 = null;
t3 = null;
j = i;
do
{
t1 = tokens[j];
i1 = j++;
} while (t1 == null);
do
{
t2 = tokens[j];
i2 = j++;
} while (t2 == null);
do
{
t3 = tokens[j];
i3 = j++;
} while (t3 == null);
//it's a binary operation if t3 is an operator and t2, t1 are operands
//if (!IsOperand(t3) && IsOperand(t2) && IsOperand(t1))
if (
!(t3.TokenType == TokenType.Variable || t3.TokenType == TokenType.Value) &&
(t2.TokenType == TokenType.Variable || t2.TokenType == TokenType.Value) &&
(t1.TokenType == TokenType.Variable || t1.TokenType == TokenType.Value))
{
float val;
if (t3.TokenType == TokenType.Add)
val = t1.Value + t2.Value;
else if (t3.TokenType == TokenType.Divide)
val = t1.Value/t2.Value;
else if (t3.TokenType == TokenType.Subtract)
val = t1.Value - t2.Value;
else if (t3.TokenType == TokenType.Multiply)
val = t1.Value * t2.Value;
else
val = int.MinValue;
//we're done, return
if (tokenCount == 3)
return val;
tokenCount -= 2;
//ok, we are done processing these, null them
tokens[i1] = new Token(val);
tokens[i2] = null;
tokens[i3] = null;
//break, for loop and repeat until done
break;
}
}
}
}
}
private void Form1_Load(object sender, EventArgs e)
{
Action<Token> setVariableValue = token =>
{
if (token.Variable == "A")
token.Value = 4;
else if (token.Variable == "B")
token.Value = 5;
else if (token.Variable == "C")
token.Value = 7;
else if (token.Variable == "D")
token.Value = 2;
};
//spaces are required because I'm splitting on them.
//I know it's lame, it's a detail I'll address later...
var x = new Expression("(A + B)/(C + D)");
x.SetVariableValue = setVariableValue;
Func<float> eval = x.Evaluate04;
eval();
int count = 1000000;
float res = 0;
var sw = new System.Diagnostics.Stopwatch();
//sw.Start();
//Parallel.ForEach(Enumerable.Range(1, count), i =>
//{
// res = eval();
//});
//sw.Stop();
//Console.WriteLine("{0} takes: {1}", "parallel", sw.ElapsedMilliseconds);
sw.Reset();
sw.Start();
//for(int i=0; i<count; ++i)
foreach (int i in Enumerable.Range(1, count))
{
res = eval();
}
sw.Stop();
Console.WriteLine("{0} takes: {1}", "single thread", sw.ElapsedMilliseconds);
Console.WriteLine("{0}", res);
}
private void Form1_KeyDown(object sender, KeyEventArgs e)
{
if (e.KeyCode == Keys.Escape)
Close();
}
}
}
如果您的函數被重用的次數比創建次數多，那麼LINQ Expressions API將佔主導地位。 – 2009-10-19 22:12:06