论文部分内容阅读
摘 要：文章基于Excelize第三方函数库，针对目前Excelize函数库没有实现排序函数的问题，以最低位优先算法思想为基础，设计并实现了Excel数据的多关键字排序算法。根据对实际案例进行排序测试所得的结果可知，该算法能够满足Excel工作表数据的单关键字、多关键字和自定义序列的排序操作。该排序算法的实现为今后设计并实现“计算机应用基础”课程自动判卷系统进一步奠定了技术基礎。
关键词：Excelize函数库;Go语言;LSD算法;Excel工作簿;多关键字排序
0 引言
为实现河南医学高等专科学校“计算机应用”课程在线考试系统的自动判卷操作以减轻教师的改卷压力，笔者选择以Go语言作为自动判卷系统的开发语言。Excelize是以Go语言开发的一套读写Excel工作簿的函数库[1]，且Excelize函数库在运行时长和占用内存方面的表现都具有绝对优势[2]，故笔者选择Excelize函数库作为该自动判分系统的第三方开发库。
本文在前期基于Excelize函数库对复杂Excel工作簿的读写操作测试的基础上，针对Excelize函数库目前没有实现排序函数的这个问题，以最低位优先算法（LSD算法）[3]思想为基础，基于Excelize函数库设计并实现了Excel数据的多关键字排序算法。该排序算法的实现为今后设计并实现“计算机应用基础”课程自动判卷系统进一步奠定了技术基础。
1 基于Excelize函数库实现Excel数据多关键字排序面临的问题
Excelize函数库提供了大量操作Excel工作簿读写的函数和方法。因为Excel工作表是按行数据进行排序的，所以需要通过Excelize函数库提供的GetRows（）方法从Excel工作簿中读取所有数据。但是，GetRows（）方法返回的数据结果为二维字符串切片，使得无论工作表中的数据为何种类型，得到的结果均为字符串类型。这样就使得对数据的操作存在以下3个方面的难题：（1）读取的数据均存储为字符串类型，无法利用程序自动判断原数据的数据类型，降低了软件的自动化程度。（2）假设排序关键字所在列为数值型数据，而读取后的结果却为字符串类型，需进行类型转换操作，否则排序结果不正确。（3）当排序结束后，需要将排序结果写回到Excel工作表中，此时需要将每一列数据由字符串类型转换为原类型的数据，否则将改变原始数据的数据类型。
2 基于Excelize函数库Excel多关键字排序算法的设计与实现
2.1 基于Excelize函数库设计Excel多关键字排序算法
本文通过对上述问题的分析和总结，以LSD算法为基础，基于Excelize函数库对Excel工作表数据设计并实现了多关键字排序算法。图1中所示左侧所示的是一个n行m列数据序列R={R1，R2，…，Ri，…，Rn}（1≤i≤n），其中Ri={Ri1，Ri2，…，Rij，…Rim}（1≤j≤m）为序列R的第i行数据，而Rij∈Dj为第i行第j列的数据值，且Dj={D1，D2，…，Dn}（1≤j≤m）为第j列所有数据的取值范围。该图是按第j列数据进行“分配”和“收集”过程的示例图。切片Bucket（顺序结构）为“排序桶”，桶中存放的是已经排列过顺序（升序、降序或自定义序列）的第j列数据值的集合，其排列顺序从下标0开始;Map类型变量CntBkt（随机存储结构）为“计数桶”，其key值记录的是第j列的所有数据值的集合，而value值记录的是在“收集”数据阶段，第j列取值为Dij所对应的记录在新生成的数据序列R’中所对应的行号。切片Bucket和Map类型变量CntBkt生成的过程被称为LSD算法的“分配”阶段，而按照CntBkt中value值，重新生成新的数据序列R’的过程被称为LSD算法的“收集”阶段。若需对数据序列R按k个关键字进行排序，则需要按照关键字的优先级次序，由低到高地循环执行上述“分配”和“收集”操作，直到主要关键字完成“收集”任务后，即完成所有关键字的排序操作。
2.2 基于Excelize函数库实现Excel多关键字排序算法
根据LSD排序算法的设计需要，定义了一种名为SortField的排序关键字数据类型，其定义结构如下：
type SortField struct {
Name string //排序列的字段名
Type string //排序类型，是”int”，”float”还是”string”，”user”为自定义序列
Order string //排序顺序，如果是"desc”为降序，”asc”为升序，”user”为自定义序列
ColIdx int //排序列的索引号，该值从1起始
RowIdx int //排序列标题所在行索引，该值从1起始
Bucket []string //“排序桶”
CntBkt map[string]int //“计数桶”
}
其中，SortField类型的ColIdx和RowIdx两个字段主要是用于记录排序列标题所在列号和行号。设置这两个字段的目的：一是为了防止其他函数对列标题坐标进行重复计算;二是为了在全表数据进行排序的过程中，利用RowIdx数值将标题行排除在外。一方面使标题行不参与排序，从而保证排序数据的准确性，另一方面也减少了排序过程中所分配的存储空间。
为SortField关键字数据类型绑定一个初始化方法SetSortField （），其方法原型为： func （field *SortField） SetSortField（file *excelize.File，sheet，name，sortType，order string，sortData ...[]string） error。其中，参数file用以接受Excelize函数库读入的excel文件变量，name，sortType，order 3个参数分别代表排序关键字的名字、排序类型和排序顺序，其含义已在SortField类型定义中予以说明。sortData為可选字段，当sortType和order两个参数均为“user”字符串时，sortData字段必须指定待排序列的自定义序列。该方法的执行步骤如下：
（1）使用name， sortType，order 3个变量分别对绑定的*SortField 类型变量field中的name，Type和order 3个字段进行赋值。
（2）执行file.GetCols（sheet）方法从sheet中将读入的数据存储到cols变量中。
（3）调用file.SearchSheet（sheet， name）方法将排序列数据存储到变量data中。
（4）调用excelize提供的工具方法CellNameToCoordinates（data[0]）获取排序列标题的坐标，并存入绑定变量field的ColIdx和RowIdx两个字段中。
（5）如果field变量的Type字段值为”user”，则调用其绑定方法MakeBucket（）并传入参数sortData[0]，构建其“排序桶”Bucket字段 ;否则调用其绑定方法MakeBucket（）并传入参数cols[colNum-1][rowNum：]，生成其“排序桶” Bucket字段。
（6）调用make（map[string]int， len（field.Bucket））函数为field变量的“计数桶”CntBkt字段分配存储空间。field变量的“计数桶”CntBkt 字段中的key值为其“排序桶”Bucket 的value值，且将“计数桶”CntBkt 的value值初始化为0。
MakeBucket（data []string）是SortField类型绑定的一个生成“排序桶”的方法，然后根据Order字段的排序顺序，完成“排序桶”Bucket的生成，其实现步骤如下：
（1）调用removeDuplicateElement（data）函数除去data中的重复数据并将结果存入orderData变量中。
（2）调用make（[]string， len（orderData））函数为field.Bucket分配存储空间;同时调用make（[]interface{}，0，len（orderData））函数生成排序数据的临时存储空间temp。
（3）根据field.Type的值，对读取的字符串数据进行类型转换。如果所传入的参数值field.Type是字符串类型或“user”类型则不必转换，否则需要按照原始数据类型对数据进行转换。然后将数据追加到切片temp中去。
（4）对转换后的数据temp通过调用SortOrder（temp，field.Order）函数，按照field.Order字段进行排序。
（5）将排序后的数据temp转换为字符串放入“排序桶”field.Bucket中。
3 结语
综上所述，本文以最低位优先算法思想为基础，基于Excelize函数库设计并实现了能够满足Excel工作表数据单关键字、多关键字和自定义序列排序操作的多关键字排序算法。接下来，笔者将进一步研究基于Excelize函数库，以实现原生Golang中的sort.Interface接口的方法来完成Excel工作表数据的多关键字排序问题。
[参考文献]
[1]XU R.介绍·Excelize简体字文档[EB/OL].（2021-03-08）[2021-07-03].https：//xuri.me/excelize/zh-hans/.
[2]XU R.性能数据·Excelize简体字文档[EB/OL].（2021-03-08）[2021-07-03].https：//xuri.me/excelize/zh-hans/performance.html.
[3]严蔚敏，吴伟民.数据结构：C语言版 [M].北京：清华大学出版社，1996.
（编辑 姚 鑫）
Design and implementation of Excel multi-keyword sorting algorithm
based on Excelize function library
Li Kun， Jia Liwei， Shi Xiaoming
（Henan Medical College， Zhengzhou 451191， China）
Abstract：In this paper， based on the Excelize third-party library， aiming at the problem that the current Excelize function library does not implement the sorting function， based on the idea of the LSD algorithm， a multi-keyword sorting algorithm for Excel data is designed and implemented based on the Excelize function library. According to the sorting test results of the actual case， the algorithm can meet the sorting operations of single-keyword， multi-keyword and custom sequence of Excel worksheet. The implementation of the sorting algorithm lays a technical foundation for the design and implementation of the automatic grading system for the course of computer application foundation in the future.
Key words：Excelize function library; Go language; LSD algorithm; Excel document; multi-keyword sorting
关键词：Excelize函数库;Go语言;LSD算法;Excel工作簿;多关键字排序
0 引言
为实现河南医学高等专科学校“计算机应用”课程在线考试系统的自动判卷操作以减轻教师的改卷压力，笔者选择以Go语言作为自动判卷系统的开发语言。Excelize是以Go语言开发的一套读写Excel工作簿的函数库[1]，且Excelize函数库在运行时长和占用内存方面的表现都具有绝对优势[2]，故笔者选择Excelize函数库作为该自动判分系统的第三方开发库。
本文在前期基于Excelize函数库对复杂Excel工作簿的读写操作测试的基础上，针对Excelize函数库目前没有实现排序函数的这个问题，以最低位优先算法（LSD算法）[3]思想为基础，基于Excelize函数库设计并实现了Excel数据的多关键字排序算法。该排序算法的实现为今后设计并实现“计算机应用基础”课程自动判卷系统进一步奠定了技术基础。
1 基于Excelize函数库实现Excel数据多关键字排序面临的问题
Excelize函数库提供了大量操作Excel工作簿读写的函数和方法。因为Excel工作表是按行数据进行排序的，所以需要通过Excelize函数库提供的GetRows（）方法从Excel工作簿中读取所有数据。但是，GetRows（）方法返回的数据结果为二维字符串切片，使得无论工作表中的数据为何种类型，得到的结果均为字符串类型。这样就使得对数据的操作存在以下3个方面的难题：（1）读取的数据均存储为字符串类型，无法利用程序自动判断原数据的数据类型，降低了软件的自动化程度。（2）假设排序关键字所在列为数值型数据，而读取后的结果却为字符串类型，需进行类型转换操作，否则排序结果不正确。（3）当排序结束后，需要将排序结果写回到Excel工作表中，此时需要将每一列数据由字符串类型转换为原类型的数据，否则将改变原始数据的数据类型。
2 基于Excelize函数库Excel多关键字排序算法的设计与实现
2.1 基于Excelize函数库设计Excel多关键字排序算法
本文通过对上述问题的分析和总结，以LSD算法为基础，基于Excelize函数库对Excel工作表数据设计并实现了多关键字排序算法。图1中所示左侧所示的是一个n行m列数据序列R={R1，R2，…，Ri，…，Rn}（1≤i≤n），其中Ri={Ri1，Ri2，…，Rij，…Rim}（1≤j≤m）为序列R的第i行数据，而Rij∈Dj为第i行第j列的数据值，且Dj={D1，D2，…，Dn}（1≤j≤m）为第j列所有数据的取值范围。该图是按第j列数据进行“分配”和“收集”过程的示例图。切片Bucket（顺序结构）为“排序桶”，桶中存放的是已经排列过顺序（升序、降序或自定义序列）的第j列数据值的集合，其排列顺序从下标0开始;Map类型变量CntBkt（随机存储结构）为“计数桶”，其key值记录的是第j列的所有数据值的集合，而value值记录的是在“收集”数据阶段，第j列取值为Dij所对应的记录在新生成的数据序列R’中所对应的行号。切片Bucket和Map类型变量CntBkt生成的过程被称为LSD算法的“分配”阶段，而按照CntBkt中value值，重新生成新的数据序列R’的过程被称为LSD算法的“收集”阶段。若需对数据序列R按k个关键字进行排序，则需要按照关键字的优先级次序，由低到高地循环执行上述“分配”和“收集”操作，直到主要关键字完成“收集”任务后，即完成所有关键字的排序操作。
2.2 基于Excelize函数库实现Excel多关键字排序算法
根据LSD排序算法的设计需要，定义了一种名为SortField的排序关键字数据类型，其定义结构如下：
type SortField struct {
Name string //排序列的字段名
Type string //排序类型，是”int”，”float”还是”string”，”user”为自定义序列
Order string //排序顺序，如果是"desc”为降序，”asc”为升序，”user”为自定义序列
ColIdx int //排序列的索引号，该值从1起始
RowIdx int //排序列标题所在行索引，该值从1起始
Bucket []string //“排序桶”
CntBkt map[string]int //“计数桶”
}
其中，SortField类型的ColIdx和RowIdx两个字段主要是用于记录排序列标题所在列号和行号。设置这两个字段的目的：一是为了防止其他函数对列标题坐标进行重复计算;二是为了在全表数据进行排序的过程中，利用RowIdx数值将标题行排除在外。一方面使标题行不参与排序，从而保证排序数据的准确性，另一方面也减少了排序过程中所分配的存储空间。
为SortField关键字数据类型绑定一个初始化方法SetSortField （），其方法原型为： func （field *SortField） SetSortField（file *excelize.File，sheet，name，sortType，order string，sortData ...[]string） error。其中，参数file用以接受Excelize函数库读入的excel文件变量，name，sortType，order 3个参数分别代表排序关键字的名字、排序类型和排序顺序，其含义已在SortField类型定义中予以说明。sortData為可选字段，当sortType和order两个参数均为“user”字符串时，sortData字段必须指定待排序列的自定义序列。该方法的执行步骤如下：
（1）使用name， sortType，order 3个变量分别对绑定的*SortField 类型变量field中的name，Type和order 3个字段进行赋值。
（2）执行file.GetCols（sheet）方法从sheet中将读入的数据存储到cols变量中。
（3）调用file.SearchSheet（sheet， name）方法将排序列数据存储到变量data中。
（4）调用excelize提供的工具方法CellNameToCoordinates（data[0]）获取排序列标题的坐标，并存入绑定变量field的ColIdx和RowIdx两个字段中。
（5）如果field变量的Type字段值为”user”，则调用其绑定方法MakeBucket（）并传入参数sortData[0]，构建其“排序桶”Bucket字段 ;否则调用其绑定方法MakeBucket（）并传入参数cols[colNum-1][rowNum：]，生成其“排序桶” Bucket字段。
（6）调用make（map[string]int， len（field.Bucket））函数为field变量的“计数桶”CntBkt字段分配存储空间。field变量的“计数桶”CntBkt 字段中的key值为其“排序桶”Bucket 的value值，且将“计数桶”CntBkt 的value值初始化为0。
MakeBucket（data []string）是SortField类型绑定的一个生成“排序桶”的方法，然后根据Order字段的排序顺序，完成“排序桶”Bucket的生成，其实现步骤如下：
（1）调用removeDuplicateElement（data）函数除去data中的重复数据并将结果存入orderData变量中。
（2）调用make（[]string， len（orderData））函数为field.Bucket分配存储空间;同时调用make（[]interface{}，0，len（orderData））函数生成排序数据的临时存储空间temp。
（3）根据field.Type的值，对读取的字符串数据进行类型转换。如果所传入的参数值field.Type是字符串类型或“user”类型则不必转换，否则需要按照原始数据类型对数据进行转换。然后将数据追加到切片temp中去。
（4）对转换后的数据temp通过调用SortOrder（temp，field.Order）函数，按照field.Order字段进行排序。
（5）将排序后的数据temp转换为字符串放入“排序桶”field.Bucket中。
3 结语
综上所述，本文以最低位优先算法思想为基础，基于Excelize函数库设计并实现了能够满足Excel工作表数据单关键字、多关键字和自定义序列排序操作的多关键字排序算法。接下来，笔者将进一步研究基于Excelize函数库，以实现原生Golang中的sort.Interface接口的方法来完成Excel工作表数据的多关键字排序问题。
[参考文献]
[1]XU R.介绍·Excelize简体字文档[EB/OL].（2021-03-08）[2021-07-03].https：//xuri.me/excelize/zh-hans/.
[2]XU R.性能数据·Excelize简体字文档[EB/OL].（2021-03-08）[2021-07-03].https：//xuri.me/excelize/zh-hans/performance.html.
[3]严蔚敏，吴伟民.数据结构：C语言版 [M].北京：清华大学出版社，1996.
（编辑 姚 鑫）
Design and implementation of Excel multi-keyword sorting algorithm
based on Excelize function library
Li Kun， Jia Liwei， Shi Xiaoming
（Henan Medical College， Zhengzhou 451191， China）
Abstract：In this paper， based on the Excelize third-party library， aiming at the problem that the current Excelize function library does not implement the sorting function， based on the idea of the LSD algorithm， a multi-keyword sorting algorithm for Excel data is designed and implemented based on the Excelize function library. According to the sorting test results of the actual case， the algorithm can meet the sorting operations of single-keyword， multi-keyword and custom sequence of Excel worksheet. The implementation of the sorting algorithm lays a technical foundation for the design and implementation of the automatic grading system for the course of computer application foundation in the future.
Key words：Excelize function library; Go language; LSD algorithm; Excel document; multi-keyword sorting