用PowerShell的管道

水木上一个算法题:

已知：
f(1) = {1}
f(2) = {1,2}
f(3) = {3,1,2}
f(4) = {2,3,1,4}
f(5) = {4,2,5,1,3}
f(6) = {3,6,2,4,1,5}
f(7) = {7,3,5,2,6,1,4}

求： f(8) = ?  f(n)=?，用程序实现之，时间复杂度要求O(n)。

这事上面例子的推导公式:

f(n) = ++f(n-1)[1..n-1] + 1 + f(n-1)[0]

f(n) 是 f(n-1) 列表中每一项自增一, 并将第一项移动到最后的过程.

PowerShell利用管道(非O(n)复杂度算法):

PS C:\> 9..3 | % {$i=,1; $r=1,2} { $r = @(1..$($r.count-1) | %{ $r[$_] + 1 }) + $i + ++$r[0] } {"$r"}
7 4 8 3 6 2 9 1 5

这里的技巧就是用 .. 和管道进行迭代操作, 可以避免我们使用循环结构. 请勿迭代超过1000的数值, 效率很差.

一个更加快速的算法, 现在唯一的开销就是搜索槽的开销. 性能还算不错, 我的机器上算3000的序列, 需要1s:

$len = 10; 1..$len | % {$a = New-Object System.Object[] $len; $pos = $len - 2} `

{ $a[$pos] = $_;

for ($i = 0; ($i -lt 2) -and ($_ -lt $len);) {

  if ($a[--$pos] -eq $null) { $i++; continue }

  if ($pos -lt 0) { $pos += $len }

}

} {"$a"}

 

最后的一个修改版本, 利用ArrayList类似链表的性质, 减少了搜索槽的不必要开销: 比上面的算法基本上快了1倍:

PS C:\> Measure-Command { $len = 20000; 1..$len | % {$a = New-Object System.Object[] $len;
>> $b = New-Object System.Collections.ArrayList $len;
>> 0..$($len-1) | %{ [void] $b.Add($_) };
>> $pos = $len - 2;
>> } `
>> {
>>     $a[$b[$pos]] = $_;
>>     [void] $b.RemoveAt($pos);
>>     if ($_ -lt $len) {
>>         $pos -= 2;
>>         while ($pos -lt 0) { $pos += $b.count }
>>     } `
>> } {"$a"}
>> }
>>

Days              : 0
Hours             : 0
Minutes           : 0
Seconds           : 3
Milliseconds      : 314
Ticks             : 33142915
TotalDays         : 3.83598553240741E-05
TotalHours        : 0.000920636527777778
TotalMinutes      : 0.0552381916666667
TotalSeconds      : 3.3142915
TotalMilliseconds : 3314.2915