一种基于喊话模式的排序算法

2024-02-16 13:58

本文主要是介绍一种基于喊话模式的排序算法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1 引言(Introduction)

排序,就是将杂乱无章的数据,通过一定的方法按特定的顺序排列的过程。[1] 排序在现代互联网应用中有着广泛的应用,例如每周、月最活动PV、PU统计、客户投诉率等问题。考虑现有商务网站的用户数据量相对较大,而所需的数据样本较小,因此研究从大量数据中高效实时的取数算法尤为重要,例如,每日PV数能达到百万级别,但每日会关注使用频次最高的前20%用户(此类用户的转化率较高)的转化率。此问题的一般处理做法:首先对数据整体排序,其次获取所需的数据。此种算法存在一个明显的缺点:无论所取的数据无论多少,都需要对于整个数据集进行排序。如果能够将所取数据映射为不同区段,根据取数范围取值,效率将大大提高。本算法就是基于以上问题提出的一种改进的数据取数算法。

为了便于分析,定义问题集合D序列{A0,,A1,...Ai...An}(0≤i≤n,其中n为问题规模),求取排序后的从i到j的元素序列P(i<j)。本文对问题集合D转化为有序频段,将所取数据映射为不同的频段,对于不同的频段排序后取数。由于获取数据方式类似于喊话叫人,故称之为喊话模式的排序算法。经试验证明,数据量在100万情况时,快速排序平均耗时是本算法的8.7倍,效果显著。

2算法分析和描述(Algorithm analysis and description)

2.1算法分析

本研究的关键问题是有序数据频段的转化、获取数据的频段转化和频段数据的排序获取。有序数据频段的转化由分析数据的带宽(最大值减去最小值即为数据带宽)和具体业务类型决定。获取数据的频段转化由获取数据的初始值、结束值和频段带宽共同决定。频段数据的排序获取由划分的数据频段和获取的数据频段决定。

获取数据的频段包括两种类型:部分区间和跨频段数据。部分区间数据即为划分频段的单个频段的部分数据。数据处理上:先对该频段数据快速排序,然后获取所需数据。跨频段数据包括端聚集性数据和完整频段数据,不同类型的数据根据不同的特点获取数据。端聚集性的数据,仅需要获取前(或后)j个数据即可,无需进行全部排序。具有端排序特性的算法包括冒泡排序、选择排序和堆排序[2]。从时间复杂度考虑,堆排序具有较好的时间复杂度()[3],因此端聚集性数据采用堆排序获取数据。完整频段首先对数据快速,其次获取该频段数据。

因为本算法要将数据按照大小序列重新划分频段,需额外增加(P+2M+R)的空间(其中P为问题规模,M为所分数据段数加一, R为输出元素的集合)。

2.2算法描述

1、扫描数据集D,找出最大值()和最小值(),如果=,则直接退出。最大值()和最小值()通过两端对比排序获得,其问题规模为。

2、计算数据的频段带宽。频段默认取10(原则上尽可能的让获取数据在一个频段),可根据具体业务适当调整。带宽计算公式,Width=。例如,网站的初期,人流量较少,则带宽为10;随着推广力度的加大,带宽会调整为100或者1000。

3、初始化数组空间Pn、Qm+1和Q2m+1,用于分别存储有序段后的数据、段序列元素频数和段序列元素累计值。

