性能优化技巧 - 遍历

【摘要】
数据分析场景中,充斥着聚合运算,常见的有求和、计数、均值、最大最小值等等,想要得到正确的结果值,遍历技术必不可少,如何更加高效地对数据进行遍历?点击:性能优化技巧 - 遍历,来乾学院一探究竟!

1. 存储方案

集文件是行存方式,组表有行存和列存两种方式。两种格式都有一定压缩效果。

首先,我们来建立一个的普通的文本文件,并在该文件中生成一些数据,代码如下:


A

B

1

=file("txt/employee.txt")


2

=file("info/ming_en_female.txt").import@i()

=A2.len()

3

=file("info/ming_en_male.txt").import@i()

=A3.len()

4

=file("info/xing_en.txt").import@i()

=A4.len()

5

=city=file("info/city_en.txt").import@i()

=A5.len()

6

=salary=20000

/10000~30000

7

=["one","two","three","four","five","six","seven","eight","nine","ten"]

=A7.len()

8

=height=50

/160~210cm

9

=weight=50

/50~100kg

10

=birthtime=946656

/1970~2000

11

for 100

=to((A11-1)*100000+1,A11*100000).new(~:id,if(rand(2)==0,A2(rand(B2)+1),A3(rand(B3)+1))+" "+A4(rand(B4)+1):name,if(A2.pos(name.array(" ")(1)),"Female","Male"):sex,A5(rand(B5-1)+1):city,date(rand(birthtime)*long(1000000)):birthday,rand(salary)+10000:salary,A7(rand(B7-1)+1):level,rand(height)+160:height,rand(weight)+50:weight,if(rand(2)==0,A2(rand(B2)+1),A3(rand(B3)+1))+"&"+A4(rand(B4)+1)+"  Co. Ltd":company)

12


=A1.export@at(B11)

代码1.1

代码 1.1,生成一个 txt 文件,总记录数为 1000 万,其中部分数据如图 1.1 所示。

1.1

 


A

1

=file("txt/employee.txt").cursor@t()

2

=file("btx/employee.btx").export@ab(A1)

代码1.2

 


A

1

=file("txt/employee.txt").cursor@t()

2

=file("ctx/employee.ctx").create(#id,name,sex,city,birthday,salary,level,height,weight,company).append(A1)

代码1.3

 


A

1

=file("txt/employee.txt").cursor@t()

2

=file("ctx/employee@r.ctx").create@r(#id,name,sex,city,birthday,salary,level,height,weight,company).append(A1)

代码1.4

代码 1.2、1.3、1.4 分别使用代码 1.1 建立的 txt 文件,转为集文件 employee.btx、列存组表文件employee.ctx和行存组表文件employee@r.ctx,各文件大小如图 1.2 所示。

 

1.2

按照文件占用的硬盘空间大小排序可以得到:txt> 行存组表 > 集文件 > 列存组表。可见,同样的数据,在不同的文件存储格式下,所占用的硬盘空间大小也不同,而文件的大小又会直接影响遍历的效率。

 

排序能有效提高列存组表压缩效率,重复次数多的字段排到前面。


A

1

=file("ctx/employee.ctx").create().cursor().sortx(level,height,weight,city)

2

=file("ctx/employee_sort.ctx").create(#id,name,sex,city,birthday,salary,level,height,weight,company).append(A1)

1.5

1.5对原组表文件的level,height,weight,city列依次进行排序。

排序后的组表文件 employee_sort.ctx与原始文件employee.ctx相比,明显变小,如图1.3所示。

1.3

 

2. 并行遍历

序表过滤时用 select@m 可以并行计算。


A

1

=now()

2

=file("ctx/employee.ctx").create().cursor(;level=="two"   && city=="Reno").fetch()

3

=interval@ms(A1,now())

4

=now()

5

=file("ctx/employee.ctx").create().cursor@m(;level=="two"   && city=="Reno";4).fetch()

6

=interval@ms(A4,now())

7

=file("ctx/employee.ctx").create().cursor().fetch()

8

=now()

9

=A7.select(level=="two"   && city=="Reno")

10

=interval@ms(A8,now())

11

=now()

12

=A7.select@m(level=="two"   && city=="Reno")

13

=interval@ms(A11,now())

代码2.1

代码2.1 中:

A2、A5 分别是外存的串行和并行情况,耗时分别为 2742 毫秒和 828 毫秒。

A9、A12 分别是内存的串行和并行情况,耗时分别为 1162 毫秒和 470 毫秒。

 

集文件和组表上都可以定义多路游标实现并行遍历。列存 + 机械硬盘 + 取用列过多时多路游标不一定会更快。


A

1

=now()

2

=file("btx/employee@z.btx").cursor@bm(;4).select(level=="two"   && city=="Reno").fetch()

3

=interval@ms(A1,now())

4

=now()

5

=file("ctx/employee.ctx")

6

=A5.create().cursor@m(;;4).select(level=="two"   && city=="Reno")

7

=A6.fetch()

8

=interval@ms(A4,now())

代码2.2

代码2.2中:

前 3 行是集文件的并行遍历,耗时 1861 毫秒。

后 5 行是相同数据的列存组表多路游标并行遍历。耗时 2282 毫秒。

 

使用 fork 语句并行时,不要返回游标。游标只是定义并没有实际取数,这种并行没有意义。要在 fork 代码块中做 fetch 或 groups 等实质取数的动作才有意义。


A

B

1

=file("ctx/employee.ctx").create()


2

=now()


3

fork to(4)

=A1.cursor(;level=="one" &&   height==180;A3:4).fetch()

4


return B3

5

=A3.conj()


6

=interval@ms(A2,now())


7

=file("ctx/employee.ctx").create()


8

=now()


9

fork to(4)

=A7.cursor(;level=="one" && height==180;A9:4)

10


return B9

11

=A9.conjx().fetch()


12

=interval@ms(A8,now())


代码2.3

2.3,前6行在fork码块中完成fetch取数,然后合并果,查询865毫秒。第7行至12 行,fork 返回游标后,合并再进行 fetch 动作,耗时 1709 毫秒。

 

3. 过滤条件

多个条件 && 时注意书写次序,如果前面的子项为假时,后面就不会再计算了,这样把容易为假的条件项写到前面,会减少后面条件项的计算次数。


A

1

=file("btx/employee.btx").cursor@b().fetch()

2

=now()

3

=A1.select(salary < 10010   && like(name,"*d*"))

4

=interval@ms(A2,now())

5

=now()

6

=A1.select(like(name,"*d*")   && salary < 10010)

7

=interval@ms(A5,now())

代码3.1

代码3.1

A3 中的条件为salary < 10010 && like(name,"*d*"),前面的子项返回结果集较小,查询耗时748 毫秒。

A6 中的条件为like(name,"*d*") && salary < 10010,前面的子项返回结果集较大,查询耗时1814毫秒。

 

在集合中找成员时(IN 判断),避免在过滤条件中临时计算这个集合。集合成员较多时要先排序,然后用 pos@b 或 contain@b 去判断,将使用二分法。


A

1

=100.(rand(1000000)+1)

2

=file("txt/keys.txt").export(A1)

代码3.2

在代码3.2中:

A1:取 100 个范围在 1 至 1000000 中的随机数;

A2:为确保后续测试的数据一致,将这 100 个随机数存到文件 keys.txt 中。

 


A

1

=file("txt/keys.txt").import@i()

2

=A1.(~*10)

3

=file("ctx/employee.ctx").create()

4

=now()

5

=A3.cursor(;A2.pos(id)).fetch()

6

=interval@ms(A4,now())

代码3.3

在代码3.3中:

A2:将预先准备的每个键值都乘以 10。

A5:使用 pos 函数在组表文件 employee.ctx 中找满足 A2 的成员并取出,耗时 15060 毫秒。

 


A

1

=file("txt/keys.txt").import@i()

2

=file("ctx/employee.ctx").create()

3

=now()

4

=A2.cursor(;A1.(~*10).pos(id)).fetch()

5

=interval@ms(A3,now())

代码3.4

在代码3.4中:

与代码3.3 的区别在于,把代码 3.3 中 A2 的集合搬到了代码 3.4 中 A4 的 cursor 过滤条件中临时计算这个集合,执行耗时 32105 毫秒。相比代码 3.3,虽然结果一致,但耗时多了一倍,应当避免这种写法。

 


A

1

=file("txt/keys.txt").import@i()

2

=A1.(~*10).sort()

3

=file("ctx/employee.ctx").create()

4

=now()

5

=A3.cursor(;A2.pos@b(id)).fetch()

6

=interval@ms(A4,now())

代码3.5

代码3.5基于代码3.3,我们还可以再进行一些优化。

将代码3.3 的 A2 排序,得到了有序键值。

A5 中的 pos 函数采用选项 @b,使用二分法。执行耗时 7854 毫秒,相比代码 3.3 快了将近一倍。

 

switch@i@d 可用于快速实现键值过滤,hash 索引常常会比二分法更有效。


A

1

=file("txt/keys.txt").import@i()

2

=A1.(~*10).sort()

3

=file("ctx/employee.ctx").create()

4

=now()

5

=A3.cursor().switch@i(id,A2).fetch()

6

=interval@ms(A4,now())

代码3.6

代码3.6 中:

A5:使用switch@i过滤出满足序列A2中的数据,结果与代码3.3、代码 3.4、代码 3.5 一致,耗时为 7104 毫秒。switch函数时会自动建索引@d选项也可以实现过滤效果,这里不再单独例举。

 

4. 预先过滤

组表游标在创建时即可写入一些过滤条件。集算器会识别这些条件,利用组表本身的排序信息快速跳到相应的数据位置。另外,这些条件不满足时取出字段就不会被读出,可以减少对象产生次数。而已经产生了游标后再做过滤就没有这些效果了。我们来看这样一个例子。


A

1

=file("ctx/employee.ctx").create()

2

=now()

3

=A1.cursor(city,sex;level=="one" && height<180)

4

=A3.groups(city;count(sex=="Male"):Male,count(sex=="Female"):Female)

5

=interval@ms(A2,now())

6

=now()

7

=A1.cursor().select(level=="one" && height<180)

8

=A7.groups(city;count(sex=="Male"):Male,count(sex=="Female"):Female)

9

=interval@ms(A6,now())

代码4.1

代码 4.1 中:

A3 在组表游标创建时写入过滤条件 level=="one" && height<180 并且只取 city 和 sex 两列数据。

A7 在组表游标创建后,再通过 select 中的过滤条件筛选数据。

随后两者进行了相同的分组聚合运算,结果前者耗时1206 毫秒,后者耗时 4740 毫秒。

 

5. 游标取数

游标取数性能和每次取出的记录数相关,要做些测试,一般最好是几万行,不要一次只取一行。


A

B

1

=file("ctx/employee.ctx").create().cursor()


2

>ctx_length_10=0


3

=now()


4

for A1,10

=A4.len()

5


>ctx_length_10=ctx_length_10+B4

6

=interval@ms(A3,now())


7

=file("ctx/employee.ctx").create().cursor()


8

>ctx_length_50000=0


9

=now()


10

for A7,50000

=A10.len()

11


>ctx_length_50000=ctx_length_50000+B10

12

=interval@ms(A9,now())


代码5.1

代码 5.1 中:

过遍历组表标,获果,并累计每次果的记录数。

6行遍历过程中每次取10条记录,最终累计耗时7823毫秒。

6行遍历过程中每次取50000条记录,最终累计耗时3923毫秒。

 

还可以使用 skip 函数计数,这样不必把游标数据读出产生成 java 对象。


A

1

=file("ctx/employee.ctx").create()

2

=now()

3

=A1.cursor(#1;).fetch().len()

4

=interval@ms(A2,now())

5

=now()

6

=A1.cursor().skip()

7

=interval@ms(A5,now())

代码5.2

代码 5.2 中:

A3 在创建组表游标时取第一列,然后取出该列数据后取得其长度。

A6 对组表游标使用 skip 函数,获取该组表记录数。

这两个单元格计算后的值都为 10000000,但前者耗时 9676 毫秒,后者耗时 6473 毫秒。

 

6. 遍历复用

使用管道技术可以对基于同一次遍历计算出多个结果,减少硬盘的访问。


A

B

C

1

=file("ctx/employee.ctx").create().cursor()



2

=channel(A1)

=channel(A1)

=channel(A1)

3

>A2.select(salary<10123 &&   level=="nine").fetch()

>B2.select(level=="two" && height==183).fetch()

>C2.select(city=="Reno" && weight>95).fetch()

4

=now()



5

for A1,100000



6

=A2.result()

=B2.result()

=C2.result()

7

=interval@ms(A4,now())



8

=now()



9

=file("ctx/employee.ctx").create().cursor().select(salary<10123   && level=="nine").fetch()

=file("ctx/employee.ctx").create().cursor().select(level=="two"   && height==183).fetch()

=file("ctx/employee.ctx").create().cursor().select(city=="Reno"   && weight>95).fetch()

10

=interval@ms(A8,now())



代码6.1

代码 6.1 中:

A2B2C2 分别是组表游标 A1 上建立的管道,A3B3C3 为这三个管道定义不同筛选条件并定义取数,A6 中遍历组表游标,每次取 100000 条。A6B6C6 返回按前文定义的筛选条件返回的结果集。耗时 5182 毫秒。

9 行的三个单元格没有使用管道,分别三次建立组表游标再按前文三个相同的筛选条件取出结果。耗时 12901 毫秒。(关于管道的使用,新版本中还有更优写法,代码简洁明了,欢迎各位读者自行体验集算器语法的优雅之处。)