在我公司的代码中,他们使用double.tryParse(),虽然很好,但为我们的需求设置了过多的安全性。由于有时我们不得不解析数十亿个字符串,因此我想出了这段代码,该代码要快一点(10%),但是我感觉它并不是处于最佳状态……不幸的是,这种东西需要更多的知识比我有。

private static double GetDoubleValue(string input)
{
    double n = 0;
    int decimalPosition = input.Length;
    bool separatorFound = false;
    bool negative = input[0] == '-';
    for (int k = (negative ? 1 : 0); k < input.Length; k++)
    {
        char c = input[k];

        if (c == '.' || c == ',')
        {
            if (separatorFound)
                return Double.NaN;
            decimalPosition = k + 1;
            separatorFound = true;
        }
        else
        {
            if (!char.IsDigit(c))
                return Double.NaN;
            n = (n * 10) + (c - '0');
        }
    }
    return ((negative ? -1 : 1) * n) / CustomPow(10, input.Length - decimalPosition);
}

private static double CustomPow(int num, int exp)
{
    double result = 1.0;
    while (exp > 0)
    {
        if (exp%2 == 1)
            result *= num;
        exp >>= 1;
        num *= num;
    }
    return result;
}


评论

我注意到您没有解析指数形式的双精度数,也没有解析无限数,依此类推。这是故意的吗?

@EricLippert是的,我的输入数据是一个实数(一个无穷大的概念)或一个错误(例如一堆字母或格式错误的数字)

如果您确实想获得更高的性能,则可以尝试进行分支/分支预测。自定义的返回语句可能会减慢您的速度,因此您可以尝试在循环内将错误变量设置为true,但在以后继续解析并返回错误...分支预测,指令流水线化和缓存可以为简单的操作带来奇迹循环具有巨大的迭代次数,因此您可以在那儿尝试一下...

您应该看一下我的答案,我现在已将输出删除为两倍,以确保不会引入任何浮动错误。我现在使用2个长变量。

这个问题本来也可以打高尔夫球的:)

#1 楼

命名

避免使用单字母或缩写形式的变量名。变量名称上的多余字符是免费的,并且对于维护程序员来说是一个奇迹。

例如



double n = 0;


此外,我没有以GetDoubleValue的名称出售。此方法决不会从任何地方检索值。此方法的作用是转换,因此应适当地这样命名。

Var

在定义局部变量的地方定义局部变量时使用var关键字类型明显。这样看起来更整洁,并节省了重构期间更改类型的时间。 >
double output = 0;


声明varforeach循环迭代器时也应使用for

例如

bool separatorFound = false;


应该be:

var separatorFound = false;


大括号

对于if语句主体始终使用大括号。它更清洁,意图更明确,以后您决定在身体上添加多余线条时,它会更快。

例如

for (int k = (negative ? 1 : 0); k < input.Length; k++)


应该是:

for (var k = (negative ? 1 : 0); k < input.Length; k++)


设计

为什么当您真正要做的就是反复乘以10时,为什么创建了函数CustomPow?除非您也打算在其他地方使用该方法,否则这似乎是过度抽象的情况。

为什么将GetDoubleValue设为私有?这听起来像是一个有用的功能,您可能想在其他地方或其他项目中使用。我怀疑它是私有的,因为它属于它不属于的类,并且您不希望有人调用StringLoader.GetDoubleValue或类似的东西。

将其放在实用程序类或扩展方法中,作为您的字符串加载器类的方法或其他方法,这没有任何意义。

评论


\ $ \ begingroup \ $
这在很多方面都是一个不错的答案!关于性能的任何想法...?
\ $ \ endgroup \ $
–托马斯·阿尤布(Thomas Ayoub)
15年1月6日在12:09

\ $ \ begingroup \ $
为了提高性能,我建议您先加入Visual Studio的分析器,它可以帮助您了解大部分处理时间都花在了哪里。如果您将结果放在这里,我们将能够为您提供更好的帮助。
\ $ \ endgroup \ $
–尼克·乌德尔(Nick Udell)
2015年1月6日,12:13

