Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

JS-Array #100

Open
yaofly2012 opened this issue Feb 11, 2020 · 3 comments
Open

JS-Array #100

yaofly2012 opened this issue Feb 11, 2020 · 3 comments

Comments

@yaofly2012
Copy link
Owner

yaofly2012 commented Feb 11, 2020

一、JS没有“真正的数组”

像C++,Java这些编程语言中数组元素分配的内存都是连续,这有利于性能提升,但是JS的数组不是这样的。它使用对象模拟数组,即对象属性为数字,并含有length属性。所以JS数组对象的内存不是连续的,同一般对象内存分配。

二、创建数组

2.1 字面量方式

var a = [], // 定义空数组
    b = [1,true], // 数组元素用逗号隔开
    c = [1,,3, void 0], // 忽略中间的元素
    d = [1,2,]; // 末尾是逗号
  1. 数组元素类型可以各不相同(因为JS数组本质是个对象);
  2. c[1]元素是未定义的,跟值是undefined的元素是不同的;
1 in c // false
3 in c // true
  1. 数组d的长度是2,不是3,因为字面量准许末尾是逗号。
d.length // 2

2.2 使用构造函数Array

var a = new Array(), // 等价 []
    b = new Array(2), // 等价 [,,], 注意这里是两个逗号哦
    c = new Array(1,2), // 等价 [1, 2]
    d = Array(1,2); // 等价于new Array(1,2)
  1. 使用构造函数Array比较坑,不同数量的实参会导致Array函数的行为不一致。
  2. Array即是构造函数也是工厂函数。即new Array() 等价于直接调用Array();

三、索引和属性名称

  1. 索引即为数组元素的下标,访问对象的属性是通过属性名称,而访问数组的元素则是通过索引。
  2. 索引是32位的正整数,有效取值范围是[0, 2^32 - 1](因为数组的length属性也是32位整数,所有下标最大为2^32-1),不在这个范围的值都不是索引。
  3. 虽然JS没有整数类型,但索引的操作都是按照32位正整数方式处理的
  4. 数组本质也是对象,也是可以通过属性名称的方式访问数组的属性。
var a = [1,2],
    b = {
        0: 1,
        1: 2
    };

console.log(a[1]); // 索引访问方式
console.log(a['1']); // 索引访问方式,会把'1'转成正整数1
console.log(b[1]); // 属性名称访问方式,会把1转成字符串“1”

注意:

  1. 索引是一种特殊的属性名称;
  2. 属性名称方式会把中括号里的表达式转成字符串,索引方式会把中括号里的表达式转成32整数,如果不是合法的索引,则视为属性名称,所以JS数组不存在下标越界的问题

3.2 稀疏数组

JS数组元素不一定是连续的,索引位置上没有元素(没有元素取值是undefined的元素是不同的)的数组叫稀疏数组。

var a = [,], // 定义即为稀疏数组
    b = Array(3), // 定义即为稀疏数组
    c = [1,2,3];
delete c[1]; // delete操作造成稀疏

注意:

  1. 再强调索引位置上没有元素跟取值是undefined的元素不一样的(有些数组的方法, 运算符的行为不一样)。
for(var a in [,]) {console.log(1)} // 没有循环
for(var a in [1,void 0]) {console.log(1)} // 循环2次

四、length属性

4.1 length属性

  1. length属性表示“数组元素的数量”,JS的数组元素并不是连续的,有些索引的位置可能没有元素,所以length属性并不能真正表示元素的数量,其值等于数组最大索引+1
  2. 并且length属性是可写的
var arr = [1];
arr.length; // 1
arr.length = 3; // 增大length属性值
arr.length;// 3, 索引1,2位置是未定义的元素。
arr.length = 0; // 减小length属性值
arr[0]; //undefined

可以利用修改length修改进行删除元素(甚至清空数组)

var a = [1, 2, 3];
a.length = 1; // 等价a.splice(1)
console.log(a); // [1]

4.2 伪数组

广义上只要含有length属性且length值是在索引有效取值范围内(或可以通过类型转换成有效索引)的对象都可以视为伪数组。伪数组可以应用数组的一些方法:

var a = {length: 2}; // a是伪数组
Array.prototype.slice.call({length: 2}); // 可以应用slice方法,其结果等价于Array(2)的结果

五、JavaScript 数组 —— 演进&性能

现代浏览器已经针对相同类型的数组进行了优化。

参考

  1. MDN Array
  2. MDN Array.prototype
@yaofly2012 yaofly2012 added the JS label Feb 11, 2020
@yaofly2012
Copy link
Owner Author

