基于TreeMap的二维长度不确定数据的主次关键字自排序算法

摘要

本发明公开一种基于TreeMap的二维长度不确定数据的主次关键字自排序算法，包括：从分隔符集合中选取能区分主关键字和次关键字的分隔符；通过二维长度不确定数据的对(主次关键字的数据类型可为整型或字符串类型)及其对应数据分别构建TreeMap的Key和Value；利用分隔符、Key和Value向TreeMap缓冲区中插入二维长度不确定数据。本发明可应用于MapReduce技术中的Reduce阶段数据关联、数据在线采集/收集、按主关键字分析数据(如汇总和平均值)等，通过将二维长度不确定数据插入到TreeMap缓冲区，达到按主次关键字要求排序的目的。

说明书

技术领域

本发明涉及一种数据处理方法，尤其涉及一种基于TreeMap的二维长度 不确定数据的主次关键字自排序算法。

背景技术

在本专利中，二维长度不确定数据，指维度确定但长度不确定的数据， 其维度为二维：采用主关键字和次关键字表示，主次关键字的数据类型可为 整型或者字符串；通过<主关键字，次关键字>对访问二维长度不确定数据。 二维长度不确定数据的排序需求为：先按主关键字排序，当主关键字相同时 则按次关键字排序。

排序是将一组无序数据(记录)调整为有序(升序或者降序)数据的操 作。现有排序方法包括传统排序算法、办公自动化中的电子表格排序、大数 据环境下的MapReduce排序。

传统排序算法(插入排序、冒泡排序、选择排序、快速排序、堆排序等) 是在给定数据长度下排序。应用传统排序算法的前提条件为：(1)数据长度 给定；(2)存储待排序的数据；(3)数据的索引(下标)数据类型为整型； (4)对数据本身排序。二维长度不确定数据的按主次关键字排序，因数据长 度不确定性、索引类型不确定(可为字符串类型或者整型)、按主次关键字排 序(不是数据本身排序)，因此传统排序算法并不适用于二维长度不确定数据 的主次关键字排序。

办公自动化中的电子表格排序是对选定排序区域排序，可以按主次关键 字排序，但选定了待排序数据的区域相当于给定了排序数据的长度，电子表 格排序方法也不适用于二维长度不确定数据的主次关键字排序。

利用大数据环境下的MapReduce技术排序：将主关键字作为Key，次关 键字为Value；对Value集合按次关键字排序。在Map阶段运行条件是必须 确定的数据源(直接/间接的文件)，二维长度不确定数据不能生成确定的数 据源，MapReduce排序不适用于二维长度不确定数据的主次关键字排序。

发明内容

本发明旨在提供一种基于TreeMap的二维长度不确定数据的主次关键字 自排序算法，可以支持复杂数据类型的二维长度不确定数据按主关键字和次 关键字排序，算法效率高，减少传统排序算法的排序操作。

为实现上述目的，本发明采用的技术方案如下：

本发明公开的基于TreeMap的二维长度不确定数据的主次关键字自排序 算法，包括以下步骤：

步骤1、按分隔符使用频率升序组织分隔符集合：将二维长度不确定数 据中的所有分隔符放在一起，形成分隔符集合；

步骤2、确定问题域为二维长度不确定数据的主、次关键字排序和主、 次关键字的排序要求；

步骤3、确定问题域中的主、次关键字集合，在主、次关键字集合中分 别找出最大值及最大值的数据宽度；

步骤4、从分隔符集合中选取能正确解析出二维长度不确定数据的主关 键字和次关键字的分隔符Separator；

步骤5、确定二维长度不确定数据的数据结构，当二维长度不确定数据 是简单数据类型，则不需定义二维长度不确定数据的数据结构；当二维长度 不确定数据是复杂数据类型否则，根据实际数据类型定义该二维长度不确定 数据的数据结构stru2d；

步骤6、申请TreeMap缓冲区TreeMapBuffer，采用TreeMapBuffer默认 的升序比较器或采用自定义的降序比较器；

步骤7、将主关键字转换成字符串PrimaryKey，次关键字转换成字符串 SecondaryKey；