\ $ \ begingroup \ $
关于局部变量的名称,我发现名称多久也很重要,这就是为什么在代码混淆后您可以看到更快的速度,所有变量名称都更改为a,b,c,d,等等长参数名称与速度无关紧要。
\ $ \ endgroup \ $
–Fredou
2015年1月6日15:26

\ $ \ begingroup \ $
不,不是这样的:stackoverflow.com/questions/2443164/…编译器还是会剥离变量,因此您应该使用尽可能多的字符来获取信息。
\ $ \ endgroup \ $
–尼克·乌德尔(Nick Udell)
2015年1月6日15:28

\ $ \ begingroup \ $
我同意OP决定使用私有静态函数而不是实用程序类的公共成员的决定。这种优化趋向于紧密地集中在一起,因此可能不需要在多个地方使用。由于涉及的优化并不总是安全的(无法处理double.Parse和double.TryParse可以正确处理的各种情况),因此仅应在OP认为绝对必要的特殊情况下使用它。
\ $ \ endgroup \ $
–布赖恩
2015年1月7日14:07

#2 楼

Nick的答案非常适合样式点,我只是想让您意识到实现中的错误:

char.IsDigit(c)对于非西方阿拉伯数字(0 1 2 3 4 5)的数字将返回true 6 7 8 9)。它晦涩难懂,但会导致程序失败。例如。

var answer = GetDoubleValue("12345०7.56"); // DEVANAGARI DIGIT ZERO
// answer = 1258087.56 


您仅假设0-9(c - '0'),所以您应该只允许它们使用。即将

if (!char.IsDigit(c))
    return Double.NaN;

更改为

if (c < '0' || c > '9')
{
    return Double.NaN;
}


我也添加了括号,因为我更喜欢。 >
编辑:

修改为不使用char.IsDigit,可将执行时间削减约1%(里程可能会有所不同)。

进一步编辑:

偶然在Debug上进行了速度比较测试。在没有调试器的情况下在Release上运行,在5次运行中平均进行了1000万次迭代:

使用char.IsDigit-311ms
使用c < '0' || c > '9'-287ms

评论


\ $ \ begingroup \ $
太酷了:),但是仍然没有性能优化
\ $ \ endgroup \ $
–托马斯·阿尤布(Thomas Ayoub)
2015年1月6日,12:49

\ $ \ begingroup \ $
您可以执行诸如优化CustomPow的exp arg的计算之类的事情,这对Debug有所不同,但在Release中,无论如何它的外观都得到了优化。
\ $ \ endgroup \ $
– RobH
2015年1月6日在13:14



\ $ \ begingroup \ $
(c ^'0')> 9应该比c <'0'||快20% c>'9',因为分支预测错误(比较越少越好,char.IsDigit对每个非unicode数字进行约3个比较)
\ $ \ endgroup \ $
– Slai
17年1月13日在15:18

\ $ \ begingroup \ $
@Slai您测试了吗?对于格式正确的数字,分支始终为假,这对于预测是理想的。
\ $ \ endgroup \ $
– RobH
17年1月13日在16:46



\ $ \ begingroup \ $
@RobH我只是在为这个答案测试stackoverflow.com/a/41639665/1383168,它只有十进制数字。
\ $ \ endgroup \ $
– Slai
17年1月13日在16:58

#3 楼

您可以尝试仅通过一次预先计算一些/所有可能的值来优化CustomPow(int num, int exp)

double[] pow10 = new double[309];

double p = 1.0;
for ( int i = 0; i < 309; i++ ) {
  pow10[i] = p;
  p = p * 10;
}


然后CustomPow10( int exp )只会返回pow10[exp]

编辑:

顺便说一句,我看到您基本上是首先构建一个整数表示形式(在n中)。 -为什么不将n声明为long整数?这将在大多数时间以整数进行操作,该整数应比浮点数快,并且仅在最后,当最终除以10的幂时,需要一个浮点数。

Edit2 :仅当您输入的所有数字均少于18位时,此方法才有效,因为这是long可以代表的最大数字。

Edit3:请参阅@Fredou的回答以获取共同努力的结果。我认为他的代码到现在将表现非常好。

评论


\ $ \ begingroup \ $
因为exp永远不会(在我的情况下)高于7,所以我在for循环的地方使用了带乘法的switch语句
\ $ \ endgroup \ $
–托马斯·阿尤布(Thomas Ayoub)
2015年1月7日,9:18

\ $ \ begingroup \ $
您实际上想存储倒数(pow10 [i] = 1 / p;),以便乘(快)而不是除(慢)。
\ $ \ endgroup \ $
–加布
15年1月8日在7:07

#4 楼

此示例包含@nick和@RobH的样式建议以及性能增强,即使用按位AND运算而不是模运算。

private static double GetDoubleValue(string input)
{
    double output = 0;
    int inputLength = input.Length;
    int decimalPosition = inputLength;
    var hasSeperator = false;
    var isNegative = input[0] == '-';

    for (int k = (isNegative ? 1 : 0); k < inputLength; k++)
    {
        char currentCharacter = input[k];

        if (currentCharacter == '.' || currentCharacter == ',')
        {
            if (hasSeperator)
            {
                return Double.NaN;
            }
            else
            {
                hasSeperator = true;
            }

            decimalPosition = k + 1;
        }
        else
        {
            var digitValue = currentCharacter - '0';

            if (digitValue < 0 || digitValue > 9)
            {
                return Double.NaN;
            }

            output = (output * 10) + digitValue;
        }
    }

    var powDividend = CustomPow(10, inputLength - decimalPosition);
    var integer = ((isNegative ? -1 : 1) * output);

    return integer / powDividend;
}

private static double CustomPow(int num, int exp)
{
    double result = 1.0;

    while (exp > 0)
    {
        if ((exp & 1) == 1)
        {
            result *= num;
        }

        exp >>= 1;
        num *= num;
    }

    return result;
}


评论


\ $ \ begingroup \ $
好吧,我建议您对此有所了解,我也感到惊讶!
\ $ \ endgroup \ $
–托马斯·阿尤布(Thomas Ayoub)
2015年1月6日在13:43



\ $ \ begingroup \ $
我无法复制本文的性能结果。在我的测试环境中,无论是在调试模式下还是在发布模式下,按位运算总是快于模运算符。
\ $ \ endgroup \ $
– kerem
2015年1月6日在13:46



\ $ \ begingroup \ $
然后我将对其进行测试:)
\ $ \ endgroup \ $
–托马斯·阿尤布(Thomas Ayoub)
2015年1月6日下午13:47

\ $ \ begingroup \ $
通过将pow计算为0.1、0.01,...并乘以查找来节省一些时间呢?在许多系统上,相乘比相除要快。
\ $ \ endgroup \ $
– Falco
15年1月7日在10:21

\ $ \ begingroup \ $
查看intel.com/content/www/us/en/architecture-and-technology/…我发现,在当前的Intel CPU上,FDIV大约为39个时钟周期,而FMUL仅需要1个时钟周期。潜在地每个节省38个CPU周期。数字,对于十亿个数字@ 3.8 GHz乘法,与除法运算相比,总共可以节省10秒的CPU时间。
\ $ \ endgroup \ $
– JimmyB
2015年1月7日,11:02

#5 楼

关于您的算法的两条评论:

请注意,您的算法可能会在边界情况下引入错误,例如解析为"1.00000000000000000000000000000000"Infinity或解析为"1.0000000000000000"5333562.5371386623(!)。

