我有一个输入
string input = "14 + 2 * 32 / 60 + 43 - 7 + 3 - 1 + 0 * 7 + 87 - 32 / 34";
// up to 10MB string size
int result = Calc(input); // 11
14 + 2 * 32为512+-*/0是不可能的,所以一个/不能成为一个0我的方法
public static int Calc(string sInput)
{
int iCurrent = sInput.IndexOf(' ');
int iResult = int.Parse(sInput.Substring(0, iCurrent));
int iNext = 0;
while ((iNext = sInput.IndexOf(' ', iCurrent + 4)) != -1)
{
iResult = Operate(iResult, sInput[iCurrent + 1], int.Parse(sInput.Substring((iCurrent + 3), iNext - (iCurrent + 2))));
iCurrent = iNext;
}
return Operate(iResult, sInput[iCurrent + 1], int.Parse(sInput.Substring((iCurrent + 3))));
}
public static int Operate(int iReturn, char cOperator, int iOperant)
{
switch (cOperator)
{
case '+':
return (iReturn + iOperant);
case '-':
return (iReturn - iOperant);
case '*':
return (iReturn * iOperant);
case '/':
return (iReturn / iOperant);
default:
throw new Exception("Error");
}
}
我需要以最快的方式获得结果.
问题:有没有办法让这个计算更快？我有多个线程,但我只使用一个.
更新:
测试用例:(我已经删除了除0错误并将其StringBuilder.ToString()从StopWatch测量中移除)
Random rand = new Random();
System.Text.StringBuilder input = new System.Text.StringBuilder();
string operators = "+-*/";
input.Append(rand.Next(0, 100));
for (int i = 0; i < 1000000; i++)
{
int number = rand.Next(0, 100);
char coperator = operators[rand.Next(0, number > 0 ? 4 : 3)];
input.Append(" " + coperator + " " + number);
}
string calc = input.ToString();
System.Diagnostics.Stopwatch watch = new System.Diagnostics.Stopwatch();
watch.Start();
int result = Calc(calc);
watch.Stop();
Mar*_*ell 20
编辑编辑:使用The General和Mirai Mann的最新版本进行更新:
如果你想知道哪匹马最快:比赛马匹.以下是BenchmarkDotNet比较这个问题的各种答案的结果(我没有将他们的代码合并到我的完整示例中,因为感觉错误 - 只有数字被呈现)具有可重复但大的随机输入,通过:
static MyTests()
{
Random rand = new Random(12345);
StringBuilder input = new StringBuilder();
string operators = "+-*/";
var lastOperator = '+';
for (int i = 0; i < 1000000; i++)
{
var @operator = operators[rand.Next(0, 4)];
input.Append(rand.Next(lastOperator == '/' ? 1 : 0, 100) + " " + @operator + " ");
lastOperator = @operator;
}
input.Append(rand.Next(0, 100));
expression = input.ToString();
}
private static readonly string expression;
通过健全检查(检查他们都做对了):
Original: -1426
NoSubStrings: -1426
NoSubStringsUnsafe: -1426
TheGeneral4: -1426
MiraiMann1: -1426
我们得到时间(注意:Original在问题中是OP的版本; NoSubStrings[Unsafe]是我的版本来自下面,还有其他两个版本来自用户名的其他答案):
(较低的"均值"更好)
(注意;有一个较新版本的Mirai Mann的实现,但我不再设置运行新测试的东西;但是:公平地假设它应该更好!)
运行时:.NET Framework 4.7(CLR 4.0.30319.42000),32位LegacyJIT-v4.7.2633.0
Method | Mean | Error | StdDev |
------------------- |----------:|----------:|----------:|
Original | 104.11 ms | 1.4920 ms | 1.3226 ms |
NoSubStrings | 21.99 ms | 0.4335 ms | 0.7122 ms |
NoSubStringsUnsafe | 20.53 ms | 0.4103 ms | 0.6967 ms |
TheGeneral4 | 15.50 ms | 0.3020 ms | 0.5369 ms |
MiraiMann1 | 15.54 ms | 0.3096 ms | 0.4133 ms |
运行时:.NET Framework 4.7(CLR 4.0.30319.42000),64位RyuJIT-v4.7.2633.0
Method | Mean | Error | StdDev | Median |
------------------- |----------:|----------:|----------:|----------:|
Original | 114.15 ms | 1.3142 ms | 1.0974 ms | 114.13 ms |
NoSubStrings | 21.33 ms | 0.4161 ms | 0.6354 ms | 20.93 ms |
NoSubStringsUnsafe | 19.24 ms | 0.3832 ms | 0.5245 ms | 19.43 ms |
TheGeneral4 | 13.97 ms | 0.2795 ms | 0.2745 ms | 13.86 ms |
MiraiMann1 | 15.60 ms | 0.3090 ms | 0.4125 ms | 15.53 ms |
运行时:.NET Core 2.1.0-preview1-26116-04(CoreCLR 4.6.26116.03,CoreFX 4.6.26116.01),64位RyuJIT
Method | Mean | Error | StdDev | Median |
------------------- |----------:|----------:|----------:|----------:|
Original | 101.51 ms | 1.7807 ms | 1.5786 ms | 101.44 ms |
NoSubStrings | 21.36 ms | 0.4281 ms | 0.5414 ms | 21.07 ms |
NoSubStringsUnsafe | 19.85 ms | 0.4172 ms | 0.6737 ms | 19.80 ms |
TheGeneral4 | 14.06 ms | 0.2788 ms | 0.3723 ms | 13.82 ms |
MiraiMann1 | 15.88 ms | 0.3153 ms | 0.5922 ms | 15.45 ms |
BenchmarkDotNet:如果我正在尝试这个,我很想看看Span<T>2.1预览中的工作 - 关键是a Span<T>可以切片而不分配(并且a string可以转换为a Span<char>而不分配); 这将允许在没有任何分配的情况下执行字符串雕刻和解析.然而,减少分配并不总是与原始性能完全相同(尽管它们是相关的),所以要知道它是否更快:你需要比赛你的马(即比较它们).
如果Span<T>不是一个选项:你仍然可以通过跟踪一个做同样的事情int offset手动,只是*从来不使用SubString)
在任何一种情况下(string或Span<char>):如果你的操作只需要处理整数表示的某个子集,我可能会试图将角色定义int.Parse为不适用尽可能多的规则(文化,替代布局等)的自定义等价物,并且它可以在不需要的情况下工作Substring- 例如它可以采用a string和ref int offset,其中offset更新为解析停止的地方(因为它击中了操作员或空间),并且哪个有效.
就像是:
static class P
{
static void Main()
{
string input = "14 + 2 * 32 / 60 + 43 - 7 + 3 - 1 + 0 * 7 + 87 - 32 / 34";
var val = Evaluate(input);
System.Console.WriteLine(val);
}
static int Evaluate(string expression)
{
int offset = 0;
SkipSpaces(expression, ref offset);
int value = ReadInt32(expression, ref offset);
while(ReadNext(expression, ref offset, out char @operator, out int operand))
{
switch(@operator)
{
case '+': value = value + operand; break;
case '-': value = value - operand; break;
case '*': value = value * operand; break;
case '/': value = value / operand; break;
}
}
return value;
}
static bool ReadNext(string value, ref int offset,
out char @operator, out int operand)
{
SkipSpaces(value, ref offset);
if(offset >= value.Length)
{
@operator = (char)0;
operand = 0;
return false;
}
@operator = value[offset++];
SkipSpaces(value, ref offset);
if (offset >= value.Length)
{
operand = 0;
return false;
}
operand = ReadInt32(value, ref offset);
return true;
}
static void SkipSpaces(string value, ref int offset)
{
while (offset < value.Length && value[offset] == ' ') offset++;
}
static int ReadInt32(string value, ref int offset)
{
bool isNeg = false;
char c = value[offset++];
int i = (c - '0');
if(c == '-')
{
isNeg = true;
i = 0;
// todo: what to do here if `-` is not followed by [0-9]?
}
while (offset < value.Length && (c = value[offset++]) >= '0' && c <= '9')
i = (i * 10) + (c - '0');
return isNeg ? -i : i;
}
}
接下来,我可能会考虑是否值得切换unsafe到删除双倍长度检查.所以我会以两种方式实现它,并使用像BenchmarkDotNet这样的东西来测试它是否值得.
编辑:这是unsafe添加和BenchmarkDotNet用法:
using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;
using System;
static class P
{
static void Main()
{
var summary = BenchmarkRunner.Run<MyTests>();
System.Console.WriteLine(summary);
}
}
public class MyTests
{
const string expression = "14 + 2 * 32 / 60 + 43 - 7 + 3 - 1 + 0 * 7 + 87 - 32 / 34";
[Benchmark]
public int Original() => EvalOriginal.Calc(expression);
[Benchmark]
public int NoSubStrings() => EvalNoSubStrings.Evaluate(expression);
[Benchmark]
public int NoSubStringsUnsafe() => EvalNoSubStringsUnsafe.Evaluate(expression);
}
static class EvalOriginal
{
public static int Calc(string sInput)
{
int iCurrent = sInput.IndexOf(' ');
int iResult = int.Parse(sInput.Substring(0, iCurrent));
int iNext = 0;
while ((iNext = sInput.IndexOf(' ', iCurrent + 4)) != -1)
{
iResult = Operate(iResult, sInput[iCurrent + 1], int.Parse(sInput.Substring((iCurrent + 3), iNext - (iCurrent + 2))));
iCurrent = iNext;
}
return Operate(iResult, sInput[iCurrent + 1], int.Parse(sInput.Substring((iCurrent + 3))));
}
public static int Operate(int iReturn, char cOperator, int iOperant)
{
switch (cOperator)
{
case '+':
return (iReturn + iOperant);
case '-':
return (iReturn - iOperant);
case '*':
return (iReturn * iOperant);
case '/':
return (iReturn / iOperant);
default:
throw new Exception("Error");
}
}
}
static class EvalNoSubStrings {
public static int Evaluate(string expression)
{
int offset = 0;
SkipSpaces(expression, ref offset);
int value = ReadInt32(expression, ref offset);
while (ReadNext(expression, ref offset, out char @operator, out int operand))
{
switch (@operator)
{
case '+': value = value + operand; break;
case '-': value = value - operand; break;
case '*': value = value * operand; break;
case '/': value = value / operand; break;
default: throw new Exception("Error");
}
}
return value;
}
static bool ReadNext(string value, ref int offset,
out char @operator, out int operand)
{
SkipSpaces(value, ref offset);
if (offset >= value.Length)
{
@operator = (char)0;
operand = 0;
return false;
}
@operator = value[offset++];
SkipSpaces(value, ref offset);
if (offset >= value.Length)
{
operand = 0;
return false;
}
operand = ReadInt32(value, ref offset);
return true;
}
static void SkipSpaces(string value, ref int offset)
{
while (offset < value.Length && value[offset] == ' ') offset++;
}
static int ReadInt32(string value, ref int offset)
{
bool isNeg = false;
char c = value[offset++];
int i = (c - '0');
if (c == '-')
{
isNeg = true;
i = 0;
}
while (offset < value.Length && (c = value[offset++]) >= '0' && c <= '9')
i = (i * 10) + (c - '0');
return isNeg ? -i : i;
}
}
static unsafe class EvalNoSubStringsUnsafe
{
public static int Evaluate(string expression)
{
fixed (char* ptr = expression)
{
int len = expression.Length;
var c = ptr;
SkipSpaces(ref c, ref len);
int value = ReadInt32(ref c, ref len);
while (len > 0 && ReadNext(ref c, ref len, out char @operator, out int operand))
{
switch (@operator)
{
case '+': value = value + operand; break;
case '-': value = value - operand; break;
case '*': value = value * operand; break;
case '/': value = value / operand; break;
default: throw new Exception("Error");
}
}
return value;
}
}
static bool ReadNext(ref char* c, ref int len,
out char @operator, out int operand)
{
SkipSpaces(ref c, ref len);
if (len-- == 0)
{
@operator = (char)0;
operand = 0;
return false;
}
@operator = *c++;
SkipSpaces(ref c, ref len);
if (len == 0)
{
operand = 0;
return false;
}
operand = ReadInt32(ref c, ref len);
return true;
}
static void SkipSpaces(ref char* c, ref int len)
{
while (len != 0 && *c == ' ') { c++;len--; }
}
static int ReadInt32(ref char* c, ref int len)
{
bool isNeg = false;
char ch = *c++;
len--;
int i = (ch - '0');
if (ch == '-')
{
isNeg = true;
i = 0;
}
while (len-- != 0 && (ch = *c++) >= '0' && ch <= '9')
i = (i * 10) + (ch - '0');
return isNeg ? -i : i;
}
}
Val*_*nko 17
以下解决方案是有限自动机.Calc(输入)= O(n).为了获得更好的性能,这种解决方案不使用IndexOf,Substring,Parse,字符串连接,或价值反复阅读(取input[i]一次以上)...只是一个字处理器.
static int Calculate1(string input)
{
int acc = 0;
char last = ' ', operation = '+';
for (int i = 0; i < input.Length; i++)
{
var current = input[i];
switch (current)
{
case ' ':
if (last != ' ')
{
switch (operation)
{
case '+': acc += last - '0'; break;
case '-': acc -= last - '0'; break;
case '*': acc *= last - '0'; break;
case '/': acc /= last - '0'; break;
}
last = ' ';
}
break;
case '0': case '1': case '2': case '3': case '4':
case '5': case '6': case '7': case '8': case '9':
if (last == ' ') last = current;
else
{
var num = (last - '0') * 10 + (current - '0');
switch (operation)
{
case '+': acc += num; break;
case '-': acc -= num; break;
case '*': acc *= num; break;
case '/': acc /= num; break;
}
last = ' ';
}
break;
case '+': case '-': case '*': case '/':
operation = current;
break;
}
}
if (last != ' ')
switch (operation)
{
case '+': acc += last - '0'; break;
case '-': acc -= last - '0'; break;
case '*': acc *= last - '0'; break;
case '/': acc /= last - '0'; break;
}
return acc;
}
另一个实现.它从输入中减少了25%.我希望它的性能提高25%.
static int Calculate2(string input)
{
int acc = 0, i = 0;
char last = ' ', operation = '+';
while (i < input.Length)
{
var current = input[i];
switch (current)
{
case ' ':
if (last != ' ')
{
switch (operation)
{
case '+': acc += last - '0'; break;
case '-': acc -= last - '0'; break;
case '*': acc *= last - '0'; break;
case '/': acc /= last - '0'; break;
}
last = ' ';
i++;
}
break;
case '0': case '1': case '2': case '3': case '4':
case '5': case '6': case '7': case '8': case '9':
if (last == ' ')
{
last = current;
i++;
}
else
{
var num = (last - '0') * 10 + (current - '0');
switch (operation)
{
case '+': acc += num; break;
case '-': acc -= num; break;
case '*': acc *= num; break;
case '/': acc /= num; break;
}
last = ' ';
i += 2;
}
break;
case '+': case '-': case '*': case '/':
operation = current;
i += 2;
break;
}
}
if (last != ' ')
switch (operation)
{
case '+': acc += last - '0'; break;
case '-': acc -= last - '0'; break;
case '*': acc *= last - '0'; break;
case '/': acc /= last - '0'; break;
}
return acc;
}
我实现了另外一个变体:
static int Calculate3(string input)
{
int acc = 0, i = 0;
var operation = '+';
while (true)
{
var a = input[i++] - '0';
if (i == input.Length)
{
switch (operation)
{
case '+': acc += a; break;
case '-': acc -= a; break;
case '*': acc *= a; break;
case '/': acc /= a; break;
}
break;
}
var b = input[i];
if (b == ' ') i++;
else
{
a = a * 10 + (b - '0');
i += 2;
}
switch (operation)
{
case '+': acc += a; break;
case '-': acc -= a; break;
case '*': acc *= a; break;
case '/': acc /= a; break;
}
if (i >= input.Length) break;
operation = input[i];
i += 2;
}
return acc;
}
抽象结果:
根据评论,这个答案并不能提供高效的解决方案.我会把它留在这里,因为有些要考虑/将来可能会对其他人发现这个问题感兴趣; 但正如人们在下面所说,这远非最高效的解决方案.
.net框架已经提供了一种处理以字符串形式给出的公式的方法:
var formula = "14 + 2 * 32 / 60 + 43 - 7 + 3 - 1 + 0 * 7 + 87 - 32 / 34";
var result = new DataTable().Compute(formula, null);
Console.WriteLine(result); //returns 139.125490196078
根据评论主题,我需要指出一些事情:
没有; 这符合正常的数学规则.
我假设你修改后的规则是简化编写代码来处理它们,而不是因为你想支持一个新的数学分支？如果是这样的话,我会反对.人们会期望事物以某种方式表现; 所以你必须确保任何向你的代码发送方程式的人都准备好了解这些新数学的规则,而不是能够使用他们现有的期望.
这里没有改变规则的选择; 因此,如果您的要求是更改数学规则,这将不适合您.
没有.但是,如果MS花费大量时间优化代码,它应该表现良好,因此可能比任何手动代码执行速度更快(尽管这个代码不仅支持四个主要运算符) ;所以它没有完全相同).
根据MatthewWatson的特定注释(即调用DataTable构造函数会产生很大的开销),您需要创建并重新使用此对象的一个实例.根据您的解决方案的外观,有多种方法可以做到这一点; 这是一个:
interface ICalculator //if we use an interface we can easily switch from datatable to some other calulator; useful for testing, or if we wanted to compare different calculators without much recoding
{
T Calculate<T>(string expression) where T: struct;
}
class DataTableCalculator: ICalculator
{
readonly DataTable dataTable = new DataTable();
public DataTableCalculator(){}
public T Calculate<T>(string expression) where T: struct =>
(T)dataTable.Compute(expression, null);
}
class Calculator: ICalculator
{
static ICalculator internalInstance;
public Calculator(){}
public void InitialiseCalculator (ICalculator calculator)
{
if (internalInstance != null)
{
throw new InvalidOperationException("Calculator has already been initialised");
}
internalInstance = calculator;
}
public T Calculate<T>(string expression) where T: struct =>
internalInstance.Calculate<T>(expression);
}
//then we use it on our code
void Main()
{
var calculator1 = new Calculator();
calculator1.InitialiseCalculator(new DataTableCalculator());
var equation = "14 + 2 * 32 / 60 + 43 - 7 + 3 - 1 + 0 * 7 + 87 - 32 / 34";
Console.WriteLine(calculator1.Calculate<double>(equation)); //139.125490196078
equation = "1 + 2 - 3 + 4";
Console.WriteLine(calculator1.Calculate<int>(equation)); //4
calculator1 = null;
System.GC.Collect(); //in reality we'd pretty much never do this, but just to illustrate that our static variable continues fro the life of the app domain rather than the life of the instance
var calculator2 = new Calculator();
//calculator2.InitialiseCalculator(new DataTableCalculator()); //uncomment this and you'll get an error; i.e. the calulator should only be initialised once.
equation = "1 + 2 - 3 + 4 / 5 * 6 - 7 / 8 + 9";
Console.WriteLine(calculator2.Calculate<double>(equation)); //12.925
}
注意:上面的解决方案使用静态变量; 有些人反对使用静力学.对于这种情况(即在应用程序的生命周期中,您只需要一种方法进行计算),这是一个合法的用例.如果您想支持在运行时切换计算器,则需要采用不同的方法.
运行了一些性能测试:
DataTable.Compute方法最大的问题是,对于你正在处理它的大小的方程式抛出一个StackOverflowException; (即基于你的方程生成器的循环for (int i = 0; i < 1000000; i++).i < 1000),计算方法(包括构造函数和Convert.ToInt32对double结果)需要更长的时间几乎100倍.链接到文档:https://msdn.microsoft.com/en-us/library/system.data.datatable.compute%28v=vs.110%29.aspx？ f = 255 & MSPPError = -2147217396
| 归档时间： |
|
| 查看次数： |
2174 次 |
| 最近记录： |