JavaScript 查找数组最大值

JavaScript 中,提供 Math.max() 函数,使用方式如下:

console.log( Math.max(3,5,8) ); // 8

其中参数以 list 形式给出,调用方式如:

Math.max([value1[, value2[, ...]]])

详细使用方式参考 MDN

那么 Math.max 的内部实现机制是怎样的呢?

Math.max 内部实现流程

首先我们来看一下 Math 对象。与其它全局对象不同的是,Math 不是一个构造器,而是是一个单例对象,按照 ES7 官方文档,Math 对象挂载在全局对象(window 或 global)的 Math 属性上,所以 Math.max() 实际上等价于 window.Math.max() (Node 环境 global.Math.max())。

查阅 ES 5 不难发现,调用 Math.max() 时基本流程如下:

1
each param of  list ==> toNumber ---> ToPrimitive  ----> Object.defaultValue --> NaN

参数列表中每个参数调用 toNumber 转为数值型, toNumber 函数中如果是 String 类型有一套转化规则,如果是 Object 先调用 ToPrimitive 方法将对象转为基本类型(non-Object)得到 primValue ,再返回 toNumber(primValue)。 primValue 则调用对象内部 defualtValue 方法得到,该方法最终规定了对象的 defualtValue 规则。

以上基本为 Math.max 的基本流程,Math.max 的容错规则如下:

  • 没有参数返回负无穷

  • 只要任意参数为 NaN 则返回 NaN

再看 max 算法

了解 max 的工作机制以后我们看 v8 源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// ECMA 262 - 15.8.2.11
function MathMax(arg1, arg2) { // length == 2
var length = %_ArgumentsLength(); // 获取参数长度
if (length == 2) {
arg1 = TO_NUMBER(arg1); // 转为数值型
arg2 = TO_NUMBER(arg2);
if (arg2 > arg1) return arg2;
if (arg1 > arg2) return arg1;
if (arg1 == arg2) {
// Make sure -0 is considered less than +0.
// +0 > -0
return (arg1 === 0 && %_IsMinusZero(arg1)) ? arg2 : arg1;
}
// All comparisons failed, one of the arguments must be NaN.
return NaN;
}
var r = -INFINITY;
// 遍历集合
for (var i = 0; i < length; i++) {
var n = %_Arguments(i);
n = TO_NUMBER(n);
// Make sure +0 is considered greater than -0.
// 出现 NaN 或者参数个数为 0 等情况
if (NUMBER_IS_NAN(n) || n > r || (r === 0 && n === 0 && %_IsMinusZero(r))) {
r = n;
}
}
return r;
}

查找算法很简单,就是遍历集合,算法复杂度为 O(n),源码中做了很多容错处理,

再看 apply

在 JavaScript 中,每个函数都是一个 Function 对象。Function 对象下有 apply、call 和 bind 等属性,很多文章都谈过 apply、call 和 bind 的作用和区别,apply、call 和 bind 都可以动态改变 this 指向。其中 apply 要求传递两个参数,第一个是 this 指向,第二个是数组,数组中的各元素最终被转成 list 集合,因此我们可以使用 apply 求数组元素最大值。如下:

1
Math.max.apply(obj, arr);

执行过程:

  • 判断 Math.max() 是否允许被调用

  • 判断 arr 是否为 null 或者 undefined,如果是以 obj 为 this 指向直接调用 Math.max()

  • 判断 arr 是否为对象(数组也是对象),如果不是抛异常

  • 遍历 arr 将其中元素以 list 集合形式作为参数传递给 Math.max()

  • 使用 obj 身份调用 Math.max(),obj 对象获得 max() 函数的功能: obj.max(arr[0],…,arr[i])

总结

动态改变函数调用者是 JavaScript 很灵活的地方,工作中应充分利用这一特点以提高工作效率。

本文标题:JavaScript 查找数组最大值

文章作者:Syncher

发布时间:2017年08月23日 - 15:08

最后更新:2018年08月14日 - 21:08

原始链接:https://0x400.com/2017-08-23-algorithm-find-max-number-in-array.html

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。