yaofly2012 commented Feb 11, 2020

方法

ES3/5/next都提供了不少方法,每个阶段提供的方法都有当时的时代性和局限性

  • ES3:主要是操作元素相关的方法
  • ES5:主要是遍历和基于遍历的搜索、诊断相关的方法
  • ES6:主要是添加了新的功能,让数组使用的更加方便

ES3

主要是操作元素相关的方法

1. push(element1[, ...[, elementN]])]/pop

  1. push方法还可以用在对象上。
var a = {}
Array.prototype.push.call(a, 'hello','world')
console.log(a); // {0: "hello", 1: "world", length: 2}
  • The push method relies on a length property to determine where to start inserting the given values
var a = { length: '2'}
Array.prototype.push.call(a, 'hello','world')
console.log(a); // {2: "hello", 3: "world", length: 4}
  • If the length property cannot be converted into a number, the index used is 0.
var a = { length: 'test'}
Array.prototype.push.call(a, 'hello','world')
console.log(a); // {0: "hello", 1: "world", length: 2}
  • This includes the possibility of length being nonexistent, in which case length will also be created
var a = {}
Array.prototype.push.call(a, 'hello','world')
console.log(a); // {0: "hello", 1: "world", length: 2}
  • 唯一的条件是对象的length属性(如果有)必须是可写的,如字符串就不可以使用push方法,因为字符串的length属性是只读的。
// Uncaught TypeError: Cannot assign to read only property 'length' of object '[object String]'
Array.prototype.push.call('hello', 'world')
  1. pop方法也可以用在对象上。
  • pop方法也依赖length属性,决定剔除的属性
var a = { length: '2', 1: 'hello', 2: 'world' }
var b = Array.prototype.pop.call(a, 'hello','world');
console.log(b); // 'hello'
console.log(a); // {2: "world", length: 1}
  • If the length property cannot be converted into a number, the index used is 0.
var a = { length: 'test', 1: 'hello', 2: 'world' }
var b = Array.prototype.pop.call(a, 'hello','world');
console.log(b); // undefined
console.log(a); // {1: "hello", 2: "world", length: 0 }
  • This includes the possibility of length being nonexistent, in which case length will also be created
var a = { 1: 'hello', 2: 'world' }
var b = Array.prototype.pop.call(a, 'hello','world');
console.log(b); // undefined
console.log(a); // {1: "hello", 2: "world", length: 0 }
  • 唯一的条件是对象的length属性(如果有)必须是可写的,如字符串就不可以使用pop方法,因为字符串的length属性是只读的。
// Uncaught TypeError: Cannot assign to read only property 'length' of object '[object String]'
Array.prototype.push.call('hello')

2. unshift(element1[, ...[, elementN]])/shift

  1. push/pop类似,unshift/shift也可以应用在对象上,不一样的地方是unshift/shift会影响到其他索引属性名称。
    因为从头部开始的。
var a = {1: 'name', length: '2'};
var b = Array.prototype.shift.call(a)
console.log(b) // undefined
console.log(a) // {0: "name", length: 1} 不仅length属性变化了,原来`属性1`变成`属性0`了
  1. 之前一直混淆unshiftshift的功能。可以借助push/pop记忆unshift/shiftpush名字比pop长,
    unshift名字也比shift长),即pushunshift功能相似,并且名字都比对应功能的方法pop/shift名字长。长对长,短对短,估计再也不会混淆unshiftshift方法的功能了。

3. join([separator])

  1. join方法会把值为undefined/null的元素转成空字符串。
    最近看到某个框架源码有这么个片段:
var indent = '';
for (i = 0; i < space; i += 1) {
    indent += ' ';
  }

大概意思就是根据参数space生成指定长度的空格字符串。可以通过join方法改进下:

 var indent = Array(space + 1).join(' '); // 记得+1,否则字符串长度少1
  1. 内部依赖length属性,并且它也可以应用到对象上。
Array.prototype.join.call({length: '2', 1: 'a'}, ',') // “,a”

4. reverse

  1. 会影响源数组
  2. reverse内部依赖length属性,并且它也可以应用到对象上。
var a = {1: 'name', length: '2'};
Array.prototype.reverse.call(a)
console.log(a); // {0: "name", length: "2"} 
  1. reverse应用到对象上时,它并不修改对象的length属性。

5. sort([compareFunction])

  1. 会影响源数组;
  2. 缺省实参(默认行为)行为会把非undefined的元素转成字符串,基于UTF-16码表的顺序升序排列;