4、遍历数据集合D,统计每个频段的数据量,存入Qm+1,当前元素的频段计算公式为Mi=(Ai-Amin/Width。Qm+1,下标为0的元素代表0段数据的个数,下标1的元素代表1段数据的个数,依次类推。

5、计算频段的数据累加值(即排序后各个频段的元素初始位置)。通过Qm+1中各段的元素频数计算各个频段的累计值,计算后存入Q2m+1

6、根据Q2m+1和原始数据集合D,将数据重新排序后存入Pn。首先计算初始数据元素的频段Mi=Ai/Width,其次根据该频段的初始位置插入Pn;最后,将该元素所在频段Mi的初始位置加1(始终指向该频段的第一个空位置)。

7、根据输入的初始值i、结束值j,分别计算初始值的频段区间Mi和结束值的频段区间Mj。算法为通过初始值或者结束值遍历频段数值累计数组,找到第一个小于或者等于数组的元素,元素下标即为所在频段。

8、初始数组R,元素个数为j-i+1,用于存储输出元素的集合

9、根据频段区间计算频段跨度,并获取相应频段数据。如果Mi和Mj相等,则所取数据为部分区间数据;反之,将数据跨度分为完整区间和端区间。部分区间数据首先通过快速排序对该频段数据排序,然后获取i-1到j-1位数据。如果Mi和Mj不在同一区间内,Mi和Mj所在区间内的数据为端区间数据,中间数据为完整区间数据。端区间数据通过堆排序获取所需的堆顶数据(仅排序所需数据)。全部区间数据通过快速排序区间数据,然后获取相应数据。

10、将获取的元素输出返回。

2.3时间复杂度分析

为了便于分析,本文采用单处理机、随机存取机计算模型分析[4]。通过算法分析,获取最大值最小值的时间为C1(n/2)。统计频段数据量时间为C2(n),频段的数据累加值时间为C3(n)。元素重新排序的时间为C4(n)。通过频段跨度获取数据的时间为,其中L为跨频段时的左端频段数,R为跨频段时的右端频段数。综上所述,其时间复杂度公式为,,其中D为部分区间情况下的时间常量合并,E为跨频段情况下的时间常量合并,M为划分的频段数。根据等价树形法[5],不难计算公式的平均时间复杂度为:,忽略低阶和常量,。

通过分析,其平均时间复杂度要优于快速排序算法[6]。跨频段获取数据要比部分区间获取数据复杂(跨频段包括两端数据获取和中间的全区间获取;部分区间仅仅涉及单个频段)。如果两端的数据量较小时,因为堆排序的是部分数据,时间复杂度默认为常量,优于整体的区间排序。当获取数据较多(仅仅整个频段数据量时),排序接近堆排序时间,而堆排序的性能要弱于快速排序,所以频段M选择的时尽可能的使得所取数据在同一频段内,保证数据排序快速高效。

2.4空间复杂度分析

通过算法分析,该算法的空间复杂度由分段数组(M)、分段频数累计数组(M)、数据重排数组(P)和输出数组(R)构成。分段数组和分段频数累计数组由业务决定,也可以说是具体业务的常量。数据重排数组与问题规模一致,为n的规模函数。数据数组与所取数据一致,具体根据业务确定,最大问题规模为n。忽略常量,其空间复杂度为。

3实验方法与结果分析

为了验证本算法的实际性能,本研究采用对比实验方法。对比的对象为快速排序算法。

为了模拟实际的操作场景,选择数据量在10万至100万的随机数据(网站访问日志基本都大于这个数据,本期先解决内排序问题,所以问题规模取100万以内数据)。抽样样本选择10万、20万、30万、40万、50万、60万、70万、80万、90万和100万的数据,测试次数为5次。样本数据由计算机随机生成。为了测试部分区间取数和跨频段取数,获取第1000到6000条数据。因为10W理论最大频段带宽1000,100万理论最大频段带宽为10000,便于生成跨段数据和部分频段数据,所以频段取100。

测试环境:win64位win10系统,英特尔Core(TM)i5-4460处理器,8G内存

1本算法与快速排序实验结果对比

 数据量

第1次(ms)

第2次(ms)

喊话

快速

喊话

快速

10w

8.8258

24.5697

3.573

19.4773

20w

13.2155

45.6709

12.2702

45.2331

30w

23.7011

52.0409

27.4297

55.0725

40w

42.4122

72.5471

49.4512

70.6461

50w

63.193

100.6848

63.0035

91.8654

60w

13.7495

113.1636

12.7504

108.8653

70w

16.0248

139.8544

15.2194

131.9484

80w

18.0659

158.1161

16.9386

150.2258

90w

20.6297

179.422

19.46

172.7602

100w

22.3652

206.6391

22.3014

189.1991

2本算法与快速排序实验结果对比

 数据量

第3次(ms)

第4次(ms)

喊话

快速

喊话

快速

10w

4.3136

19.934

14.7755

30.9893

20w

13.8354

45.5183

13.9435

47.5351

30w

25.3302

51.4837

24.3336

51.9052

40w

39.1099

71.7607

41.5151

71.1878

50w

65.0524

92.9575

63.3463

90.5247

60w

12.6445

110.5534

89.599

110.715

70w

15.8985

130.7257

16.0402

130.8483

80w

19.2973

151.1634

18.9198

153.5619

90w

20.5617

172.3641

20.7253

173.4401

100w

22.9002

193.5984

22.194

192.0752

3本算法与快速排序实验结果对比

 数据量

第5次(ms)

平均

喊话

快速

喊话

快速

快速/喊话

10w

4.3255

20.2342

7.16268

23.0409

3.216799

20w

13.5038

46.0809

13.35368

46.00766

3.445317

30w

24.1351

53.1237

24.98594

52.7252

2.110195

40w

42.0969

72.9474

42.91706

71.81782

1.67341

50w

65.6817

93.0191

64.05538

93.8103

1.464519

60w

13.4457

111.3523

28.43782

110.9299

3.900788

70w

15.0328

130.7848

15.64314

132.8323

8.49141

80w

16.8305

146.5838

18.01042

151.9302

8.435683

90w

19.4478

171.8165

20.1649

173.9606

8.6269

100w

21.4771

194.0227

22.24758

195.1069

8.769803

通过1,2,3实验结果得出1)喊话模式的排序方式明显优于快速排序,适合快速的随机获取排序数据。当数据在10万至100万之间,快速排序算法平均耗时是本算法的1.5倍以上,最大耗时是其8.7倍2)数据量在10万到50万时,喊话模式的消耗时间逐增,达到60万时下降后再逐增。

