调整法建堆过程的优化

2024-05-08 18:58
文章标签 优化 过程 建堆 调整法

本文主要是介绍调整法建堆过程的优化,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!



        用调整法建堆,并在如下几个方面进行优化:(a)递归函数改成while循环;(b)减少比较次数;(c)减少交换次数;

源代码如下:

#include <string>
#include <fstream>
#include <stdlib.h>
#include <iostream>
#include <sys/time.h>
using namespace std;
#define MAX 10000000void readNum(int a[]){string filename;ifstream infile("data_1000w.txt", ios::in);string textline = "";int i = 0;while(getline(infile, textline, '\n')){a[i] = atoi(string(textline).c_str());//cout << textline << endl;i++;}infile.close();
}long getCurrentTime(){struct timeval tv;gettimeofday(&tv, NULL);return tv.tv_sec * 1000 + tv.tv_usec / 1000;
}int verify(int a[]){for(int i = 0; i < MAX - 1; i++){if(a[i] < a[i+1])return -1;}return 0;
}//原函数---------------------------------------------------void minHeapify(int a[], int heapsize, int index)
{int left = 2*index + 1;int right = 2*index + 2;int min = index;int tmp = -1;if(left < heapsize){if(a[min] > a[left]){min = left;}if(right < heapsize && a[min] > a[right]){min = right;}}if(min != index){tmp = a[min];a[min] = a[index];a[index] = tmp;minHeapify(a, heapsize, min);}
}int buildMinHeap_1(int a[], int length)
{int heapsize = length;if(heapsize < 2){return 0;}for(int i =heapsize/2 - 1; i >= 0; i--){minHeapify(a, heapsize, i);}return 1;
}void heapSort_1(int a[], int length){buildMinHeap_1(a,length);int tmp = -1;for(int i = length-1; i>=0; i--){tmp = a[0];a[0] = a[i];a[i] = tmp;minHeapify(a, i, 0);}
}//优化后的函数--------------------------------------------------void minHeapify_2(int a[], int length, int index)
{int left, right, min, tmp;while(2*index + 1 < length){left = 2*index + 1;right = 2*index + 2;min = index;if(left < length){if(a[min] > a[left]){min = left;}if(right < length && a[min] > a[right]){min = right;}}if(min != index){tmp = a[index];a[index] = a[min];a[min] = tmp;}else{break;}index = min;}
}void minHeapify_3(int a[], int length, int index)
{int child, tmp;while(2*index + 1 < length){child = 2*index + 1;if(child != length -1 && a[child+1] < a[child]){child++;}if(a[index] > a[child]){tmp = a[index];a[index] = a[child];a[child] = tmp;}else{break;}index = child;}
}void minHeapify_4(int a[], int length, int index)
{int child, tmp;tmp = a[index];while(2*index + 1 < length){child = 2*index + 1;if(child != length -1 && a[child+1] < a[child]){child++;}if(tmp > a[child]){a[index] = a[child];}else{break;}index = child;}a[index] = tmp;
}void heapSort_2(int a[], int length){int tmp = -1;for(int i = length/2 - 1; i >= 0; i--){minHeapify_2(a, length, i);}for(int i = length-1; i > 0; i--){tmp = a[0];a[0] = a[i];a[i] = tmp;minHeapify_2(a, i, 0);}
}void heapSort_3(int a[], int length){int tmp = -1;for(int i = length/2 - 1; i >= 0; i--){minHeapify_3(a, length, i);}for(int i = length-1; i > 0; i--){tmp = a[0];a[0] = a[i];a[i] = tmp;minHeapify_3(a, i, 0);}
}void heapSort_4(int a[], int length){int tmp = -1;for(int i = length/2 - 1; i >= 0; i--){minHeapify_4(a, length, i);}for(int i = length-1; i > 0; i--){tmp = a[0];a[0] = a[i];a[i] = tmp;minHeapify_4(a, i, 0);}
}//---------------------------------------------------main(){int a[MAX] = {0};int b[MAX] = {0};int c[MAX] = {0};int d[MAX] = {0};/*srand((unsigned)time(NULL));for(int i = 0; i < MAX; i++){a[i] = rand()%MAX;cout << a[i] << endl;}*/readNum(a);readNum(b);readNum(c);readNum(d);cout << "----1111-----" << endl;long time_1_1 = getCurrentTime();heapSort_1(a, MAX);long time_1_2 = getCurrentTime();cout << time_1_2 - time_1_1 << endl;int aa = verify(a);cout << aa << endl;	cout << "----2222-----" << endl;long time_2_1 = getCurrentTime();heapSort_2(b, MAX);long time_2_2 = getCurrentTime();cout << time_2_2 - time_2_1 << endl;int bb = verify(b);cout << bb << endl;	cout << "----3333-----" << endl;long time_3_1 = getCurrentTime();heapSort_3(c, MAX);long time_3_2 = getCurrentTime();cout << time_3_2 - time_3_1 << endl;int cc = verify(c);cout << cc << endl;	cout << "----4444-----" << endl;long time_4_1 = getCurrentTime();heapSort_4(d, MAX);long time_4_2 = getCurrentTime();cout << time_4_2 - time_4_1 << endl;int dd = verify(d);cout << dd << endl;	/*for(int k = 0; k < MAX; k++){cout << d[k] <<endl;}*/
}



        依次记录上述优化的幅度,结果如下图所示:1、2、3、4分别为原算法、递归函数改成while循环、减少比较次数、减少交换次数的运行时间(单位:毫秒)。两幅图分别为100w和1000w数据量的时间耗费。 

