【程序设计】5.6 [一把抓] 排序相关
5.6 排序相关
为了解决数字黑洞问题，我们已经写了好几种排序代码了。排序确实是很常见的动作，所以 SPL 直接提供了排序函数。
A.sort() 将返回将 A 的成员从小到大排列的序列。当然我们也会经常用到从大到小排序，使用 @z 选项就可以了。
排序函数返回成是序列原成员构成的序列，可以理解成某种选出函数，它也有个对应的定位函数，A.psort()将返回一个数列 p，使得 A(p) 是从小到大排列的。也就是说
A.sort()==A(A.psort())
请仔细理解一下这个等式的意义。
尝试一下，老规矩，A 列的运算结果就是 B 列的常数。
A |
B |
|
1 |
[13,30,45,23,42,98,61] |
|
2 |
=A1.sort() |
[13,23,30,42,45,61,98] |
3 |
=A1.sort@z() |
[98,61,45,42,30,23,13] |
4 |
=A1.psort() |
[1,4,2,5,3,7,6] |
5 |
=A1(A4) |
[13,23,30,42,45,61,98] |
有了排序函数，数字黑洞可以更简单了，不需要用 pseg 和 insert 倒腾了：
A |
B |
C |
D |
|
1 |
5 |
12345 |
=A1.run(~=if(#>1,~[-1]*10,1)) |
|
2 |
for |
=C1.(B1\~%10).sort() |
||
3 |
=C1.sum(B2(#)*~) |
=C1.sum(B2.m(-#)*~) |
||
4 |
=@|B1 |
>output(B1) |
>B1=B3-D3 |
|
5 |
if B4.pos(B1) |
break |
||
排序函数也支持有表达式的情况 A.sort(x)，但它不等于 A.(x).sort()，它是由 psort 定义的，即 A.sort(x)==A(A.psort(x))，而 A.psort(x) 则可以用 A.(x).psort() 来定义。
这和 maxp 的情况是一样的，这是选出函数和定位函数的共同特点，select 也是这样，即 A.select(x)==A(A.pselect@a(x))，而不是 A.(x).select()。
不过，SPL 没有提供与 A.max(x) 风格一致、可直接返回 A.(x).sort() 的函数，这个需求就只能用这个表达式计算，这是历史习惯造成的，早期程序语言都是这么设计 sort 函数的。
排序一般是用于获得一个整齐的次序，但也可用来打乱一个序列的次序。
A |
B |
|
1 |
=to(1000) |
=A1.sort(rand()) |
B1 的中的 rand() 函数在每次计算时会返回一个 0 和 1 之间的随机浮点数，随机的大小是乱的，那么排出来的次序也是乱的，结果原来很整齐的 A1 就被排成很乱的样子了。如果开发一个扑克游戏时，这个原理可以用来洗牌。
打乱次序的方法还可以用来抽样，比如要从 1 到 1000 的范围随机抽 100 个数，不能重复。简单地随机生成并不容易，如果发生了重复还要重新生成，比较麻烦。用上面这个排序方法就很简单，乱序后取前 100 个就行了。
A |
B |
|
1 |
=to(1000) |
=A1.sort(rand()).to(100) |
针对 rand() 函数多说几句，使用随机数用于生成测试数据是非常方便。但是，当测试时发现错误后，我们又希望能用同一套测试数据再跑一遍，以方便找出错误在哪里。然而，随机数就是会随机，再计算第二遍后又是另一批数了。
其实，计算机里并没有真正的随机数，而是在上一次生成的数进行一系列计算得出一个新数返回，当计算规则满足一些数学原理时，人就很难看出规律，而且也能保证算出来的数能均衡地分布在指定范围内，这种随机数称为伪随机数。只要第一个数确定了，再计算出来的数的序列都是确定的。
利用这个原理，我们就可以造出相同的“随机数”来了。
A |
B |
|
1 |
=rand@s(1) |
=100.(rand()) |
2 |
=100.(rand()) |
|
3 |
=rand@s(1) |
=100.(rand()) |
rand@s(s) 函数将把参数 s 设置为第一个随机数，称为种子。运行这段代码会发现，B1 和 B3 是一样的。
那么，如果每次执行程序开始时用到种子想关，那么生成的随机数序列不是都一样了吗？
不会的，程序启动时一般会自动执行一句类似 rand@s(long(now())) 这样的语句，now() 返回当时的时间，也就是用程序执行的起始时间作为种子，而这个是人操作出来的，有足够的随机性，这就能保证每次程序执行之前会得到不同的随机数序列了。
再回过头来看 psort，它并不是只用来把 sort 定义出来，它本身也有用处。考察这样一段代码：
A |
B |
|
1 |
=50.(1000+~) |
=A1.(rand(100)) |
2 |
=B1.psort@z() |
=A1(A2) |
B2 中的 rand(n) 表示返回一个 n 之内的随机整数。
将这里的 A1 看成一批学生的学号（其实应该用姓名，但要等我们学过字符串知识后才会，现在就先用整数当学号），B1 理解为这些学生的成绩，和 A1 的成员一一对应，现在我们希望得到这批学号按其对应成绩排序后的结果序列。
对 A1 去排序显然是没有用的，而对 B1 排序能排出成绩本身，却得不到学号的成绩排序，使用 psort 就可以解决这个问题了，现在 B2 就是我们想要的按成绩排序的学号序列。
在成员数很多的时候，整个序列的排序就很慢，而且常常并没有业务意义。比如有几万个商店的销售额，我们通常只关心前几名是谁以及有多少销售额，没有兴趣关心上千名甚至上百名之后的情况了。而只想得到前几名，就没有必要对整个序列做排序。
SPL 提供了 top 函数用于只出前几名，类似地也还有 ptop 函数，但和 sort 函数的语法规则有点不同。因为 top 函数有着和 max 函数对应的的三种情况：返回值的 max、定位函数 pmax 以及选出函数 maxp。
A |
B |
|
1 |
[13,30,45,24,42,98,61] |
|
2 |
=A1.ptop(3) |
[1,4,2] |
3 |
=A1.top(3) |
[13,24,30] |
4 |
=A1.ptop(3,~%10) |
[2,7,5] |
5 |
=A1.top(3,~%10) |
[0,1,2] |
6 |
=A1.top(3;~%10) |
[30,61,42] |
定位函数 A.ptop(n) 将返回最小的 n 个成员的位置，有参数时的 A.ptop(n,x) 定义为 A.(x).ptop(n)，这个类似 pmax，不难理解。而 A.top(n) 则可以定义为 A(A.ptop(n))，在无 x 参数时，它即是值也是成员，类比为 max 和 maxp 都可以，不会有歧义。但是，有 x 参数时，A.top(n,x) 被定义为 A.(x).top(n)，相当于 max，是针对值的。而选出函数则用 A.top(n;x) 来表示，注意其中是用来分隔参数的是分号而不是逗号，它和和 maxp 是对应的。
可能因为 topp 这个词实在不太好看而没有采用。这里的 n 不能省略，SPL 中也有大量用分号区分参数的情况（我们后面会再仔细讲），这样也就能区分开了。
总得来讲，SPL 中设计的函数风格还是比较一致的，各种不同运算之间容易类比。
