排序

ABSTRACT(摘要)

1.INTRODUCTION(排序整体介绍)

2.排序前的算法准备

2.1 快排

2.2 败者树(多路归并)

2.2.1 归并排序

2.2.1.1 二路归并

令u个记录分布在两个归并段上,按merge过程进行归并。每得到归并后的一个记录,仅需一次比较即可,则得到韩u个记录的归并段需进行u-1次比较。

2.2.1.2 k路归并

令u个记录分布在k个归并段上,显然,归并后的第一个记录应是k个归并段中关键字最小的记录,即应从每个归并段的第一个记录的相互比较中选出最小者,这需要进行k-1次比较。同理,每得到归并后的有续断中的一个记录,都要进行k-1次比较。显然,为得到含u个记录的归并段需进行(u-1)*(k-1)次比较。由此,对n个记录的文件进行外排时,在内部归并过程中进行比较的总次数为floor(logkm) $行内公式$ 由于(k-1)/log2k随k的增长二增长,则内部归并时间亦随k的增!长而增长,这将第效由于增长k二减少外村信息都写时间所得效益,这是我们所不希望的。然而,若在进行k路归并时利用败者树,则可使总的归并时间有xxx变为xxxx,显然这个式子和k无关,他不随k的增长二增长。

2.2.1.3 败者树

败者树是胜者树的一种变体。在败者树中,用父结点记录其左右子结点进行比赛的败者,而让胜者参加下一轮的比赛。败者树的根结点记录的是败者,需要加一个结点来记录整个比赛的胜利者。采用败者树可以简化重构的过程。

1.png

b[3] < b[4] , ls[4] = 4
b[1] < b[2] , ls[3] = 1
b[ls[4]] < b[0] , ls[2] = 0
b[ls[0]] > b[ls[1]] , ls[1] = 0
根节点ls[1]上再加一个节点表示获胜者ls[0]=1

败者树的重构

2.png

将新进入选择树的结点与其父结点进行比赛:将败者存放在父结点中;而胜者再与上一级的父结点比较。
比赛沿着到根结点的路径不断进行,直到ls[1]处。把败者存放在结点ls[1]中,胜者存放在ls[0]中。

2.2.1.4 胜者树与败者树

胜者树每上升一次需要访问两个节点:父节点和兄弟节点;而败者树只需要访问父节点。这就是访存优势。”比较好的回答了这个问题。做一点设计层面的补充:由于新加入的节点一定是替换了上一轮的胜者,那么对于胜者堆,从新节点到根之间路径节点存的都是上一轮的胜者,这些数据事实上对于本轮比较来说是无用的,但每次还要与兄弟节点比较去更新它。而败者堆中,对于新更新的节点,它的父节点都是兄弟子堆的胜者,是最有价值、值得比较的数据,每次更新也都可以直接用于下轮比较。
(知乎)

3.排序文件格式

3.1 排序前文件格式

车牌号,日期,时:分,经度,纬度
806601461409,2010-9-12 17:38,118.817412,32.060442
806776000000,2010-9-12 3:05,118.749538,32.101681
806814049590,2010-9-12 12:31,118.76982,32.009938
806851756143,2010-9-12 14:00,118.778224,32.037016
806852000000,2010-9-12 6:41,118.751648,32.041414
806512544327,2010-9-12 17:56,118.779008,32.089196
806601000000,2010-9-12 6:14,118.815351,32.025234
806814000000,2010-9-12 0:15,118.790441,32.040154
806914728348,2010-9-12 22:21,118.870588,31.737184
806813360490,2010-9-12 16:24,118.775081,32.092388
806584048013,2010-9-12 10:19,118.745974,32.024608
806951028913,2010-9-12 12:55,118.82232,31.89717

3.2 排序后文件格式

车牌号 日期 时 分 经度 纬度
806512542975 2010-09-12 00:00:00 32.096014 118.758009
806512542975 2010-09-12 00:01:00 32.096019 118.758967
806512542975 2010-09-12 00:03:00 32.095144 118.762707
806512542975 2010-09-12 00:03:00 32.095171 118.762678
806512542975 2010-09-12 00:04:00 32.093044 118.769842
806512542975 2010-09-12 00:04:00 32.094481 118.765503
806512542975 2010-09-12 00:04:00 32.093202 118.769501
806512542975 2010-09-12 00:05:00 32.092466 118.774339
806512542975 2010-09-12 00:05:00 32.092208 118.77526
806512542975 2010-09-12 00:05:00 32.092464 118.774026
806512542975 2010-09-12 00:05:00 32.092128 118.7816

4.排序整体思路

3.png

