外存排序原理

阅读(2637) 标签: 外存排序,

在数据分析计算中,将表中的记录排序,是很常见的需求。集算器中,可以用sort函数为序列或者序表中的数据排序。如果需要排序的数据量巨大,不能一次将它们读入内存,普通的排序方法就无法执行了,此时需要使用外存排序

大数据中的外存排序

在数据统计中,遇到海量数据时,通常会使用游标来读取,在集算器中同样使用游标来处理大数据计算。集算器中的游标与数据库存储过程中的游标是类似的:可以根据游标记录的位置每次读取一条或多条记录,而不会一次返回全部数据。

使用游标计算时,每次读取的都只是部分数据,如果需要对游标中的所有数据进行排序、分组等计算时,是无法直接完成的。集算器面对大数据的这类运算时,使用了外存,每次读取出部分数据来计算出初步的结果,并将结果临时记录在硬盘上;这样就可以用全部的初步结果通过归并构成游标,从而获得最终的结果。

首先,我们先来准备一个大数据表,其中随机生成日期和电话号码,其中日期和电话号码随机生成,电话号码固定为8位数字组成,首尾号码不为0。为方便起见,大数据表存储为集文件。

 

A

B

C

1

100000

1000

=A1/B1

2

=file("PhoneRecord.btx")

=create(ID,Date,PhoneNum)

 

3

=date(now())

0

 

4

for C1

for B1

>B3=B3+1

5

 

 

=elapse(A3,-rand(1000))

6

 

 

=rand(90000000)+10000000

7

 

 

>B2.insert(0,B3,C5,C6)

8

 

>A2.export@ab(B2)

 

9

 

>B2.reset()

 

10

=A2.cursor@b()

>A10.skip(50000)

=A10.fetch(1000)

11

>A10.close()

 

 

总共生成100,000条数据,在C10中,可以看到用游标读取第50001条到51000条的结果如下:

下面将用生成的数据文件PhoneRecord为例,研究一下在集算器中如何实现外存排序。

外存排序时,使用的函数是cs.sortx(x…),可以将游标cs中的数据按表达式x的计算结果升序排序。如:

 

A

1

=file("PhoneRecord.btx")

2

=A1.cursor@b()

3

=A2.sortx(PhoneNum;20000)

4

=A3.fetch(1000)

5

>A3.close()

为了了解集算器是如何用外存排序的,在这里我们在工具栏的调试区内点击分步执行代码,一直到A5的代码执行之前。A2用集文件PhoneRecord.btx建立游标。A3中用sortx函数将游标中的数据排序,参数中的20000为缓冲区行数,用来设定缓存数据行数为20000,这个参数在正常使用中不必设定,会根据内存空余情况,在需要时自动缓存数据。排序的结果实际上是由多个临时文件游标有序归并所产生的游标,A3中的结果如下:

A4从这个游标中获取排序后的前1000条记录如下:

A3中代码执行时,就会在临时文件目录下,生成外存文件,可以在临时文件目录下找到这些临时文件:

这里使用sortx时,设定的测试缓存行数比前面测试时大,因此游标中的100,000条记录共生成了5个临时文件。我们可以读取其中一个临时文件中的数据:

 

A

1

=file("/temp/tmpdata984048609330992507")

2

=A1.import@b()

3

=A2.count()

A2中读取到的数据如下:

A3中计算出这个临时文件中的数据数如下:

A2中的数据与前面获得的最终排序结果对比,就知道这实际上是部分数据排序后的结果。说明每个临时文件都是获取部分数据后排序的结果。

继续执行前一个网格文件,可以发现,当游标关闭时,使用的临时文件会自动删除。

 

使用sortx,还可以对多个字段执行排序,如:

 

A

1

=file("PhoneRecord.btx ")

2

=A1.cursor@b()

3

=A2.sortx(Date,-PhoneNum)

4

=A3.fetch(1000)

5

>A3.close()

A3在排序时,用Date-PhoneNum来排序,即先按照日期升序排序,日期相同的再按照号码的降序来排序。这种在需要降序排序的表达式前加负号的方法,在应用中比较常见。A4中读取排序后的前1000条结果如下:

外存排序的应用

其实,从外存排序的过程中,我们就可以看到对游标排序的应用之一:排序后的数据可以用来有序归并。有序归并可以从多个游标中获取数据,根据排序表达式计算,哪个游标中的当前结果最小(或最大),则读取这个游标中的记录。显然,只有在各个游标中的数据均有序时,才能使用这样的计算方法。除此以外,使用joinx() 函数将游标中的记录对齐式连接时,也要求各个游标中的数据先完成排序。关于joinx() 的使用,请阅读游标并与连接

当游标中的数据满足有序需求时,在游标中获取数据还可以指定取数到表达式变化为止,如:

 

A

1

=file("PhoneRecord.btx ")

2

=A1.cursor@b()

3

=A2.sortx(Date,-PhoneNum;20000)

4

=A3.fetch(;Date)

5

>3.(A3.skip(;Date))

6

=A3.fetch(;Date)

7

>A3.close()

A4中,从A3的游标中取数,直到日期变化为止,即取出第1天的数据;A5中,连续跳过3天的数据;A6中取出第5天的数据。A4A6中的结果如下: