性能优化技巧 - 位置利用

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

快速查询

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

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

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


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

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


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

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

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


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


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

快速对齐

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


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


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

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

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


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


有序数据批量查询

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


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

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

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


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


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


©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 215,539评论 6 497
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 91,911评论 3 391
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 161,337评论 0 351
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 57,723评论 1 290
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 66,795评论 6 388
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 50,762评论 1 294
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 39,742评论 3 416
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 38,508评论 0 271
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,954评论 1 308
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,247评论 2 331
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,404评论 1 345
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 35,104评论 5 340
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 40,736评论 3 324
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,352评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,557评论 1 268
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 47,371评论 2 368
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 44,292评论 2 352

推荐阅读更多精彩内容