`
cgs1999
  • 浏览: 536377 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

嵌套For循环性能优化案例

阅读更多
1 案例描述
某日,在JavaEye上看到一道面试题,题目是这样的:请对以下的代码进行优化
for (int i = 0; i < 1000; i++)
	for (int j = 0; j < 100; j++)
		for (int k = 0; k < 10; k++)
			testFunction (i, j, k);

(注:为了同后面的内容一致,这里对原题目进行了部分修改)

2 案例分析
从给出的代码可知,不论如何优化,testFunction执行的次数都是相同的,该部分不存在优化的可能。那么,代码的优化只能从循环变量i、j、k的实例化、初始化、比较、自增等方面的耗时上进行分析。
首先,我们先分析原题代码循环变量在实例化、初始化、比较、自增等方面的耗时情况:
变量 实例化(次数) 初始化(次数) 比较(次数) 自增(次数)
i 1 1 1000 1000
j 1000 1000 1000 * 100 1000 * 100
k 1000 * 100 1000 * 100 1000 * 100 * 10 1000 * 100 * 10

(注:由于单次耗时视不同机器配置而不同,上表相关耗时采用处理的次数进行说明)
该代码的性能优化就是尽可能减少循环变量i、j、k的实例化、初始化、比较、自增的次数,同时,不能引进其它可能的运算耗时。

3 解决过程
从案例分析,对于原题代码,我们提出有两种优化方案:
3.1 优化方案一
代码如下:
for (int i = 0; i < 10; i++)
	for (int j = 0; j < 100; j++)
		for (int k = 0; k < 1000; k++)
			testFunction (k, j, i);

该方案主要是将循环次数最少的放到外面,循环次数最多的放里面,这样可以最大程度的(注:3个不同次数的循环变量共有6种排列组合情况,此种组合为最优)减少相关循环变量的实例化次数、初始化次数、比较次数、自增次数,方案耗时情况如下:
变量 实例化(次数) 初始化(次数) 比较(次数) 自增(次数)
i 1 1 10 10
j 10 10 10 * 100 10 * 100
k 10 * 100 10 * 100 10 * 100 * 1000 10 * 100 * 1000


3.2 优化方案二
代码如下:
int i, j, k;
for (i = 0; i < 10; i++)
	for (j = 0; j < 100; j++)
		for (k = 0; k < 1000; k++)
			testFunction (k, j, i);

该方案在方案一的基础上,将循环变量的实例化放到循环外,这样可以进一步减少相关循环变量的实例化次数,方案耗时情况如下:
变量 实例化(次数) 初始化(次数) 比较(次数) 自增(次数)
i 1 1 10 10
j 1 10 10 * 100 10 * 100
k 1 10 * 100 10 * 100 * 1000 10 * 100 * 1000


4 解决结果
那么,提出的优化方案是否如我们分析的那样有了性能上的提升了呢?我们编写一些测试代码进行验证,数据更能说明我们的优化效果。
4.1 测试代码
public static void testFunction(int i, int j, int k) {
		System.out.print("");	// 注:该方法不影响整体优化,这里只有简单输出
	}

	public static void testA() {
		long start = System.nanoTime();
		for (int i = 0; i < 1000; i++)
			for (int j = 0; j < 100; j++)
				for (int k = 0; k < 10; k++)
					testFunction(i, j, k);
		System.out.println("testA time>>" + (System.nanoTime() - start));
	}

	public static void testB() {
		long start = System.nanoTime();
		for (int i = 0; i < 10; i++)
			for (int j = 0; j < 100; j++)
				for (int k = 0; k < 1000; k++)
					testFunction(k, j, i);
		System.out.println("testB time>>" + (System.nanoTime() - start));
	}

	public static void testC() {
		long start = System.nanoTime();
		int i;
		int j;
		int k;
		for (i = 0; i < 10; i++)
			for (j = 0; j < 100; j++)
				for (k = 0; k < 1000; k++)
					testFunction(k, j, i);
		System.out.println("testC time>>" + (System.nanoTime() - start));
}

4.2 测试结果
1、测试机器配置:Pentium(R) Dual-Core CPU E5400 @2.70GHz 2.70GHz, 2GB内存;
2、循环变量i、j、k循环次数分别为10、100、1000,进行5组测试,测试结果如下:
第1组 第2组 第3组 第4组 第5组
原方案 171846271 173250166 173910870 173199875 173725328
方案一 168839312 168466660 168372616 168310190 168041251
方案二 168001838 169141906 168230655 169421766 168240748

从上面的测试结果来看,优化后的方案明显性能优于原方案,达到了优化的效果。但优化方案二并没有如我们预期的优于方案一,其中第2、4、5组的数据更是比方案一差,怀疑可能是循环次数太少,以及测试环境相关因素影响下出现的结果。

3、重新调整循环变量i、j、k循环次数分别为20、200、2000,进行5组测试,测试结果如下:
第1组 第2组 第3组 第4组 第5组
原方案 1355397203 1358978176 1358128281 1350193682 1354786598
方案一 1343482704 1348410388 1343978037 1347919156 1340697793
方案二 1342427528 1343897887 1342662462 1342124048 1336266453

从上面的测试结果来看,优化后的方案基本符合我们的预期结果。

5 总结
从案例分析和解决过程中的三个表的分析可知,优化方案一和优化方案二的性能都比原代码的性能好,其中优化方案二的性能是最好的。在嵌套For循环中,将循环次数多的循环放在内侧,循环次数少的循环放在外侧,其性能会提高;减少循环变量的实例化,其性能也会提高。从测试数据可知,对于两种优化方案,如果在循环次数较少的情况下,其运行效果区别不大;但在循环次数较多的情况下,其效果就比较明显了。

6 参考资料
[1] http://www.javaeye.com/topic/762312
[2] http://www.javaeye.com/topic/632481
2
1
分享到:
评论
2 楼 cgs1999 2012-07-19  
iceblooded 写道
方案二的优势其实并不明显,我把数值同时都提高了一个量级 循环数都乘10,结果方案一胜出,优于方案二



理论上讲方案二应该会比较快的,但两种方案的区别就在于变量的实例化,且变量实例化的时间非常非常短,实际测试确实会有你说的情况,这个应该同测试机当时的运行状态有关,这也是我对每一种方案要分别做5组测试数据的原因。


正如我文后总结也指出“如果在循环次数较少的情况下,其运行效果区别不大;但在循环次数较多的情况下,其效果就比较明显了”。方案二的优势体现在循环次数非常非常多的情况才会比较明显,具体你可以分别将i,j,k的数值分别提高1万倍或者更高,这样其优势即可体现出来了。
1 楼 iceblooded 2012-07-18  
方案二的优势其实并不明显,我把数值同时都提高了一个量级 循环数都乘10,结果方案一胜出,优于方案二

相关推荐

    javaEE-嵌套For循环性能优化案例借鉴.pdf

    本文通过一个具体的案例,探讨了如何对嵌套for循环进行性能优化。 案例中的原始代码如下: ```java for (int i = 0; i ; i++) for (int j = 0; j ; j++) for (int k = 0; k ; k++) testFunction(i, j, k); ``` ...

    For循环嵌套要点和难点具体案例

    2. **网格计算**:如求解棋盘上的所有可能路径、计算像素图像等,可以用嵌套for循环来生成坐标网格。 3. **算法实现**:许多经典算法,如冒泡排序、选择排序,都需要使用到嵌套循环。 四、难点与注意事项 1. **性能...

    循环嵌套案例.rar

    3. 优化性能:循环嵌套可能导致计算量增大,注意优化代码以提高效率,如减少循环次数、并行化处理等。 4. 适当使用break和continue:在某些情况下,可能需要提前终止循环或跳过当前迭代,合理使用这些语句可以增强...

    python for循环优化

    本文以一个实际案例出发,探讨如何优化Python的for循环以提高程序效率。 一、问题背景 在项目初期,由于用户数量较少,使用了两层嵌套的for循环来完成计算任务,耗时1-2小时。然而,随着用户基数的增长,项目运行...

    C#中for循环的交换排序案例 c#经典案例.pdf

    在提供的代码示例中,这种排序方法通过两个嵌套的for循环实现。外层循环(i)遍历数组的所有元素,内层循环(j)从当前元素的下一个位置开始,直到数组末尾。如果当前元素(num[i])大于其后面的元素(num[j]),则...

    Oracle查询优化改写技巧与案例

    Oracle数据库是全球广泛使用的大型关系型数据库管理系统,其性能优化是DBA和开发人员日常工作中不可或缺的部分。查询优化是提高数据库性能的关键环节,通过合理的查询改写,可以显著提升数据检索速度,降低系统资源...

    Vivado HLS 视频课程总结

    15 for循环优化-基本性能指标 40 15.1 基本衡量指标 40 15.2 for循环pipeline 41 15.3 for循环UNROLL展开 41 15.4 for循环变量i 42 16 for循环优化-循环合并 42 17 for循环优化-数据流 46 18 for循环优化-嵌套的for...

    循环结构进阶练习.zip

    - **循环优化**:学习如何通过减少循环次数、提前退出条件等方法提高程序性能。 - **迭代器(Iterator)**:在处理集合时,Java提供了迭代器接口,它能方便地遍历集合元素,尤其在进行循环操作时。 通过“教学演示...

    Intel FPGA SDK for OpenCL Best Practices Guide

    循环信息部分不仅分析了循环的使用,还提供了通过改变内存访问模式、使用循环合并减少嵌套循环消耗的面积等案例。区域信息分析则包括了源代码和系统级别的区域分析。 针对内存复制和停滞情况的验证,文档提供了系统...

    [精华] 通过分析SQL语句的执行计划优化SQL(总结)7年DBA工作经验.docx

    - 优化不仅是DBA的责任,应用设计人员和开发人员也需要了解数据库知识,共同参与性能优化。 7. **总结** SQL优化是一个系统工程,涉及到应用设计、开发和DBA的协同工作。通过深入理解SQL执行计划,我们可以找出...

    《C语言程序设计》中循环结构的教学方法探讨.pdf

    其次,对于for循环,教学应从其初始化、条件检查、迭代更新三部分着手。通过实例演示,如计数器或数组遍历,让学生了解每一部分的作用。同时,强调初始化和迭代更新的重要性,避免无限循环的发生。 接着,讲解while...

    Oracle 中HINT的使用

    8. **数据库优化案例**:提供的PDF文档可能包含了实际的Oracle数据库优化案例,这些案例通常会展示在不同场景下如何通过HINT和其他手段进行性能改进。 9. **淘宝数据库架构演进**:淘宝作为大型电商网站,其数据库...

    Oracle_sql性能的调整

    - **连接方式**: 如嵌套循环(Nested Loops)、哈希连接(Hash Join)等。 #### 六、干预执行计划 **6.1 使用Hints提示** - Hints允许开发者直接控制优化器的行为,指定特定的执行路径。 - 示例:`/*+ INDEX(t1 idx1)...

    Matlab高效编程技巧与应用+案例

    3. **函数设计**:合理使用嵌套函数和局部变量,减少全局变量的使用,提高代码可读性和性能。 4. **并行计算**:利用Matlab的并行计算工具箱,如`parfor`循环,将任务分配到多个处理器上,加速计算。 5. **错误...

    火山PC三维数组的使用案例_理论上可以无数维

    这通常通过嵌套循环实现,例如`for(x=0; x; x++) for(y=0; y; y++) for(z=0; z; z++)`。 4. **性能优化**:在火山PC这样的高性能平台上,数组访问速度和内存访问模式对性能有很大影响。理解数据局部性原理并优化...

    性能调优——Oracle索引技术的应用与剖析

    在比对过程中,使用游标(Cursor info)和嵌套循环来逐条处理比对结果。然而,这种方式可能会导致大量的磁盘I/O操作,降低效率。在大型数据库中,更推荐使用并行查询或者批量处理,以减少物理I/O和提升处理速度。...

    求因子数量.docx

    在这个案例中,嵌套循环被用来求解一个数的所有因子数量。下面我们将深入探讨这个主题。 首先,程序的目标是找到1到n之间每个数的因子个数。因子是一个整数a可以被另一个整数b整除,即a/b没有余数,那么b就是a的...

    编程技能训练与等级考试辅导:循环控制.ppt

    4. **多重循环**:程序中可能会使用到多层循环,例如,猜数字游戏可能扩展为二维数组形式,让用户猜矩阵中的一个数,这时就会用到嵌套的for循环。 5. **循环跳转语句**:`break`和`continue`语句用来控制循环的行为...

    c#编程技巧典型案例解析

    其次,C#支持多种控制流结构,如if语句、switch语句、循环(for、while、foreach)以及异常处理(try-catch-finally)。熟练掌握这些语法结构,能够编写出逻辑清晰、易于维护的代码。例如,通过案例我们可以学习如何...

    参考资料-环路学习笔记20180529.zip

    在计算机科学中,环路学习可能指的是循环结构的学习,如for、while循环等,以及递归算法的理解。递归是一种强大的编程技术,它允许函数调用自身来解决问题,通常用于树形结构遍历、排序算法(如快速排序、归并排序)...

Global site tag (gtag.js) - Google Analytics