特别是第二种行为是由CustomPow函数中的错误引起的,该函数使num保持为int,对于16以上的指数很容易溢出(CustomPow(10, 16)返回1874919424)。像GetDoubleValue("1." + new string('0', 310))这样的临界情况返回Infinity。 (请注意,Fredou的解决方案在这里更糟,它死于IndexOutOfRangeException。)

(问题在于,您在编写整数时不考虑小数点分隔符,因为小数点分隔符可能会在最终除法之前溢出。)

改进的算法也具有更好的性能(根据我的实验,比您的原始算法好约30%,比弗雷杜的算法好约20%):

private static double QuickDoubleParse(string input)
{
    double result = 0;
    var pos = 0;
    var len = input.Length;
    if (len == 0) return Double.NaN;
    char c = input[0];
    double sign = 1;
    if (c == '-')
    {
        sign = -1;
        ++pos;
        if (pos >= len) return Double.NaN;
    }

    while (true) // breaks inside on pos >= len or non-digit character
    {
        if (pos >= len) return sign * result;
        c = input[pos++];
        if (c < '0' || c > '9') break;
        result = (result * 10.0) + (c - '0');
    }

    if (c != '.' && c != ',') return Double.NaN;
    double exp = 0.1;
    while (pos < len)
    {
        c = input[pos++];
        if (c < '0' || c > '9') return Double.NaN;
        result += (c - '0') * exp;
        exp *= 0.1;
    }
    return sign * result;
}


该算法分别解析积分部分和小数部分。我也尝试过使用unsafe功能来实现它,但是改进尚无定论,但是您可以尝试:

private unsafe static double UnsafeQuickDoubleParse(string input)
{
    double result = 0;
    var len = input.Length;
    if (len == 0) return Double.NaN;
    double sign = 1;
    fixed (char* pstr = input)
    {
        var end = (pstr + len);
        var pc = pstr;
        char c = *pc;
        if (c == '-')
        {
            sign = -1;
            ++pc;
            if (pc >= end) return Double.NaN;
        }

        while (true) // breaks inside on pos >= len or non-digit character
        {
            if (pc >= end) return sign * result;
            c = *pc++;
            if (c < '0' || c > '9') break;
            result = (result * 10.0) + (c - '0');
        }

        if (c != '.' && c != ',') return Double.NaN;
        double exp = 0.1;
        while (pc < end)
        {
            c = *pc++;
            if (c < '0' || c > '9') return Double.NaN;
            result += (c - '0') * exp;
            exp *= 0.1;
        }
    }
    return sign * result;
}


评论


\ $ \ begingroup \ $
好一个!在我的数据中,exp永远不会大于7,我不会处理大数
\ $ \ endgroup \ $
–托马斯·阿尤布(Thomas Ayoub)
2015年1月7日13:21

\ $ \ begingroup \ $
请注意,数字的绝对大小无关紧要,仅取决于字符串的长度。我的示例全部等于1,只是以回旋的方式编写,并带有许多小数位。
\ $ \ endgroup \ $
–莫尔梅吉尔
2015年1月7日下午13:31

\ $ \ begingroup \ $
我认为您的算法存在四舍五入问题,如果您在答案中使用我的主要代码并将我的解析替换为解析,则会出现如下所示的错误:输入:78.1784928767842输出:78.1784928767841,输入:87.5688321364898输出:87.5688321364897 ,输入:-68.6253328195891 -68.625332819589,等等。
\ $ \ endgroup \ $
–Fredou
2015年1月7日15:01

\ $ \ begingroup \ $
@Thomas,不要忘记对我的答案或其他答案进行质量检查,以确保正确输入。
\ $ \ endgroup \ $
–Fredou
2015年1月7日在15:05



\ $ \ begingroup \ $
由于浮点数不精确,该算法确实存在舍入问题。每次计算结果+ =(c-'0')* exp都会引入更多的错误。
\ $ \ endgroup \ $
– RobH
2015年1月7日在16:28

#6 楼

我更改了if逻辑以删除一些分支,我认为您可以在您这一边进行测试吗? ,仅当返回最终结果时。 br />
using System;

