尧惘宣的代码,目的是要解决很大的浮点数之间的乘法。
计算机能够高效表示有限位的小数,但任意精度的话,随场景对时间和空间效率重视程度的不同,也有不同的解决方案。
而他目前的算法,则是把小数拆成很多数位。
例如 114.514 和 0.07相乘,第一个数的第四位,是4 x 0.1, 第二个数只有一位,7 * 0.01。那么他们的最终贡献则是 28 x 0.001。
第一个数和第二个数中,所有对应数位如此相乘,最终贡献之和,则是大数乘法的结果。
然而,因为他用了一个大字符数组来表示最终输出的大浮点数,他其实每次都在把两个数位相乘的结果更新到这个大字符数组。
在这里,他犯了错——大字符数组里有小数点的位置,这里他的特判出了错。
可是,如果用上tuple,思路就很简单——整个求解会多出一个额外的阶段,实际上是解开了直接更新大字符数组时操作的耦合:
我们只用tuple来表示一个数位:
114.514这个数,表示为一串数位:
[(1, 2), (1, 1), (4, 0), (5, -1), (1, -2), (4, -3)]
而两个数位(a, b), (c, d)的相乘,结果则是
(a x c, b + d)。我们对他再做一定的拆分和合并,例如(28, -3)拆成(2, -2)和(8, -3), 而(2, 3), (1, 3)则合并为(3, 3)。
最终就可以得到一个数位串,里面的元素(a, b),都满足b各不相同,a均小于10。
这个数位串可以直接拿来填最终输出的大字符数组。
"你给我起来,本小姐给你写一下,一会儿自己理解理解。"
我催促着少年起身。
他有些无奈地站起来后,我随手搭到他肩上:
"学弟啊,你们这些小男生,是不是每天满脑子都——数 理 基 础——啊?"
感觉有点好玩,我故意让气息能够触碰到他的皮肤。
然后我看到他脸上出现了青筋。
"哼哼…"
我根本不虚,反而乐呵呵地笑了起来。
"前辈,你请。"
他冷静异常,无视我的捉弄,拉开我的手,把凳子让给了我。
我不满地嘟了下嘴,也不介意,开始码代码。
基本上也是秒掉。
我运行ac之后,并没有停下来。
在他疑惑的目光里,我给出了基于这份代码的两个变种。
首先,在最终数位串中不使用tuple, 程序性能提高了好几倍。
然后,再把原先的个位数乘法改成32位乘法,性能直接起飞。
后面这个算法,其实是把浮点数切割成连续n位(而不是1位),然后原来的
M(第一个数的总数位数) x N(第二个数的总数位数) 次乘法
变成了
M / n x N / n次乘法
在并非大整数时,性能直接逼近乘法指令。
"这个…好快…"
我未来的好兄弟有些痴了。
"男人不能只追求快。你看,先追求基本的模型,思路清楚了,优化也很简单。"
"谢谢…学姐"
他有点不好意思。
我见状,立马就想占 占他便宜。
我伸出手,把他往下一拉。
好吧没拉动。
讲道理大一我身体素质很过硬的啊…
想摸摸他脸的。
"学姐你干嘛…"
"过来让我摸摸帅学弟的脸…"
"你能不能自重一下!?"
"啊!"
我被他拉了起来,然后他坐了回去。
"哈?这么小气嘛?"
我不满地叫到,非常不良。
"你们俩吵什么?!"
阿姨冲我们这边喊。
我立刻萎了,低下头往回走。
但尧惘宣拉住了我。
"学姐,我叫尧惘宣… 你叫什么名字?"
我露出一个笑容,在旁边空的机位坐了下来,小声说:
"邵流空。"
"邵学姐,加个联系方式?"
"啊…好…"
我还有点不好意思。
貌似是qq... 然后我们又交换了手机号码…
淦,他好熟练啊!还是"学姐"身份的我居然被他carry了。
"你先慢慢看代码吧。不懂的可以继续问。"
我故作老成。
他看着我,突然微笑,"学姐你有点傻。"
我瞥了他一眼,不解气,又恶狠狠瞪了他一下,转身回到自己的机位。
原以为他会立刻和我qq聊,结果他马上看代码去了。
"不愧是你啊…"