解决链式计算的最快方法 [英] Fastest way to solve chain-calculations

问题描述

我有一个类似的输入

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

• 从左到右计算，逐个编号
• 数字是 0 到 99
• 加法前的乘法被忽略，所以 14 + 2 * 32 是 512
• 可能的计算是+-*/
• 除以 0 是不可能的，所以在 / 之后不能是 0
• the calculation is from left to right, number by number
• the numbers are 0 to 99
• multiplication before addition is ignored so 14 + 2 * 32 is 512
• the possible calculations are +-*/
• division by 0 is not possible so after a / can't be a 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");
    }
}

我需要最快的方法来获得结果.

I need the fastest way to get a result.

问题:有没有办法让这个计算更快?我有多个线程，但我只使用一个.

Question: is there a way to make this calculation faster? I have multiple threads but I use only one.

更新:

测试用例:(我已经删除了除以 0 的错误并从 StopWatch 测量中删除了 StringBuilder.ToString())

Test-Case: (I've removed the division by 0 bug and removed the StringBuilder.ToString() from the StopWatch measurement)

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();

推荐答案

以下解决方案是有限自动机.计算(输入)= O(n).为了获得更好的性能，此解决方案不使用 IndexOf、Substring、Parse、字符串连接或重复读取值(获取 input[i]不止一次)...只是一个字符处理器.

The following solution is a finite automaton. Calc(input) = O(n). For better performance, this solution does not use IndexOf, Substring, Parse, string concatenation, or repeated reading of value (fetching input[i] more than once)... just a character processor.

    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%.

---

And another implementation. It reads 25% less from the input. I expect that it has 25% better performance.

    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;
    }

<小时>

我又实现了一个变体:

---

I implemented one more variant:

    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;
    }

抽象点的结果:

• 计算 1 230
• 计算 2 192
• 计算 3 111

这篇关于解决链式计算的最快方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！