经分析,此现象的原因:当为50万时,数据跨越两个频段,端数据通过堆排序处理,最终获取数据。堆排序要频繁的进行建堆操作,并且数据要进行合并所以处理速度要慢;当数据达到60万时,数据在一个频段,只需对当前频段进行快速排序获取即可。

实验结果与算法的时间复杂度分析结果一致,因此建议选取频段时尽可能的将所取数据包括在同一频段之内。

4结语

本算法是针对数据排名场景提出的一种优化算法,其获取速度明显优于快速排序,平均时间复杂度为。通过实验证明:数据获取的速度与频段划分相关,尽可能的将获取数据存在一个频段中,可以缩短获取数据时间。本算法获取数据的速度明显优于快速排序。数据为100万时,快速排序算法耗时是其8.7倍。

本算法可以在排名统计的任何场景应用,例如统计访问最多的当月用户、访问最多的产品访问、访问最多的主机等。数据应用前需要将应用数据过滤清洗,使之符合排序的数据序列,但本研究不适用于外排序场景。

由于频段的获取需要依赖于具体的业务经验,这是本研究的不足之处。接下来将会对于怎样智能的选择频段对本算法改进。其次,本研究是针对内排序的改进,对于大数据量的外排序并没有涉及(虽然最终的外排序最终转化为本机的内排序,但是应用的结构场景不同)。对于大型的业务网站而言,外排序应用的场景更多,这将是未来的主要研究方向。

参考文献(References)

[1] 袁九惕..常用排序程序算法及分析[J].湖南城市学院学报,19892(6):70-76.

[2]朱建莉,刘宏强.常用排序算法综述[J].胜利油田师范专科学校学报.2002,16(4):27-29. 

[3]余冬梅.一种基于堆的快速排序算法[J].科学技术与工程.2014,14(35):80-83.

[4] Thomas H.Cormen, Charles E.Leiserson, Ronald L.Rivest, Clifford Stein..算法导论[M].第二版,潘金贵,顾铁成,李成法等译.机械工业出版社.2006:12-22

[5] CAR HoareQuicksort[J].Computer Journal 1962 , 5 (1) :10-15.

[6]唐向阳.分段快速排序法[J].软件学报1993,4(2):53-57

这篇关于一种基于喊话模式的排序算法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/714735

相关文章

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

SpringBoot如何通过Map实现策略模式

《SpringBoot如何通过Map实现策略模式》策略模式是一种行为设计模式,它允许在运行时选择算法的行为,在Spring框架中,我们可以利用@Resource注解和Map集合来优雅地实现策略模式,这... 目录前言底层机制解析Spring的集合类型自动装配@Resource注解的行为实现原理使用直接使用M

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

C++快速排序超详细讲解

《C++快速排序超详细讲解》快速排序是一种高效的排序算法,通过分治法将数组划分为两部分,递归排序,直到整个数组有序,通过代码解析和示例,详细解释了快速排序的工作原理和实现过程,需要的朋友可以参考下... 目录一、快速排序原理二、快速排序标准代码三、代码解析四、使用while循环的快速排序1.代码代码1.由快

C#原型模式之如何通过克隆对象来优化创建过程

《C#原型模式之如何通过克隆对象来优化创建过程》原型模式是一种创建型设计模式,通过克隆现有对象来创建新对象,避免重复的创建成本和复杂的初始化过程,它适用于对象创建过程复杂、需要大量相似对象或避免重复初... 目录什么是原型模式?原型模式的工作原理C#中如何实现原型模式?1. 定义原型接口2. 实现原型接口3

大数据spark3.5安装部署之local模式详解

《大数据spark3.5安装部署之local模式详解》本文介绍了如何在本地模式下安装和配置Spark,并展示了如何使用SparkShell进行基本的数据处理操作,同时,还介绍了如何通过Spark-su... 目录下载上传解压配置jdk解压配置环境变量启动查看交互操作命令行提交应用spark,一个数据处理框架

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》:本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1

Spring排序机制之接口与注解的使用方法

《Spring排序机制之接口与注解的使用方法》本文介绍了Spring中多种排序机制,包括Ordered接口、PriorityOrdered接口、@Order注解和@Priority注解,提供了详细示例... 目录一、Spring 排序的需求场景二、Spring 中的排序机制1、Ordered 接口2、Pri