var a = [1,2,12,32, null, undefined, 34, 'z'].sort()
// [1, 12, 2, 32, 34, null, "z", undefined]
console.log(a)
  • undefined元素在最后;
  • undefined元素转成字符串,按照UTF-16 code units值升序排列。
  1. sort方法也可以应用对象上。

6. concat

  1. 一直以为该方法用于多个数组合并,其实除了的功能外还可以把非数组类型的参数插入返回值数组里(所以都到ESNext了该方法依旧不能支持伪数组)。
var a = [1, 2];
a.concat([3, 4]) // [1, 2, 3, 4]
a.concat(3, 4) //  [1, 2, 3, 4]
a.concat({length: 2}) // [1, 2, {length: 2}]
  1. 不会影响源数组,会返回一个新数组;
  2. concat也可以应用到对象上,但行为有点出乎意料
var a = {1: 'name', length: '2'};
Array.prototype.concat.call(a, 10, 20) // [{1: 'name', length: '2'}, 10, 20]

相当于:[].concat(a, 10, 20)

7. slice([begin[, end]])

  1. 获取区间[begin, end)的元素,其中beginend表示的是下标位置,但可以为负数,表示从尾部开始数;
[1,2,3].slice(-2) // [2, 3] 等价于[1,2,3].slice(-2 + 3), 即[1,2,3].slice(1)
[1,2,3].slice(2,-5) // [] 等价于[1,2,3].slice(2, -1 + 3 * 2 ), 即[1,2,3].slice(2, 1)
[1,2,3].slice(-2, -1) // [2] 等价于[1,2,3].slice(-2 + 3, -1 + 3 ), 即[1,2,3].slice(1, 2)
  1. slice也可以应用到对象上。

8. splice(start[, deleteCount[, item1[, item2[, ...]]]])

  1. splice方法可以实现对数组任意位置,任意数量的元素进行增加,删除,替换(也包含删除)操作。
var a = [1, 2, 3, 4, 5];
// 替换:将元素2,3替换成10,11
a.splice(1, 2, 10, 11)
console.log(a) // [1, 10, 11, 4, 5]

// 删除:删除10,11
a.splice(1, 2) // [1, 4, 5]

// 插入:在元素4后面插入元素22,23,24
a.splice(2, 0, 22, 23, 24)
console.log(a) // [1, 4, 22, 23, 24, 5]

start指定操作开始的位置(索引),如果发生删除,也会影响start位置的元素,即受影响范围的元素区间是:[start, start + delCount)
2. splice的返回值是被删除的元素的集合;
3. 大部分情况我们经常对数组的首尾进行添加删除操作,所以一般使用push/pop, unshift/shift方法多些;

var a = [1, 2, 3];
// 也可以用a.splice(a.length, 0 ,4)替换,但是返回值不同
a.push(4); 

// 也可以用a.splice(a.length - 1)替换,但是返回值不同
a.pop();
  1. 会影响原数组;
  2. splice也可以应用到对象上。

9. toString

  1. toString的行为等价于join(',')
console.log([1, 2, 3].toString()) // "1,2,3"
  1. 也可以用于对象,但是当用于非数组时,等价调用Object.prototype.toString()
var a = {
    1: 'name'
}

// "[object Object]",等价`a.toString()`
console.log([].toString.call(a))

总结(时代性和局限性)

  1. ES3定义的方法基本都是操作数组的方法;
  2. 并且都可以应用到对象上,估计主要是为了方便处理伪数组(尤其是arguments变量)。
var obj = {
    '2': 3,
    '3': 4,
    'length': 2,
    'slice': Array.prototype.slice,
    'splice': Array.prototype.splice,
    'push': Array.prototype.push,
    'pop': Array.prototype.pop
}

obj.push(1) // 
obj.push(2)

console.log(obj.slice()) // [,,1,2]
var c = obj.pop(); 
console.log(c) // 2
console.log(obj) 
  1. 很难想象ES3中判断数组是否包含指定的元素居然要手动使用循环,居然没有提供内置的方法。

ES5

主要是遍历和基于遍历的搜索、诊断相关的方法,这些恰恰是ES3没有提供的

1. forEach(callback(element[, index[, array]])[, thisArg])

2. map(callback(element[, index[, array]])[, thisArg])

3. filter(callback(element[, index[, array]])[, thisArg])

4. every/some(callback(element[, index[, array]])[, thisArg]): boolean

5. reduce/reduceRight

reduce的含义"简化",可以表示输入多个参数,输出单个值。 reduce的参数函数也叫reducer函数。

  • 是否指定初始值循环的次数不一样的
  • reduce应用场景很多,认真看下MDN Demos,还有这个面试题
    改成纯Promise版:
function genTask(action, delay, context) {
    return function() {
        return new Promise(resolve => {          
             action && action.call(context);
             setTimeout(resolve, delay == null ? 0 : (delay * 1000))
        })
    }
}

function machine(name) {
    var tasks = [];
    tasks.push(genTask(function() {
        console.log(`start ${name}`)
    }))
    function execute() {
        var self = this;
        tasks.reduce((promise, task) => {
            return promise.then(task)
        }, Promise.resolve())
    }
    function _do(task) {       
        tasks.push(genTask(function() {
            console.log(`${name} ${task}`)
        }))
        return this
    }

    function wait(delay) {
        tasks.push(genTask(() => {
            console.log(`wait ${delay}s`);
        }, delay, null))
        return this
    }
    
    function waitFirst(delay) {
        tasks.unshift(genTask(() => {
            console.log(`wait ${delay}s`);
        }, delay, null))
        return this
    }

    return {
        name: name,
        execute: execute,
        do: _do,
        wait: wait,
        waitFirst: waitFirst
    }
}

machine('ygy')
.waitFirst(3)
.do('eat')
.execute();
function fetch(x) {
  return new Promise((resolve, reject) => {
      console.log(x)
    setTimeout(() => {
      resolve(x)
    }, 500 * x)
  })
}

async function test() {
    let arr = [3, 2, 1]
    await arr.reduce(async (promise, item) => { 
      await promise;
      console.log(item)
      return await fetch(item);
    }, Promise.resolve())
    console.log('end')
}
test();

6. indexOf/lastIndexOf(searchElement[, fromIndex])

采用绝对相等(===)的判断逻辑,这个跟includes不一样。

[-0, NaN].indexOf(0) // 0
[-0, NaN].indexOf(NaN) // -1
[-0, NaN].includes(NaN) // true

7. Array.isArray(obj)

总结(时代性和局限性)

  1. ES5基本都是遍历和基于遍历的方法(forEach, map, filter, every/some, reduce/reduceRights, indexOf/lastIndexOf),要根据不同的需求选用不用的遍历方法;并且都不会遍历数组中被删除或从未被赋值的元素,见稀疏数组;
  2. indexOf/lastIndexOf采用的相等性判断是严格相等===(此时JS还没引入0值相对算法);

补充

有人尝试把async函数作为上述数组具有遍历功能的回调函数,但可能得到意想不到的结果,比如这个重学 JS:为啥 await 在 forEach 中不生效。不仅仅是forEach,其他的遍历方法也都只处理同步代码。
异步函数的返回值是个Promise对象,相当于这些遍历方法实际在操作Promise对象。

ES6

主要是添加了新的功能,让数组使用的更加方便

  1. 创建方法
  2. 初始化方法
  3. 查询/检测方法

1. copyWithin

2. entries

类似对象的entries方法功能,不过是由索引和元素构成的(index-value)对迭代器(iterator)。

3. fill(value[, start[, end]])

  1. 会修改数组本身
var a = [1, 2]
var b = a.fill(3)
console.log(a === b) // true

3. find(callback(element[, index[, array]])[, thisArg])

4. findIndex(callback( element[, index[, array]] )[, thisArg])

  1. 功能类似ES5点indexOf,不过参数不同,是indexOf的加强版;
  2. 更灵活,使用回调函数可以更灵活的控制相等判断逻辑

5. includes(valueToFind[, fromIndex])

判断数组是否包含指定的元素,在此之前我们一般借助indexOf方法的返回只是否为-1判断元素是否存在:

var a = [1, 2, 4];
a.indexOf(1) !== -1 // true, 存在
a.indexOf(6) !== -1 // false, 不存在

ES6引入includes方法专门用来判断元素是否存在,并且采用的是0值相等的等值判断算法,indexOf方法采用的绝对相等(===)算法。

var a = [1, NaN];
a.includes(NaN) // true, 存在
a.indexOf(NaN) !== -1 // false, 不存在

6. keys

类似Object.keys方法,不过返回的是迭代器。

const array1 = ['a', 'b', 'c'];
const iterator = array1.keys();

console.log(typeof iterator); // object
console.log(Object.keys(array1)); // ["0", "1", "2"],数组的`length`属性不可遍历的。

7.values

类似Object.values方法,不过返回的是迭代器。

  1. Array.prototype.values返回值和数组本身是实时对应的。
const array1 = ['a', 'b', 'c'];
const iterator = array1.values();
array1.push('d') // 动态添加

