调整法建堆过程的优化

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

相关文章

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. 自定义过滤

Python如何使用__slots__实现节省内存和性能优化

《Python如何使用__slots__实现节省内存和性能优化》你有想过,一个小小的__slots__能让你的Python类内存消耗直接减半吗,没错,今天咱们要聊的就是这个让人眼前一亮的技巧,感兴趣的... 目录背景:内存吃得满满的类__slots__:你的内存管理小助手举个大概的例子:看看效果如何?1.

一文详解SpringBoot响应压缩功能的配置与优化

《一文详解SpringBoot响应压缩功能的配置与优化》SpringBoot的响应压缩功能基于智能协商机制,需同时满足很多条件,本文主要为大家详细介绍了SpringBoot响应压缩功能的配置与优化,需... 目录一、核心工作机制1.1 自动协商触发条件1.2 压缩处理流程二、配置方案详解2.1 基础YAML

java中使用POI生成Excel并导出过程

《java中使用POI生成Excel并导出过程》:本文主要介绍java中使用POI生成Excel并导出过程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录需求说明及实现方式需求完成通用代码版本1版本2结果展示type参数为atype参数为b总结注:本文章中代码均为

MySQL中慢SQL优化的不同方式介绍

《MySQL中慢SQL优化的不同方式介绍》慢SQL的优化,主要从两个方面考虑,SQL语句本身的优化,以及数据库设计的优化,下面小编就来给大家介绍一下有哪些方式可以优化慢SQL吧... 目录避免不必要的列分页优化索引优化JOIN 的优化排序优化UNION 优化慢 SQL 的优化,主要从两个方面考虑,SQL 语

MySQL中慢SQL优化方法的完整指南

《MySQL中慢SQL优化方法的完整指南》当数据库响应时间超过500ms时,系统将面临三大灾难链式反应,所以本文将为大家介绍一下MySQL中慢SQL优化的常用方法,有需要的小伙伴可以了解下... 目录一、慢SQL的致命影响二、精准定位问题SQL1. 启用慢查询日志2. 诊断黄金三件套三、六大核心优化方案方案

SpringCloud之LoadBalancer负载均衡服务调用过程

《SpringCloud之LoadBalancer负载均衡服务调用过程》:本文主要介绍SpringCloud之LoadBalancer负载均衡服务调用过程,具有很好的参考价值,希望对大家有所帮助,... 目录前言一、LoadBalancer是什么?二、使用步骤1、启动consul2、客户端加入依赖3、以服务