100万数据量:

改进后,相对于原函数的优化幅度分别为:8.1%、17.3%、27.6%。


1000万数据量:


改进后,相对于原函数的优化幅度分别为:5.6%、22.3%、30.4%。


        下面讨论为什么同样的程序,不同的数据规模,各种优化方案的优化幅度不一致,考虑两种情况:
         一方面这个可能和待排序的数据有关。由于原始数据是随机的,因此待排序的数据初始的状态是不确定的,它们的本身是否有序对排序有一定的影响。
        另一方面考虑排序算法本身的因素。排序过程比较耗费时间的主要有两个方面:一个是数据的比较、数据交换、递归过程(分配局部栈等开销)。下面从这三个方面进行分析:
        (1)首先,对于第一种优化,即把递归函数改为循环,堆调整函数minHeapify_2比minHeapify_1的改进就是将递归改成了循环,数据的比较次数、数据交换的次数都没有改变。在数据规模增大到10倍以后,数据比较次数、数据交换次数都以10log10的数量级增长,而且占总体时间复杂度的绝大部分;同时minHeapify_1递归过程的时间复杂度并没有同步上升。因此在表现上,将递归改写为循环的优化效果会随着数据规模的上升变得越来越不明显。
        (2)第二,对于第二种优化,即把递归函数改为循环,同时减少了比较次数。堆调整函数minHeapify_3比minHeapify_1的改进就是将递归改成了循环,同时减少了数据的比较次数(由5次减到三次,减少40%),但数据交换的次数没有改变。在数据规模增大到10倍以后,影响时间复杂度的三个因素中数据比较次数相对减少成为影响总体时间复杂度的最明显因素。因此在表现上,这种优化效果会随着数据规模的上升变得越来越明显。同时也说明了虽然单次数据比较比单次数据交换需要的时间少很多,但是在堆排序的问题中,数据比较的频次相当的多,因此在总体的时间消耗中也占据了很大的一部分。
        (3)第三,对于第三种优化,即把递归函数改为循环,同时减少了比较次数和交换次数。堆调整函数minHeapify_4比minHeapify_1的改进就是将递归改成了循环,同时减少了数据的比较次数(由5次减到三次,减少40%),数据交换的次数也大大减少。在数据规模增大到10倍以后,影响时间复杂度的三个因素在改进后的算法都进行了优化。在原函数的时间复杂度随着10log10增长时,优化后的算法时间复杂度并没有同步上升。因此在表现上,这种优化效果会随着数据规模的上升变得越来越明显。

这篇关于调整法建堆过程的优化的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

MySQL索引的优化之LIKE模糊查询功能实现

《MySQL索引的优化之LIKE模糊查询功能实现》:本文主要介绍MySQL索引的优化之LIKE模糊查询功能实现,本文通过示例代码给大家介绍的非常详细,感兴趣的朋友一起看看吧... 目录一、前缀匹配优化二、后缀匹配优化三、中间匹配优化四、覆盖索引优化五、减少查询范围六、避免通配符开头七、使用外部搜索引擎八、分

PyInstaller打包selenium-wire过程中常见问题和解决指南

《PyInstaller打包selenium-wire过程中常见问题和解决指南》常用的打包工具PyInstaller能将Python项目打包成单个可执行文件,但也会因为兼容性问题和路径管理而出现各种运... 目录前言1. 背景2. 可能遇到的问题概述3. PyInstaller 打包步骤及参数配置4. 依赖

Python通过模块化开发优化代码的技巧分享

《Python通过模块化开发优化代码的技巧分享》模块化开发就是把代码拆成一个个“零件”,该封装封装,该拆分拆分,下面小编就来和大家简单聊聊python如何用模块化开发进行代码优化吧... 目录什么是模块化开发如何拆分代码改进版:拆分成模块让模块更强大:使用 __init__.py你一定会遇到的问题模www.

SpringBoot首笔交易慢问题排查与优化方案

《SpringBoot首笔交易慢问题排查与优化方案》在我们的微服务项目中,遇到这样的问题:应用启动后,第一笔交易响应耗时高达4、5秒,而后续请求均能在毫秒级完成,这不仅触发监控告警,也极大影响了用户体... 目录问题背景排查步骤1. 日志分析2. 性能工具定位优化方案:提前预热各种资源1. Flowable

SpringBoot3实现Gzip压缩优化的技术指南

《SpringBoot3实现Gzip压缩优化的技术指南》随着Web应用的用户量和数据量增加,网络带宽和页面加载速度逐渐成为瓶颈,为了减少数据传输量,提高用户体验,我们可以使用Gzip压缩HTTP响应,... 目录1、简述2、配置2.1 添加依赖2.2 配置 Gzip 压缩3、服务端应用4、前端应用4.1 N

将Mybatis升级为Mybatis-Plus的详细过程

《将Mybatis升级为Mybatis-Plus的详细过程》本文详细介绍了在若依管理系统(v3.8.8)中将MyBatis升级为MyBatis-Plus的过程,旨在提升开发效率,通过本文,开发者可实现... 目录说明流程增加依赖修改配置文件注释掉MyBATisConfig里面的Bean代码生成使用IDEA生

Spring Boot + MyBatis Plus 高效开发实战从入门到进阶优化(推荐)

《SpringBoot+MyBatisPlus高效开发实战从入门到进阶优化(推荐)》本文将详细介绍SpringBoot+MyBatisPlus的完整开发流程,并深入剖析分页查询、批量操作、动... 目录Spring Boot + MyBATis Plus 高效开发实战:从入门到进阶优化1. MyBatis

MyBatis 动态 SQL 优化之标签的实战与技巧(常见用法)

《MyBatis动态SQL优化之标签的实战与技巧(常见用法)》本文通过详细的示例和实际应用场景,介绍了如何有效利用这些标签来优化MyBatis配置,提升开发效率,确保SQL的高效执行和安全性,感... 目录动态SQL详解一、动态SQL的核心概念1.1 什么是动态SQL?1.2 动态SQL的优点1.3 动态S

C# WinForms存储过程操作数据库的实例讲解

《C#WinForms存储过程操作数据库的实例讲解》:本文主要介绍C#WinForms存储过程操作数据库的实例,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、存储过程基础二、C# 调用流程1. 数据库连接配置2. 执行存储过程(增删改)3. 查询数据三、事务处

JSON Web Token在登陆中的使用过程

《JSONWebToken在登陆中的使用过程》:本文主要介绍JSONWebToken在登陆中的使用过程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录JWT 介绍微服务架构中的 JWT 使用结合微服务网关的 JWT 验证1. 用户登录,生成 JWT2. 自定义过滤