for (const value of iterator) {
  console.log(value);
}
// expected output: "a"
// expected output: "b"
// expected output: "c"
// expected output: "d"
  1. Array.prototype.values方法返回值和Array.prototype[@@iterator]()返回值一样,但是不同的对象;
const array1 = ['a', 'b', 'c'];
const iterator = array1.values();
const iterator2 = array1[Symbol.iterator]();
console.log(iterator === iterator2) // false
  1. 数组本身已经是迭代器了,为啥还需要Array.prototype.values方法?

8. [Symbol.iterator]()

迭代协议和迭代器

9. [Symbol.species] ?

10. Array.of

我们都知道Array的构造函数根据的参数数量的不同具有不同的行为:

Array(7);          // 一个参数表示数组的长度:构建长度为7的数组
Array(1, 2, 3);    // 多个参数表示数组的元素:构建数组为[1, 2, 3]

Array.of方法统一了这种行为,都是用来根据元素构建数组:

Array.of(7);       // [7] 
Array.of(1, 2, 3); // [1, 2, 3]

11. Array.from(arrayLike [, mapFn(val, index) , [thisArg]])

创建数组工厂方法。
将类数组(含有length属性的对象)或则iterable对象转成数组,并顺便融合类似map的功能进行元素值转化;

// 初始化数组(跟采用`fill`方法初始化不一样的是,这样每个元素值都不一样)
var arr = Array.from(Array(10), (val, index) => index);

var arr2 = Array(10).fill()

MDN列举了其他使用场景。

@yaofly2012
Copy link
Owner Author

yaofly2012 commented Feb 11, 2020

练习

数组去重

var a = [1, 2,3,4,3,2]
// ES3
for(var i = 0,len = a.length; i !== len; ++i) {
    if(b.indexOf(a[i]) === -1) {
        b.push(a[i])
    }
}

// ES5
var b = a.reduce((result, item) => {
    if(result.indexOf(item) === -1) {
        result.push(item)
    }
    return result
}, [])

// ES6
var a = Array.from(new Set(a))

1. 利用排序减少遍历次数

var b = a.sort().reduce((result, item) => {
    if(result[result.length -1 ] !== item) {
        result.push(item)
    }
    return result
}, [])

2. 高性能数组去重

除了1,2还有其他多种方式史上最全JavaScript数组去重的十种方法(推荐)各种方法的性能PK见JavaScript 高性能数组去重

  1. 自测下来(Chrome)是Array.from(new Set(a))最快;
// case1
 Array.from(new Set(arr));

// case2
[...new Set(arr])];

优化方案总结

去重方案一般涉及双层遍历(除了ES6的方式Array.from(new Set(a))):

  1. 第一层遍历获取元素(获取元素)
  2. 第二层遍历用于诊断(判断元素是否重复)

第一层遍历避免不了(并且一次遍历性能也没问题),主要看怎么优化第二层遍历(Array自带的诊断方法基本上都是基于遍历的,实际没有优化):

  • 对象属性方式(属性名到属性地址应该有索引)
var obj = {}
function include(arr, ele) {
    if(ele in obj) {
        return true;
    }
    obj[ele] = void 0;
    return false;
}

缺点:只针对基本类型数据

  • 有序数组利用相邻值判断
    排序的目的是让相同元素相邻。
    缺点:只针对基本类型数据

按顺序运行Promise

涉及元素前后依赖的都可以借助reduce,如函数功能管道。

@yaofly2012
Copy link
Owner Author

yaofly2012 commented Feb 12, 2020

练习

1. 输出结果Daily-Interview-Question-66

[3, 15, 8, 29, 102, 22].sort()

2. 输出结果Daily-Interview-Question-76

var obj = {
    '2': 3,
    '3': 4,
    'length': 2,
    'splice': Array.prototype.splice,
    'push': Array.prototype.push
}
obj.push(1)
obj.push(2)
console.log(obj)

3. 数组里面有10万个数据,取第一个元素和第10万个元素的时间相差多少

没差别。
Array就是对象(不管元素地址是否是连续的)都是根据索引直接计算出元素地址获取的,不是通过遍历查询元素的。
课外补充:JS Array演进

4. 有以下 3 个判断数组的方法,请分别介绍它们之间的区别和优劣Object.prototype.toString.call() 、 instanceof 以及 Array.isArray()

  1. 注意的是instanceof不能跨全局环境判断。
  2. underscore是优先使用Array.isArray+Object.prototype.toString.call()兜底。
    underscore isArray
// Is a given value an array?
  // Delegates to ECMA5's native Array.isArray
  _.isArray = nativeIsArray || function(obj) {
    return toString.call(obj) === '[object Array]';
  };

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

1 participant