`

javascript之算法优化

阅读更多

正如其他编程语言,代码的写法和算法选用影响javascript的运行时间。与其他编程语言不同的是,javascript可用资源有限,所以优化技术更为重要。

 

一。for,while,do-while循环的性能特性相似,谁也不比谁更快或更慢。除非你要迭代遍历一个属性未知的对象,否则不要使用for-in循环。

 

由于每次迭代操作要搜索实例或原形的属性,for-in 循环每次迭代都要付出更多开销,所以比其他类型

循环慢一些。如果你迭代遍历一个有限的,已知的属性列表,使用其他循环类型更快,可使用如下模式:

 

var props = ["prop1", "prop2"],
var i = 0;
var len = props.length;
while (i < len){
process(object[props[i]]);
i++;
}

 

 

 

二。改善循环性能的最好方法是减少每次迭代中的运算量,并减少循环迭代次数。

 

//slow
for (var i=0; i < items.length; i++){
process(items[i]);
}
//faster
for (var i=0, len=items.length; i < len; i++){
process(items[i]);
}
//fastest
for (var i=items.length; i--; ){
process(items[i]);
}

 达夫设备是一个循环体展开技术,在一次迭代中实际上执行了多次迭代操作。

 

 

var i = items.length % 8;
while(i){
process(items[i--]);
}
i = Math.floor(items.length / 8);
while(i){
process(items[i--]);
process(items[i--]);
process(items[i--]);
process(items[i--]);
process(items[i--]);
process(items[i--]);
process(items[i--]);
process(items[i--]);
}

 

 

三。一般来说,switch总是比if-else更快,但并不总是最好的解决方法。当判断条件较多时,查表法比if-else或者switch更快。

 

//slow
if (value == 0){
return result0;
} else if (value == 1){
return result1;
} else if (value == 2){
return result2;
} else if (value == 3){
return result3;
} else if (value == 4){
return result4;
} else if (value == 5){
return result5;
} else if (value == 6){
return result6;
} else if (value == 7){
return result7;
} else if (value == 8){
return result8;
} else if (value == 9){
return result9;
} else {
return result10;
}

//faster,二分搜索法(此方法适用于需要测试大量数值的情况(相对离散值来说switch 更合适)
if (value < 6){
if (value < 3){
if (value == 0){
return result0;
} else if (value == 1){
return result1;
} else {
return result2;
}
} else {
if (value == 3){
return result3;
} else if (value == 4){
return result4;
} else {
return result5;
}
}
} else {
if (value < 8){
if (value == 6){
return result6;
} else {
return result7;
}
} else {
if (value == 8){
return result8;
} else if (value == 9){
return result9;
} else {
return result10;
}
}
}
//查表法
//define the array of results
var results = [result0, result1, result2, result3, result4, result5, result6, result7, result8, result9, result10]
//return the correct result
return results[value];

 

 

四。浏览器的调用栈尺寸限制了递归算法在javascript中的应用,栈溢出错误导致其他代码也不能正常执行。如果你遇到一个栈溢出错误,将方法修改为一个迭代算法或者使用制表法可以避免重复工作。

 

 

JavaScript 引擎所支持的递归数量与JavaScript 调用栈大小直接相关。只有Internet Explorer 例外,它的

调用栈与可用系统内存相关,其他浏览器有固定的调用栈限制。大多数现代浏览器的调用栈尺寸比老式浏

览器要大(例如Safari 2 调用栈尺寸是100).当你使用了太多的递归,超过最大调用栈尺寸时,浏览器会出错并弹出以下信息:

 

• Internet Explorer: “Stack overflow at line x”

• Firefox: “Too much recursion”

• Safari: “Maximum call stack size exceeded”

• Opera: “Abort (control stack overflow)”

Chrome 是唯一不显示调用栈溢出错误的浏览器。

 

递归模式一:一个函数调用自身

 

function recurse(){
recurse();
}
recurse();

 递归模式二:精巧模式,两个函数互相调用对方

 

 

 

 

function first(){
second();
}
function second(){
first();
}
first();

 

 

任何可以用递归实现的算法都可以用迭代实现:

 

//javascript的合并排序算法
function merge(left, right){
var result = [];
while (left.length > 0 && right.length > 0){
if (left[0] < right[0]){
result.push(left.shift());
} else {
result.push(right.shift());
}
}
return result.concat(left).concat(right);
}
function mergeSort(items){
if (items.length == 1) {
return items;
}
var middle = Math.floor(items.length / 2),
left = items.slice(0, middle),
right = items.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}

//uses the same mergeSort() function from previous example
function mergeSort(items){
if (items.length == 1) {
return items;
}
var work = [];
for (var i=0, len=items.length; i < len; i++){
work.push([items[i]]);
}
work.push([]); //in case of odd number of items
for (var lim=len; lim > 1; lim = (lim+1)/2){
for (var j=0,k=0; k < lim; j++, k+=2){
work[j] = merge(work[k], work[k+1]);
}
work[j] = []; //in case of odd number of items
}
return work[0];
}
虽然迭代版本的合并排序可能比递归版本的慢一些,但它不会像递归版本那样影响调用栈。将递归算法切换为迭代只是避免栈溢出错误的方法之一。

 

 

制表:

制表,通过缓存先前计算结果为后续计算所重复使用,避免了重复工作。这使得制表成为递归算法中有用的技术。

//slow
function factorial(n){
if (n == 0){
return 1;
} else {
return n * factorial(n-1);
}
}
var fact6 = factorial(6);
var fact5 = factorial(5);
var fact4 = factorial(4);

//制表
function memfactorial(n){
if (!memfactorial.cache){
memfactorial.cache = {
"0": 1,
"1": 1
};
}
if (!memfactorial.cache.hasOwnProperty(n)){
memfactorial.cache[n] = n * memfactorial (n-1);
}
return memfactorial.cache[n];
}
var fact6 = memfactorial(6);
var fact5 = memfactorial(5);
var fact4 = memfactorial(4);

 制表过程因每种递归函数而略有不同,但总体上具有相同的模式。为了使一个函数的制表过程更加容易,

你可以定义一个memoize()函数封装基本功能。例如:

function memoize(fundamental, cache){
cache = cache || {};
var shell = function(arg){
if (!cache.hasOwnProperty(arg)){
cache[arg] = fundamental(arg);
}
return cache[arg];
};
return shell;
}
//memoize the factorial function
var memfactorial = memoize(factorial, { "0": 1, "1": 1 });
//call the new function
var fact6 = memfactorial(6);
var fact5 = memfactorial(5);
var fact4 = memfactorial(4);

 

分享到:
评论

相关推荐

    JavaScript遗传算法之迷宫寻路

    JavaScript遗传算法之迷宫寻路是一种利用人工智能技术解决复杂问题的方法。遗传算法是模拟生物进化过程的一种优化技术,常用于解决最优化问题,如路径规划、组合优化等。在这个例子中,我们用JavaScript来实现这一...

    基于javascript实现的一些常用算法

    这个名为"基于javascript实现的一些常用算法"的资源集合,很可能包含了一系列用JavaScript编写的经典算法实现,这对于学习和理解算法有着极大的帮助。让我们深入探讨一下这些算法及其在JavaScript中的实现。 1. **...

    Javascript银行家算法

    **JavaScript银行家算法详解** 银行家算法是一种避免死锁的预防策略,由艾兹格·迪杰斯特拉在1965年提出,主要用于操作系统中资源分配的安全性检查。在这个JavaScript实现中,我们可以动态地调整资源数和进程数,...

    JavaScript布局算法_JavaScript_下载.zip

    7. **性能优化**:JavaScript布局算法应考虑到性能问题,避免不必要的重绘和回流。通过使用requestAnimationFrame或者监听MutationObserver来优雅地处理布局更新,可以显著提升用户体验。 8. **模块化布局**:在...

    JavaScript前端算法.zip

    本压缩包包含了一系列与JavaScript算法相关的学习资料和代码示例,主要涉及了数据结构如链表、树,以及排序算法等主题。 1. **链表**:在"2链表.js"中,你可以找到关于链表操作的实现,如插入、删除、遍历等。链表...

    javascript版 A*寻路算法实例

    总结,这个"javascript版 A*寻路算法实例"是一个优秀的学习资源,它涵盖了路径规划、启发式搜索、数据结构和算法优化等多个重要主题,对于提升JavaScript开发者在游戏开发、图形编程等领域的技能非常有帮助。...

    javascript算法训练营

    JavaScript算法训练营是一个专注于提升JavaScript开发者算法能力的学习资源。在这个训练营中,参与者将深入学习和实践各种算法,从而提高编程技巧,理解数据结构,并掌握解决复杂问题的方法。JavaScript作为前端开发...

    CarSimulator使用JavaScript实现基于模糊控制遗传算法和粒子群优化的模拟车

    总的来说,CarSimulator项目展示了JavaScript在高级计算和模拟领域的潜力,模糊控制、遗传算法和粒子群优化的结合为车辆模拟提供了更真实和智能的解决方案。这个项目不仅对游戏开发和仿真技术有启示,也为教育和研究...

    基于JavaScript的旅行路径规划算法设计与实现

    本项目聚焦于如何利用JavaScript设计和实现一个旅行路径规划算法,以帮助用户高效地规划他们的出行路线。 首先,我们需要理解路径规划的基本概念。路径规划算法通常涉及图论中的最短路径问题,如Dijkstra算法或A*...

    算法JavaScript实现

    在IT领域,算法是解决问题和优化程序的核心工具。在这个名为"算法JavaScript实现"的主题中,我们将深入探讨如何使用JavaScript这一广泛应用于Web开发的脚本语言来实现几种关键的算法。这些算法包括大根堆、Canvas...

    JavaScript实现磁盘调度算法

    在计算机系统中,磁盘调度算法是用于管理硬盘读写操作的一种策略,其目标是优化I/O性能,减少磁头移动时间,从而提高系统效率。本文将深入探讨如何使用JavaScript来实现几种常见的磁盘调度算法:先来先服务(FCFS)、...

    JavaScript_算法讨论

    以上只是JavaScript算法讨论的一些基本方面,实际上,这个主题涵盖了更多深度和广度,包括字符串处理、日期时间操作、错误处理、异步编程、性能优化等。不断学习和实践这些算法,将有助于提升JavaScript开发者的专业...

    JavaScript算法

    JavaScript算法的学习不仅仅是理解和实现这些算法,更重要的是学会如何根据实际问题选择合适的算法,并进行性能优化。在实际开发中,理解算法的工作原理能帮助我们编写出更加高效和优雅的代码。 总的来说,...

    将遗传算法应用于旅行商问题_JavaScript_html_代码_下载

    通过这个JavaScript实现的遗传算法解决旅行商问题的项目,开发者可以深入理解遗传算法的运作机制,同时也能学习到JavaScript编程和网页交互设计。这是一个很好的学习实践案例,对于提高问题解决能力和编程技巧都有...

    向量加权平均优化算法INFO-蒲公英优化算法DO-人工水母优化算法JS-蜜獾优化算法HBA-黏菌优化算法SMA【单目标优化算法】

    向量加权平均优化算法INFO-蒲公英优化算法DO-人工水母优化算法JS-蜜獾优化算法HBA-黏菌优化算法SMA【单目标优化算法】在23个测试函数上对比(Matlab代码实现) 向量加权平均优化算法INFO-蒲公英优化算法DO-人工水母...

    数据结构与算法-JavaScript描述

    数据结构与算法是计算机科学的基础,对于任何编程语言来说,理解和掌握它们都是至关重要的,JavaScript也不例外。本资源“数据结构与算法-JavaScript描述”显然是一本专注于将这些概念应用于JavaScript编程的电子书...

    javaScript AStar 寻路算法

    JavaScript中的A*(A-Star)寻路算法是一种广泛应用的路径搜索算法,特别是在游戏开发、地图导航、图形界面设计等领域。A*算法结合了Dijkstra算法的最短路径保证和贪婪最佳优先搜索的效率,通过引入启发式函数来指导...

    数据结构与算法javascript描述

    《数据结构与算法JavaScript描述》是一本深入探讨计算机科学核心概念——数据结构和算法的书籍,特别使用JavaScript作为实现语言。这本书是图灵程序设计丛书中的一部,旨在帮助读者理解并掌握如何用动态且直观的方式...

    JavaScript数据结构算法.zip

    二、JavaScript算法 1. 排序算法:包括冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序等,了解它们的工作原理和性能特点,可以帮助选择合适的排序方法。 2. 搜索算法:线性搜索、二分搜索、深度优先...

    JavaScript代码优化一例.pdf

    现在,由于机器内存资源相对充裕,算法(代码)的优化,更多地集中于运行时长上,对JavaScript代碼而言,更是如此。 三、JavaScript代码优化的重要性 JavaScript代码的优化非常重要。根据Syracuse大学的Geofrery ...

Global site tag (gtag.js) - Google Analytics