4.1 参数说明

  • MAX_SAVE_RECORDS 已有序的块大小
  • MAX_LEAVES_NUM 最大子叶数目
  • f_point_num 最大子叶文件指针数
  • max_save_num 败者树获胜数据最大缓存数 2048
  • MAX_REMOVE_RECORDS_NUM 最大记录移动数(车牌号提取阶段 第三阶段)
  • MAX_FILE_NUM 打开的最大子文件个数 >=最大子叶数目
  • MAX_LEAVES_SON_BUFF 最大子叶记录缓存数
  • max_file_num 文件分割阶段即排序第一阶段最大hash文件个数
  • file_name 当前排序的文件名
  • cur_file_name 当前排序的文件路径
  • cur_file_name = ORIGIN_DIRECTOION+file_name
  • new_file 当前文件.dat阶段排序放置路径
  • MAX_FILE_NUM >= MAX_LEAVES_NUM
  • f_point_num >= MAX_LEAVES_NUM
  • ORIGIN_DIRECTION 将进行排序的文件路径(文件夹)
  • NEW_DIRECTION 阶段排序后的文件放置路径(文件夹)
  • DONE_DIRECTION 排序后的文件路径(文件夹)
  • SOURCE_DIRECTION 未处理的文件路径.txt
  • SAVE_CAR_TO_FILE 提取出租车数据后的放置路径(文件夹)

4.2 排序标准(将数据按第一关键字车牌号第二关键字时间排序)

文件数据中每一条记录的信息包含车牌号,时间,经度,纬度,我们的目的时将数据根据车牌号分割出来并排序,将数据按第一关键字车牌号第二关键字时间排序,可以保证同一个车牌号分布在相邻区域,并且一个车牌号块数据按照时间有序排列

4.3 将源乱序文件分割为多个小文件

4.2.1 分割算法

4.3 对单个文件败者树排序

4.4 在一次排序完更新源文件路径和目标文件路径

4.5 车牌号提取

4.5.1 二分法查找单个车牌号的起始终止地址

5.缓存机制

在排序第一阶段,hashxxxxxxxxxxxxxxxxx
在排序第二阶段,单文件排序,败者树中,k个归并段,对每一个归并段先读取定长数组MAX_LEAVES_SON_BUFF作为缓存,每次读取数组中的数据指针往后移一位,数据被读完后再向内存读取MAX_LEAVES_SON_BUFF个数据作为缓存,直到该归并段的文件指针指到该有序数据块的末尾.
在排序第二阶段,单文件排序,败者树中,获取的获胜者的数据放在一个数组中re_save[max_save_num],用一个变量记录当前指针re_save_numre_save_num==max_save_num或者所有归并段归并结束时,写到文件中,re_save_num重新指向缓存数组头,即re_save_num=0
缓存机制可减少IO操作

6.排序结果

分割后的有序的出租车gps数据放在分别以车牌号命名一个dat文件中
5.png

6.1 参数的变化对排序的影响

6.1.1 参数

  • 单文件排序
    对于hash之后的文件,可以保证每一个车牌号只存在在一个.dat文件中,且每个.dat文件都是块有序的,基于每个文件都是块有序的采用外部排序归并算法,具体为败者树算法。将文件中块数据依次读入内存中,并利用归并算法进行排序,将排序后的有序子文件写入文件。利用败者树进行k路归并利用使得每次归并在k个记录中选出最小记录仅需进行 次(二叉树的深度)比较,从而使总的归并时间为 。其中,m为初始归并段个数,n为总记录数, 每次比较时间。每次读入到内存中的数据带有缓存机制,不需要每个数据都访问一次文件,可减少io操作,对于写入到文件中的数据也有缓存机制,当记录的条数达到给定的阈值则写入文件。设最初有序块的单位长度为m个记录,一次排序后,有序块长度为mn,设文件记录数为all_num,对文件反复进行归并排序(两个文件夹反复替换),第k次排序后有序快的长度为mn^k,当m*n^k>=all_num时,说明文件已有序,移入最终文件夹。当所有文件都排序完毕移入最终文件夹时,开始对最终文件分割出车牌号。

  • 分割出车牌号
    对以上的文件均已排完序,此时,单个数据文件可能有多个车牌,但都是排好序的,即每个车牌号的数据都是一个块,所以采用二分查找法找出单个车牌号的首尾记录id,分块写入新文件,而不是一次性切块写入文件,例每次读取n条记录写n条记录到新文件,并将文件名,记录数写入log文件。由于单个文件夹不宜存放多个文件,所以每m个新文件放在一个文件夹里面,文件夹命名为(当前车牌号数/200),即每200个车牌放一个文件夹