性能优化技巧 - 位置利用

【摘要】

SPL 的特征之一是数据有序,适当地利用位置,可以显著提高性能。让我们先从一个典型场景开始,逐步掌握利用位置的各种技巧。

对排序后的数据进行二分查找,可以获得较高的性能,但有些算法需用到原始顺序,看上去似乎不该再排序。比如下面的案例:

PerformanceRanking.txt有三个字段,分别是empID(销售员编号)dep(部门名称)amount(销售额)。该文件记录着各部门各销售员本季度的业绩排名,已按销售额逆序存放,现在需根据指定的销售员ID,计算出:他应当再增加多少销售额,才能提高业绩排名。如果该员工已经是第1名,则无需增加销售额。

本算法需要用排名高一位的销售员的销售额,减去该销售员的销售额,即对原始数据做相对位置计算。既然要用到原始顺序,似乎就不该再排序,否则两者难以互转,而且其他算法可能用到原始数据。这种思路下会把脚本写成这样:


A

B

1

=file("PerformanceRanking.txt").import@t()

/读取数据

2

=A1.pselect(empID:10)

/不利用位置,按empID查询记录序号

3

=A1.calc(A2,if(#>1,amount[-1]-amount,0))

/在原始数据中做相对位置计算

上述脚本没有对数据排序,所以不能进行二分查找,性能不高。

事实上,我们可以在保留原始数据的前提下,利用位置进行排序,从而提高查询性能。脚本如下:


A

B

5

=oPos=A1.psort(empID)

/排序后记录在原数据中的位置

6

=index=A1(oPos)

/利用位置制造排序数据

7

=oPos(index.pselect@b(empID: 10))

/二分查找,获得序号

8

=A1.calc(A7,if(#>1,amount[-1]-amount,0))

/在原始数据中做相对位置计算

A5:函数psort只获得排序后记录在原数据中的位置,并不会对原数据真正排序。

A6:利用oPos制造一份排序后的数据。注意,此时原数据不受影响,而且oPos可以作为排序后数据index和原始数据之间互转的桥梁。

A7:对排序后的数据做二分查找,并转回原始数据中对应的记录序号。

 

为了验证利用位置之前、之后两种算法的性能差别,可以随机取出销售员编号做参数,用循环模拟大量访问,并分别执行两种算法。如下:


A

B

10

=100000.(A1(rand(A1.len())+1).empID)

/制造1万个empID

11

=now()


12

for A10

=A1.pselect(empID:A12)

13


=A1.calc(B12,if(#>1,amount[-1]-amount,0))

14

=interval@ms(A11,now())

/不利用位置,耗时:13552毫秒

15



16

=now()


17

for A10

=oPos(index.pselect@b(empID: A17))

18


=A1.calc(B17,if(#>1,amount[-1]-amount,0))

19

=interval@ms(A16,now())

/利用位置,耗时:165毫秒

       可以看到,利用位置后性能提高几十倍。例子中数据量较少,随着数据量的增加,性能差距会急剧拉大,这是因为遍历查找的时间复杂度为线性,而二分查找为对数。

快速对齐

函数align可将数据按序列对齐,比如输入条件:=pOrderList= [10250,10247,10248,10249,10251],将订单明细按该列表对齐,求每个订单的金额小计。代码如下:


A

1

=connect("demo").query@x("select   orderID,productID,price,quantity from orderDetail")

2

=A1.align@a(pOrderList,orderID).new(orderID,~.sum(price * quantity):小计)

但上述写法没有利用位置,性能因此不高。要想提高性能,可以将序列排序(手工建立索引表),再用二分法对齐,最后恢复为原顺序,代码如下:


A

1

=connect("demo").query@x("select   orderID,productID,price,quantity from orderDetail")

2

=oPos= pOrderList.psort()

3

=index= pOrderList (oPos)

4

=A1.align@ab(index,orderID).new(orderID,~.sum(price   * quantity):total)

5

=A4.inv(oPos)

A2-A3:手工建立索引表。

A4:将订单明细表与订单列表对齐,求出金额小计。由于索引表有序,因此可用二分法对齐,即@b选项。

A5:将A4按原位置调整,与pOrderList的顺序保持一致。函数inv可按指定位置调整成员,这里按原位置调整成员,相当于恢复成原位置。

 

对利用位置前后的两种算法,模拟大访问量测试,可以看到性能提升显著:


A

B

8

=now()


9

for A9

=A1.align@a(A12,orderID).new(orderID,~.sum(price*quantity):total)

10

=interval@ms(A11,now())

/不利用位置,耗时43456毫秒

11



12

=now()


13

for A9

=oPos=A16.psort()

14


=index=A16(oPos)

15


=A1.align@ab(index,orderID).new(orderID,~.sum(price*quantity):total)

16


=B18.inv(oPos)

17

=interval@ms(A15,now())

/利用位置,耗时7313毫秒

18

=now()


19

for A9

=A1.align@a(A12,orderID).new(orderID,~.sum(price*quantity):total)

20

=interval@ms(A11,now())

/不利用位置,耗时43456毫秒

有序数据批量查询

有时要对有序数据进行批量查询,比如pOrderList=[10877,10588,10611,11037,10685],请统计符合该列表的订单的运货费合计,代码可以这样写:


A

B

1

=connect("demo").query@x("select   orderID,customerID,orderDate,shippingCharge from order order  by orderID")

2

=pOrderList=[10877,10588,10611,11037,10685]

/列表参数

3

=A1.select(pOrderList.pos(OrderID)).sum(shippingCharge)

/不利用位置,单次代码

解释:函数posselect配合,可实现批量查询。其中函数pos可返回某个值在序列中的位置,如该值不在序列中,则返回null。函数select用于查询,当条件非null且非false时,可返回当前记录。

但上述代码没有利用位置,所以性能不高。

应当注意到,订单记录是有序的,所以可以用二分法取得符合条件的订单位置,再用位置取记录并计算。具体代码如下:


A

B

5

=A1.(orderID).pos@b(pOrderList)


6

=A1(A5).sum(shippingCharge)

/利用位置,单次代码

A1.(orderID)可取得orderID列,pos@b可针对有序数据,用二分法快速取得成员位置。A6按位置取数据。

 

对利用位置前后的两种算法,模拟大访问量测试,可以看到性能提升显著:


A

B

8

=A1.(OrderID)

/性能测试准备

9

=100000.(A1.(OrderID).sort(rand()).to(rand(100)))

/随机生成100000个列表

10



11

=now()


12

for A9

=A1.select(A12.pos(OrderID)).sum(shippingCharge)

13

=interval@ms(A11,now())

/不利用位置,85166毫秒

14



15

=now()


16

for A9

=A1.(OrderID).pos@b(A16)

17


=A1(B16).sum(shippingCharge)

18

=interval@ms(A15,now())

/利用位置,3484毫秒