namespace ConsoleApplication1
{
    class Program
    {
        private readonly static double[] pow10Cache;
        static Program()
        {
            pow10Cache = new double[309];

            double p = 1.0;
            for (int i = 0; i < 309; i++)
            {
                pow10Cache[i] = p;
                p /=  10;
            }
        }

        private static double GetDoubleValue(string input)
        {
            long inputLength = input.Length;
            long digitValue = long.MaxValue;
            long output1 = 0;
            long output2 = 0;
            long sign = 1;
            double multiBy = 0.0;
            int k;

            //integer part
            for (k = 0; k < inputLength; ++k)
            {
                digitValue = input[k] - 48; // '0'

                if (digitValue >= 0 && digitValue <= 9 )
                {
                    output1 = digitValue + (output1 * 10);
                }
                else if (k == 0 && digitValue == -3 /* '-' */)
                {
                    sign = -1;
                }
                else if (digitValue == -2 /* '.' */ || digitValue == -4 /* ',' */)
                {
                    break;
                }
                else
                {
                    return Double.NaN;
                }
            }

            //decimal part
            if (digitValue == -2 /* '.' */ || digitValue == -4 /* ',' */)
            {
                multiBy = pow10Cache[inputLength - (++k)];

                for (; k < inputLength; ++k)
                {
                    digitValue = input[k] - 48; // '0'

                    if (digitValue >= 0 && digitValue <= 9)
                    {
                        output2 = digitValue + (output2 * 10);
                    }
                    else
                    {
                        return Double.NaN;
                    }
                }

                multiBy *= output2;
            }

            return sign * (output1 + multiBy);
        }

        static void Main(string[] args)
        {
            Console.Write("Preparing values to test ");
            var rnd = new Random(42);
            var test = new string[10000000];
            double value;
            for (int i = 0; i < 10000000; ++i)
            {
                value = rnd.NextDouble() * 10000;
                value *= value;
                value += rnd.NextDouble();
                value *= (i % 2) == 0 ? 1 : -1;

                test[i] = value.ToString();

                if ((i % 1000000) == 0)
                {
                    Console.Write(".");
                }
            }

            Console.WriteLine(" benchmarking them");
            for (int a = 1; a < 5; ++a)
            {
                var sw = System.Diagnostics.Stopwatch.StartNew();
                for (int i = 0; i < 10000000; ++i)
                {
                    GetDoubleValue(test[i]);
                }
                sw.Stop();
                Console.WriteLine("Run {0} took {1}ms",a,sw.ElapsedMilliseconds);
            }

            bool anyError = false;
            int errorCount = 0;
            Console.Write("Any error? ");
            for (int i = 0; i < 10000000; ++i)
            {
                if (!string.Equals(GetDoubleValue(test[i]).ToString(), test[i]))
                {
                    if (!anyError)
                    {
                        Console.WriteLine(" Yes");
                        anyError = true;
                    }

                    errorCount++;
                    Console.WriteLine("{0} = {1} = {2}", GetDoubleValue(test[i]), test[i], string.Equals(GetDoubleValue(test[i]).ToString(), test[i]));
                    if (errorCount >= 10)
                    {
                        break;
                    }
                }
                if ((i % 1000000) == 0)
                {
                    Console.Write(".");
                }
            }

            Console.WriteLine(" {0}", anyError ? "" : "No");

            Console.ReadKey();
        }
    }
}


评论


\ $ \ begingroup \ $
如果您使用查找表-为什么仍在使用除法?乘法通常更快-因此您应该在数组中保存0.1、0.01,...并乘法!
\ $ \ endgroup \ $
– Falco
2015年1月7日,9:28

\ $ \ begingroup \ $
@Falco,我进行了更改,它确实有所帮助。
\ $ \ endgroup \ $
–Fredou
2015年1月7日14:51

\ $ \ begingroup \ $
@Fredou是否可以尝试检查是否将double输出更改为0.0?到int输出= 0;有所作为?
\ $ \ endgroup \ $
– JimmyB
2015年1月7日在17:19

\ $ \ begingroup \ $
@Falco我在32位(anycpu)下进行所有测试:-)在64位下进行测试会改变:-)
\ $ \ endgroup \ $
–Fredou
2015年1月8日14:04

\ $ \ begingroup \ $
@Falco,我更新了代码,现在我认为它比以前更好
\ $ \ endgroup \ $
–Fredou
2015年1月8日14:57

#7 楼

很抱歉,我没有足够的时间来编写所有内容并进行基准测试,所以这里只是一些想法:

一些获得更高性能的方法: >如果要将数百万个String转换为double,请使用C#并行执行机制。处决都是独立的,所以在四核,你应该大致保存在一个核心的您的执行时间的70%
操作的优化:由于分析主要归结为被执行很多时候你可以一个非常基本的循环尝试对处理器体系结构进行微优化。乘法通常比除法快。增补甚至更快的变化是最快的
流水线/分支预测:你平时处理器作为尝试许多指令尽可能重叠,如果它们不依赖于对方。如果您有分支机构,则分支预测器会尝试预测结果,如果错误,通常会导致很大的性能损失。在一个循环中,如果变量在一次迭代中编写并在下一次迭代中读取,则会遇到瓶颈。但是现代处理器甚至可以做一些花哨的事情,例如将结果从一个计算直接传递到下一个。

因此可能会加快整个过程的速度是消除因变量的复杂分支。如果有时间的话,代码将随之而来...

#8 楼


似乎没有人提到过这个问题。包含句点或逗号的内容可以解析为双精度。


似乎这是一种过度抽象的情况,除非您也打算在其他地方使用该方法。




我错了,但这是因为不清楚发生了什么。为什么不清楚?缺少括号。






















括号会使您立即清楚地知道自己正在返回,而不仅仅是让代码偶然绊倒。哎呀,即使在return语句后添加新行也可以解决此问题。在您的方法中传递一些可能会破坏它的奇怪字符串。

您绝对不会认为很多文化都使用空格作为分隔符而不是逗号。我不知道正确的方法来做您要尝试的事情,但我坚信事实并非如此。确保您正在考虑可能会破坏您的方法的字符串”。你绝对不是。事实证明,您根本没有考虑组分隔符。你可能应该是。这些毕竟是字符串。这些数字的格式可能与人们所写的一样。以下所有字符串格式的数字都会破坏您的代码。


if (c == '.' || c == ',')



评论


\ $ \ begingroup \ $
好吧,如果(!char.IsDigit(c))返回Double.NaN,我就得到了这段代码。这将杀死您的短语:p但空格分隔符+1! (我不会考虑,因为它不在我的数据中)
\ $ \ endgroup \ $
–托马斯·阿尤布(Thomas Ayoub)
2015年1月7日在8:16



\ $ \ begingroup \ $
啊,你是对的。我忽略了这一点。可能是因为那里没有括号...请稍等片刻,将更新我的答案。
\ $ \ endgroup \ $
–RubberDuck
15年1月7日,11:05

\ $ \ begingroup \ $
他接受句点或逗号作为小数点,而不接受组分隔符-他的代码完全不支持组分隔符。
\ $ \ endgroup \ $
–Random832
15年1月7日在20:59

\ $ \ begingroup \ $
@ Random832并不意味着像“ 200,123.45”这样的字符串会破坏代码?
\ $ \ endgroup \ $
–RubberDuck
2015年1月7日在22:48

\ $ \ begingroup \ $
@RubberDuck是的。他显然没有任何类似的字符串。显然,这是专门针对特定数据集而不是常规的解析函数。老实说,令我感到惊讶的是,他不愿意处理所有可能的小数点。
\ $ \ endgroup \ $
–Random832
2015年1月8日在16:05