代码挑战:你计算1000的速度有多快！使用Powershell

Question

我有一个计算1000的挑战！使用Powershell尽可能快。这里给出了这个代码挑战的规则：

• 没有预定义的数组或字符串(除了初始的0！-值(
• 不使用外部模块或嵌入式C#代码
• 例程对于从0到1000的任何输入都必须正确
• 结果字符串必须作为测量的一部分创建

基于这些条件，我可以创建以下代码片段作为初稿。有什么办法提高速度吗？非常欢迎输入！

cls
Remove-Variable * -ea 0
$in = 1000
$runtime = measure-command {

# define initial arr with 0! = 1:
$arr = [System.Collections.Generic.List[uint64]]::new()
$arr.Add(1)
if ($in -gt 1) {
# define block-dimension per array-entry:
$posLen = 16
$multiplier = [uint64][math]::Pow(10,$posLen)
# calculate faculty:
$start = 0
foreach($i in 2..$in) {
$div = 0
if ($arr[$start] -eq 0){$start++}
foreach($p in $start..($arr.Count-1)) {
$mul = $i * $arr[$p] + $div
$arr[$p] = $mul % $multiplier
$div = [math]::Floor($mul/$multiplier)
}
if ($div -gt 0) {$arr.Add($div)}
}
}
# convert array into string-result:
$max = $arr.count-1
$faculty = $arr[$max].ToString()
if ($max -gt 1) {
foreach($p in ($max-1)..0) {
$faculty += ($multiplier + $arr[$p]).ToString().Substring(1)
}
}
}
# check:
if ($in -eq 1000 -and !$faculty.StartsWith('402387260077') -or $faculty.length -ne 2568) {
write-host 'result is not OK.' -f y 
}
# show result:
write-host 'runtime:' $runtime.TotalSeconds 'sec.'
write-host "`nfaculty of $in :`n$faculty"

Answer 1

最快的方法是依赖专门为大整数设计的数据类型的现有乘法功能，如[bigint]:

$in = 1000
$runtime = Measure-Command {
# handle 0!
$n = [Math]::Max($in, 1)
$b = [bigint]::new($n)
while(--$n -ge 1){
$b *= $n
}
}
Clear-Host
Write-Host "Runtime: $($runtime.TotalSeconds)"
Write-Host "Factorial of $in is: `n$b"

这给了我大约18ms的运行时间，与使用基于[uint64]的进位方法的大约300ms形成对比：(

正如Jeroen Mostert所指出的，您可以通过绕过*=运算符并直接调用[BigInt]::Multiply来获得额外的改进：

# change this line
$b *= $n
# to this
$b = [bigint]::Multiply($b, $n)

我相信所有的限制都得到了满足：

没有预定义的数组或字符串(除了初始的0！-值(

• 检查

不使用外部模块或嵌入式C#代码

• 检查！([bigint]是.NET基类库的一部分(

例程对于从0到1000 的任何输入都必须正确

• 检查

结果字符串必须作为测量的一部分创建

• 我们已经将结果作为整数进行跟踪，从而隐式存储字符串表示