步骤8、构建二维长度不确定数据的TreeMap的键值对<Key，Value>， 将字符串PrimaryKey+Separator+SecondaryKey合并生成Key，当所述二维 长度不确定数据为复杂数据类型时，申请str2d空间，申请的空间赋值给 Value，填充str2d的数据成员，当所述二维长度不确定数据为简单数据类型 时，将二维长度不确定数据赋值给Value；

步骤9、调用TreeMapBuffer的put操作，二维长度不确定数据的键值 对<Key，Value>缓存在TreeMapBuffer中。

优选的，所述分隔符为空格、制表符、分号或不可见字符。

进一步的优选，所述分隔符在调试时采用可见字符，在发布时采用不可 见字符。

优选的，所述简单数据类型为整型、字符型或字符串型。

优选的，在步骤2中，整型主关键字和整型次关键字的排序要求包括按 主关键字的升序/降序排序和/或按次关键字的升序/降序排序。

优选的，在步骤7中，当所述主、次关键字的数据类型为整型时，则将 主、次关键字转换为字符串类型将主、次关键字转换结果分别赋值给 PrimaryKey、SecondaryKey，所述转换规则如下：当主、次关键字采用升序 排列时，则将主、关键字转换为与主、关键字位数相同的字符串；当主、关 键字采用降序排列时，用主、次关键字的最大值减去该关键字的值，然后将 差值转换成字符串。

优选的，在步骤7中，当主、次关键字的数据类型为字符串类型，将主、 次关键字分别赋值给PrimaryKey、SecondaryKey。

进一步的，在步骤9之后，当排序未完成时，重复步骤7～9，直到排序 完成。

本发明公开的基于TreeMap的二维长度不确定数据的主次关键字自排序 算法具有以下特征：

第一，算法效率高：算法的步骤1～6是排序的准备阶段(分析问题域和 选取分隔符)，步骤7～9是插入操作。准备阶段的花销时间代价可以忽略， 插入操作简单，由TreeMap保证排序。算法的时间复杂度为O(l)，其中，l 为二维长度不确定数据的长度。

第二，通过定义复杂数据类型的数据结构，支持复杂数据类型的二维长 度不确定数据的按主次关键字排序。

第三，通过自定义比较器、主次关键字转换，支持整型主关键字(次关 键字)的升序或者降序排序。

第四，很容易支持Reduce阶段数据关联、数据在线采集/收集、按主关 键字分析数据(汇总、平均值等)扩展应用：

(1)对于Reduce阶段数据关联，假设有两组二维长度不确定的数据间 需建立关联，用<A，B>和<A，C>表示两组二维长度不确定的数据，A表示相 同的主关键字，B和C表示不同的次关键字。因为已经对A进行了相同排序 (如升序)，对齐主关键字，然后分析处理这两组数据。

(2)对于数据在线采集/收集，因为本发明针对二维长度不确定的数据 按主次关键字排序，所以适合于长度不确定数据的采集/收集，方便有序存储。

(3)对于按主关键字分析数据，本发明先按主关键字排序，当主关键字 相同时按次关键字排序，即按主关键字分类。将需分类的依据设定为主关键 字，统计量为次关键字；遍历TreeMapBuffer后，很容易对次关键字进行汇 总、平均等分析操作。

本发明有益效果如下：

(1)通过向TreeMap缓冲区中插入二维长度不确定数据，自动实现按主 关键字和次关键字排序。

(2)通过按主次关键字自排序，减少传统排序算法的排序操作。

(3)对整型主关键字(次关键字)，可实现按主关键字(次关键字)的 升序或者降序排序。

(4)向TreeMap缓冲区中插入二维长度不确定数据，算法简单，执行高 效。

(5)可以支持复杂数据类型的二维长度不确定数据按主关键字和次关键 字排序。

附图说明

图1为本发明的流程图。

具体实施方式

为了使本发明的目的、技术方案及优点更加清楚明白，以下结合附图， 对本发明进行进一步详细说明。

如图1所示，本发明公开的基于TreeMap的二维长度不确定数据的主次 关键字自排序算法，包括以下步骤：

步骤1、按分隔符使用频率升序组织分隔符集合

本发明将二维长度不确定数据的<主关键字，次关键字>对转换成 TreeMap的Key，以便通过Key访问/遍历缓存在TreeMapBuffer的<主关键字， 次关键字>对的二维长度不确定数据。反之，为了支持基于TreeMapBuffer 的应用，如:查找数据最大者的主关键字和次关键字，需利用Key解析出主关 键字和次关键字。为了正确解析出主次关键字，必须在主次关键字间加上分 隔符，即分隔符具有区分主次关键字的能力。将所使用的分隔符放在一起， 形成分隔符集合。为了快速选取分隔符，分隔符集合元素按分隔符使用频率 升序组织。推荐分隔符为空格、制表符、分号、不可见字符，在软件开发调 试应用中最好使用可见字符(便于调试)；在发布软件应用中最好使用不可见 字符(增大破解软件难度)。

步骤2、确定问题域为二维长度不确定数据的主次关键字排序和主次关 键字的排序要求

当排序问题具有以下特征：(1)数据的长度不确定；(2)按主关键字和 次关键字排序；(3)按主关键字排序，当主关键字相同时按次关键字排序， 该问题域为二维长度不确定数据的主次关键字排序问题。分析问题域，明确 整型主关键字和次关键字的排序要求：(1)按主关键字的升序/降序排序；(2) 按次关键字的升序/降序排序。

步骤3、确定问题域中的主次关键字集合

对于整型主关键字(次关键字)，在主关键字集合(次关键字集合)中找 出主关键字(次关键字)的最大值和及其数据宽度。

步骤4、从分隔符集合中选取分隔符Separator

选取的分隔符Separator必须具备区分主次关键字集合的每个元素字符 的能力，以满足基于TreeMapBuffer的应用需求，确保通过分隔符能正确解 析出二维长度不确定数据的主关键字和次关键字。

步骤5、定义二维长度不确定数据的数据结构

若二维长度不确定数据是简单数据类型(如整型和字符串等)，则不需定 义二维长度不确定数据的数据结构；否则，根据实际情况定义该二维长度不 确定数据的数据结构stru2d。

步骤6、申请TreeMap缓冲区TreeMapBuffer

在申请TreeMapBuffer缓冲区时，需考虑TreeMapBuffer的比较器。比 较器默认为升序，若期望为降序，需定义比较器，如需按字符串降序排列， 则自定义比较器为：

若数据处理完成，执行步骤10退出算法，否则，重复步骤7～9：

步骤7、将主关键字转换成字符串PrimaryKey，次关键字转换成字符串 SecondaryKey

若主关键字(次关键字)的数据类型为整型，则将整型转换成字符串类 型，其中，转换时确保主关键字(次关键字)的长度与主关键字(次关键字) 集合中最大元素位数对齐，这样保证主关键字(次关键字)的升序；若期望 主关键字(次关键字)的降序排列，则转换时用主关键字(次关键字)的最 大值减去该关键字的值，然后将差值转换成字符串；将主关键字(次关键字) 转换结果赋值给PrimaryKey(SecondaryKey)。

若主关键字(次关键字)的数据类型为字符串类型，将主关键字(次关 键字)赋值给PrimaryKey(SecondaryKey)。

步骤8、构建二维长度不确定数据的TreeMap的键值对<Key，Value>

将字符串PrimaryKey+Separator+SecondaryKey合并生成Key。若二维 长度不确定数据为复杂数据类型，申请str2d空间，申请的空间赋值给Value， 填充str2d的数据成员；否则，将二维长度不确定数据赋值给Value。

步骤9、调用TreeMapBuffer的put操作，二维长度不确定数据的键值 对<Key，Value>缓存在TreeMapBuffer中。

步骤10、结束。

当然，本发明还可有其它多种实施例，在不背离本发明精神及其实质的 情况下，熟悉本领域的技术人员可根据本发明作出各种相应的改变和变形， 但这些相应的改变和变形都应属于本发明所附的权利要求的保护范围。