网站 框架图,公众号开发者权限哪里添加,二级分销小程序,临沂经开区建设局网站本文Github地址#xff1a;CSharp-MathOptimization.md
华为公司的C语言编程规范在开头就强调了#xff1a; 一般情况下#xff0c;代码的可阅读性高于性能#xff0c;只有确定性能是瓶颈时#xff0c;才应该主动优化。 本文讲述的方法没有经过大项目和大公司的检验…本文Github地址CSharp-MathOptimization.md
华为公司的C语言编程规范在开头就强调了 一般情况下代码的可阅读性高于性能只有确定性能是瓶颈时才应该主动优化。 本文讲述的方法没有经过大项目和大公司的检验所以请批判性地阅读本文。本文中的大部分结论有测试代码支持参见SpeedTest.cs. 虽然C#的编译器会在release版本中执行一些优化C#的运行时也有一些优化但偶尔会遇到debug版本正常而release版本异常的问题比如我在github上fork了已停止维护的屏幕录像软件Capturadebug模式能启动release版本无法启动我短时间内解决不了这个问题如果要发布只能发布debug版本。所以手工执行一些虽然编译器(在release版本中)会做但也简单易读的优化还是有意义的。同时建议把未经优化的代码作为注释附在旁边提高可读性。
1). const, readonly, in 这3个关键词在能用的地方要尽量用。这样可以让编译器执行更激进的优化策略同时提高代码的安全性、可读性和可维护性。
2). 正整数乘以或除以 2 n 2^n 2n (n也是整数)使用移位来代替。但对乘以非 2 n 2^n 2n 的整数不要使用此方法比如不要把 i * 12 改写成 (i 2 i 3). 对于负整数的乘除运算也不要用移位否则代码可读性很差也容易出错。对于int型整数除法耗时是乘法的13倍是移位的17倍。对于long型整数除法耗时是乘法的1.4倍是移位的9.8倍。(数据来源)
3). 除以浮点型常数的除法改写为乘以这个数的倒数。比如把 x / 2.0 改写为 x * 0.5 .对于条件语句if(a/b c)可以改写为if( (b 0 a b * c) || (b 0 a b * c) ). 对于某些有很多分数嵌套的数学公式请先进行恒等变形只保留最长的一条分数线其它的分数一律去掉分母除法变成乘法。例如 ( 1 a 2 k 2 b 2 ) x 2 2 k m b 2 x m 2 b 2 − 1 0 \left(\frac{1}{a^{2}}\frac{k^{2}}{b^{2}}\right)x^2\frac{2km}{b^{2}}x\frac{m^{2}}{b^{2}}-10 (a21b2k2)x2b22kmxb2m2−10 x 1 x 2 − 2 k m b 2 1 a 2 k 2 b 2 − 2 a 2 k m b 2 a 2 k 2 x_1x_2-\frac{\frac{2km}{b^{2}}}{\frac{1}{a^{2}}\frac{k^{2}}{b^{2}}}-\frac{2a^{2}km}{b^{2}a^{2}k^{2}} x1x2−a21b2k2b22km−b2a2k22a2km x 1 x 2 m 2 b 2 − 1 1 a 2 k 2 b 2 ( m 2 − b 2 ) a 2 b 2 a 2 k 2 x_1x_2\frac{\frac{m^2}{b^{2}}-1}{\frac{1}{a^{2}}\frac{k^{2}}{b^{2}}}\frac{\left(m^{2}-b^{2}\right)a^{2}}{b^{2}a^{2}k^{2}} x1x2a21b2k2b2m2−1b2a2k2(m2−b2)a2 因为浮点除法的耗时是浮点乘法耗时的13倍。(数据来源)
4). 除非测试结果表明使用float型比double型更快或者因为数据量巨大float型比double型显著节省空间否则都应该使用double型浮点数。因为float型的计算速度有时比double更慢而且float型的精度太差可能带来一些难以察觉的bug比如 for(float i 0.0f; i 20000000; i) 就是一个难以察觉的死循环当 i 达到 2 24 2^{24} 22416777216 时会由于float的精度太低无法区分 16777216 和 16777217即无法自增1. 另外使用float型所有的字面量都要加 f 后缀所有的Math库函数前面都要加(float)进行强制类型转换(或者使用MathF库中的函数)写起来麻烦看起来丑陋所以要尽量避免。在以下情形(但不限于)可考虑使用float型 * 训练AI模型数据量巨大但对计算精度要求不高float型可显著节省存储空间。 * 程序要在32位处理器上运行或者要在没有硬件浮点单元的处理器上运行。 * 需要使用SIMD技术加速使用float型可以在一条指令中处理两倍于double型的数据。
5). 如需计算 x n x^n xn 当 n2,3 时不要使用Math.Pow(x,n), 而是直接写成 x * x 和 x * x * x. 当 n 2 k ( k ∈ N ) n2^k(k\in N^) n2k(k∈N) 时可用yx, 再执行k次 y*y 来代替。当 n 取其它值时才可调用Math.Pow.
6). 引入一些额外的变量来存储函数调用的结果或者复杂运算过程中的子过程的值避免重复调用和计算。比如计算二维坐标旋转: x1 x * cos(a) - y * sin(a) y1 x * sin(a) y * cos(a)同一个角的正弦和余弦值都要使用两次。一元二次方程求根 Δ 2 a \frac{\sqrt{\Delta}}{2a} 2aΔ 会使用两次。二元一次方程求根系数矩阵的行列式值会使用两次。在循环中如果要以同样的参数调用某个函数或者有一些不随循环变化的子过程则应提到循环外部用变量存储。
7). 对浮点数进行取整操作时如果确定浮点数的大小不超出int(或long)型的范围以及不会出现NaN则可以用强制类型转换结合条件语句替代Floor、Ceiling和Round函数显著提高速度。使用 (int)(t ± 0.5) 来代替Math.Round(t)则需谨慎因为当t的小数部分为0.5时Round(t)的结果取决于中点值舍入模式的设定默认是MidpointRounding.ToEven即向最近的偶数舍入。其它模式还有ToZero, AwayFromZero, ToNegativeInfinity, ToPositiveInfinity. 要根据不同的舍入模式选择不同的替代写法。 // 替代 a (int)Math.Floor(t)a (t 0 ? (int)t - 1 : (int)t);// 替代 b (int)Math.Ceiling(t)b (t 0 ? (int)t : (int)t 1);// 替代 c (int)Math.Round(t, MidpointRounding.ToZero)c (t 0 ? (int)(t - 0.5) : (int)(t 0.5));8). 对于Array of Struct(AoS)和Struct of Array(SoA)两种数据结构 内存布局 AoS每个结构体实例的所有字段在内存中是连续存储的。 SoA每个字段的所有值在内存中是连续存储的但不同字段的值分开存储。性能 AoS在需要频繁访问单个结构体实例的所有字段时性能较好。 SoA在需要频繁访问所有实例的单个字段时性能较好特别是在SIMD(单指令多数据)优化中表现更佳。 对于有限元程序需要存储大量节点的编号、坐标和位移需要视情况选择AoS或SoA.
9). 对于较小的结构体可以考虑用ref struct代替struct强制结构体存储在栈上(注意防范栈溢出)避免装箱操作同时减少垃圾回收的性能损失。
10). 对于局部变量使用 SpanT, ReadOnlySpanT 和 stackalloc 在栈上分配连续的小段内存(注意防范栈溢出)比使用数组(存储在堆上)速度更快。
11). 对于分支较多的流程优先使用模式匹配而不是大量的if else既能提高程序可读性又能提高运行速度。比如分段函数就应该使用模式匹配。 static double Foo(double x) x switch{ 0 -x, // 当 x 0 时f(x) -x 0 and 1 x * x, // 当 0 x 1 时f(x) x^2 1 and 2 2 * x, // 当 1 x 2 时f(x) 2x 2 x 1, // 当 x 2 时f(x) x 1_ throw new ArgumentOutOfRangeException(nameof(x), Invalid input)};12). 尽量避免编写含递归调用的函数。比如阶乘函数 n!递推数列(斐波那契数列、汉诺塔问题等)二分查找等均可以用循环替代递归。
13). 对于那些参数的允许范围比较小的函数优先考虑用查表法实现。比如阶乘函数 n!因为阶乘函数增长太快在大多数情况下阶乘函数允许的参数的范围很小 13 ! 6227020800 2 32 − 1 4294967295 13! 6227020800 2^{32}-1 4294967295 13!6227020800232−14294967295 uint.MaxValue 21 ! 5.109 × 1 0 19 2 64 − 1 1.845 × 1 0 19 21!5.109\times 10^{19} 2^{64}-1 1.845\times 10^{19} 21!5.109×1019264−11.845×1019 ulong.MaxValue 28 ! 3.049 × 1 0 29 2 96 − 1 7.923 × 1 0 28 28!3.049\times 10^{29} 2^{96}-1 7.923\times 10^{28} 28!3.049×1029296−17.923×1028 decimal.MaxValue 35 ! 1.033 × 1 0 40 2 128 3.403 × 1 0 38 35!1.033\times 10^{40} 2^{128} 3.403\times 10^{38} 35!1.033×104021283.403×1038 float.MaxValue 171 ! 1.241 × 1 0 309 2 1024 1.798 × 1 0 308 171!1.241\times 10^{309} 2^{1024} 1.798\times 10^{308} 171!1.241×10309210241.798×10308 double.MaxValue 至多占用171*8 1368Byte的存储空间就能满足double型计算的需求。不仅速度快而且没有多次浮点乘法带来的累积误差。 特殊情况下指数函数的自变量如果只能取正整数那么自变量的范围一般也不会很大比如 e 709 2 1024 e 710 e^{709} 2^{1024} e^{710} e70921024e710 那么可以考虑对不超过某一阈值的整数采用查表法超过该阈值则调用标准库。或者为自变量取等差数列时的函数值建立数表然后用少量运算就能得到0~709内任意整数的函数值(参见 https://zhuanlan.zhihu.com/p/5221342896 )。 二项式系数(组合数)和阶乘的自然对数ln(n!)可以采用部分查表法。 CRC(循环冗余校验)也经常使用查表法加速。
14). 小于255的素数(质数)一共有54个如下 static readonly byte[] PrimesLessThan255 [2, 3, 5, 7, 11, 13, 17, 19, 23,29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151,157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251];对正整数n进行素性测试时可以先用上表的素数进行试除(比使用255以内的奇数试除要快)若都不能整除就可以继续用从257到 n \sqrt{n} n 之间的奇数进行试除从257开始是因为253(11*23)和255都是合数。试除法是最简单但并不高效的素性测试方法比较高效的方法是 Miller-Rabin测试法。但因为绝大多数正整数都有一个不大的素因子比如88的正整数有一个小于100的素因子92的正整数有一个小于1000的素因子(数据来源 大数因子分解算法综述.刘新星)。大于255但不超过1024的素数有118个。同时根据素数定理不超过n的正整数中素数占的比例大致是1/ln(n). 因此构建一张比较大的素数表采用先除素数再除奇数的试除法对于不太大的整数是一种勉强能用的素性测试方法同时也是寻找素因子的方法。
15). 以e为底的指数函数有一种快速近似算法 public static double FastExp(double x) { long tmp (long) (1512775 * x 1072632447); return BitConverter.Int64BitsToDouble(tmp 32); }该方法的速度大致是Math.Exp的5倍原理参见《 A Fast, Compact Approximation of the Exponential Function》. 对于神经网络中的Sigmoid函数中的指数函数就可以采用这种近似算法。
16). 以e为底的对数函数有一种快速近似算法 public static double FastLn(double x) // 抛弃对x0的检查。{long longx BitConverter.DoubleToInt64Bits(x);double k (longx 52) - 1022.5; return k * 0.693147180559945309; }该方法实际上就是Math.Log的算法的前半部分用位运算提取了IEEE 754浮点数的阶码而抛弃了尾数的对数速度大致是Math.Log的4倍其中-1022.5 - 1023 0.50.693147……就是ln(2)该算法可以保证绝对误差不超过ln(2)/20.346573… 但该算法有一个不可忽视的弊端设 n 为正整数则对于区间 [ 2 n − 1 , 2 n ) [2^{n-1},2^n) [2n−1,2n) 内的任意实数该算法会返回完全一样的结果。以2为底或以10为底的对数函数也可以使用该方法把最后一行与k相乘的常数换掉即可以2为底就是return k以10为底就是return k*0.301029995663981196.
17). 免费的数学库推荐ALGLIB免费版收费的数学库推荐ALGLIB、ILNumerics和Dew.Math. 不推荐 MathNET Numerics其代码质量低下原因参见点评10多个C#的数学库.
18). 避免在循环中做以下事情 创建对象。使用try catch.打开和关闭同一个文件、数据库等。创建和断开对同一个URI的链接。 19). 避免不加测试地用Parallel.For代替for循环因为前者需要创建和管理多个线程会带来额外的开销。当循环次数太少或者单次循环所做的运算太简单时使用Parallel.For反而会降低性能而且很可能出现计算结果不正确的问题。比如函数f(x)在某个区间上做数值积分有sum f(xi)*dx这样的累加运算需要测试Parallel.For的耗时是否更短以及结果是否正确。又比如一些写不出通项公式的递推数列 a n 1 a n a n 1 a_{n1}a_n\sqrt{a_n}1 an1anan 1 每次循环都依赖上一次的结果注定无法并行此时禁止使用Parallel.For.
20). 考虑使用[SkipLocalsInit]属性省略CLR将方法中声明的所有局部变量初始化为其默认值的操作提高速度。注意此属性需要 AllowUnsafeBlocks 编译器选项同时要重点检查代码中是否存在访问未初始化的变量的行为。
21). 绝大多数时候矩阵求逆都是非必须的(而且计算代价很大的)除非就是要得到逆矩阵本身。比如对于线性方程组 A x b , x A − 1 b Axb,\ xA^{-1}b Axb, xA−1b 使用逆矩阵表达方程组的解只具有形式意义不可直接用于计算。请使用高斯消去法、LU分解法、Jacobi迭代法、Gauss-Seidel迭代法、Cholesky分解法等。矩阵的逆几乎不会单独出现几乎总是会和其它矩阵做乘法总有不求逆的替代方案。
22). 多项式求值优先使用秦九韶算法 a n x n a n − 1 x n − 1 ⋯ a 1 x a 0 ( ⋯ ( ( a n x a n − 1 ) x a n − 2 ) x ⋯ a 1 ) x a 0 a_nx^n a_{n-1}x^{n-1}\cdotsa_1xa_0 \\ (\cdots ((a_nxa_{n-1})xa_{n-2})x\cdotsa_1)xa_0 anxnan−1xn−1⋯a1xa0(⋯((anxan−1)xan−2)x⋯a1)xa0 对于阶数不太高的多项式(比如小于10阶)不要使用循环语句来实现这个算法而应该手工进行循环展开。还可以使用融合乘加指令Fma.MultiplyAdd进行进一步加速。秦九韶算法是一个串行的算法无法并行。如果某个n次多项式的全部根均为实数(设为 x 1 x_1 x1 , x 2 x_2 x2 , ⋯ \cdots ⋯ , x n x_n xn 需要提前计算出来)那就可以使用SIMD指令进行并行计算 a n ( x − x 1 ) ( x − x 2 ) ⋯ ( x − x n ) a_n(x-x_1)(x-x_2)\cdots (x-x_n) an(x−x1)(x−x2)⋯(x−xn)
23). 利用泰勒级数计算double型函数值时多项式阶数通常不应该超过17阶太高的阶数没有意义(因为浮点运算的累积误差)。泰勒级数具有局部性离展开点越远精度越差。所以如果要提高计算精度首先应考虑更换展开点而不是提高多项式的阶数。
24). 除非绝对必要(比如要求很高的精度或比long型更大的范围)否则不要使用decimal型变量因为其计算耗时是double的几十倍甚至百倍(decimal除法尤其缓慢)。
参考文章
Writing Faster Managed Code: Know What Things Cost新版C#高效率编程指南C#中那些举手之劳的性能优化
