UDN-企业互联网技术人气社区

板块导航

浏览  : 781
回复  : 2

[面试技巧] 别人家的面试题:不可变数组快速范围求和

[复制链接]
哥屋恩的头像 楼主
发表于 2016-6-1 20:19:02 | 显示全部楼层 |阅读模式
  是一道翻译小组的同学问我的题目,这道题很有意思,在 leetcode 上标记的难度为 Easy, 然而正确率出奇地低,只有不到 25%,看来这是一道看似简单实际上颇有挑战性的题目。

GOD_is_immutable.jpg


  不可变数组的范围求和

  给定一个整数数组 nums,计算出从第 i 个元素到第 j 个元素的和 ( i ≤ j ),包括 nums[ i ] 和 nums[ j ]。

  例子:

  
  1. const nums = Object.freeze([-2, 0, 3, -5, 2, -1]);

  2.   sumRange(0, 2) -> 1

  3.   sumRange(2, 5) -> -1

  4.   sumRange(0, 5) -> -3
复制代码


  注意:

  假定数组的值不会改变(如上面代码,nums 因为 Object.freeze 的缘故可读不可写)

  sumRange 可能会被使用很多次,求不同范围的值

  数组可能规模很大(比如超过 10000 个数),注意运行时间

  解题思路

  这道题看起来十分简单对吧,简单写一个函数应该谁都会:

  简单实现

  
  1. function sumRange(i, j){

  2.   var sum = 0;

  3.   for(; i <= j; i++){

  4.   sum += nums;

  5.   }

  6.   return sum;

  7.   }
复制代码


  不过呢,这么写,对照上面的注意事项,尤其是后两条:

  sumRange 可能会被使用很多次

  数组的规模可能会很大

  如果考虑这两条,那么上面的方法可以说是十分慢的,这也是为什么很多人在 leetcode 提交代码通不过,因为简单这么算的话,跑 leetcode 的大数组 case 肯定超时。

  那么,我们要怎么做才能更快呢?注意到前面说的这是不可变数组了吧?也就是说数组初始化完成之后,它的值不会改变,因此我们可以对它进行拷贝,同时“重新编码”。

  具体怎么做,大家心里是不是已经隐隐有答案了?让我们思考30秒钟然后继续 ——

  重构数组

  我们可以重新创建一个数组类,用新的数组来计算 sumRange:

  重构数组

 
  1.  const Immutable = Sup => class extends Sup {

  2.   constructor(...args){

  3.   super(...args);

  4.   Object.freeze(this);

  5.   }

  6.   }

  7.   class NumArray extends Immutable(Array){

  8.   sumRange(i, j){

  9.   let sum = 0;

  10.   for(; i <= j; i++){

  11.   sum += this;

  12.   }

  13.   return sum;

  14.   }

  15.   }
复制代码


  上面的代码里面我们重构了数组,这里我用了一点点小技巧来让数组元素不可变,这个技巧在我之前的一篇译文“六个漂亮的 ES6 技巧”中被提到,很多同学不理解那篇文章的第6个技巧,在这里我使用了一下,当然这无关我们今天讨论的主题。

  于是我们可以用新的数组对象来计算 sumRange:

  
  1. var nums = new NumArray(-2, 0, 3, -5, 2, -1);

  2.   nums.sumRange(0, 2) -> 1

  3.   nums.sumRange(2, 5) -> -1

  4.   nums.sumRange(0, 5) -> -3
复制代码


  到这里为止,我们似乎并没有改变什么,我们只是继承了 Array 类,把 sumRange 改成了对象的方法而已,它还是一样很慢。

  那接下来我们要怎么做呢?

  因为前面说过了,sumRange 要被调用很多次,所以我们要尽可能减少 sumRange 调用的复杂度对吗?按照前面的方式,我们用一个循环来对从 i 到 j 进行求和,有没有更快的方法?答案是:空间换时间,查表!

  查表

  查表不是查水表,因为 sumRange 要计算很多次,所以我们可以事先在 NumArray 构造的时候将 sumRange 需要查的值算好存入一个表中。

  二维表?
R/C012345
0
-2
-2
1
-4
-2
-3
1

0
3
-2
0
-1
2

3
-2
0
-1
3


-5
-3
-4
4


2
1
5



-1

  二维表可以将每一对 i, j 完全映射一个值,这样的话,空间复杂度变成了 O( n2 ),记得我们前面说了,这个数组可能会很大,有 10000 个元素,如果用这样的映射表,内存就溢出了。实际上,使用二维表是愚蠢的,因为我们可以很容易找到以下对应关系:

  sumRange(i, j) === sumRange(0, j) - sumRange(0, i - 1); //(i > 0)

  一维表

  我们只需要将 NumArray 的每一个元素对应从第 1 元素开始求和,将结果保存成一个一维表,我们就可以用 O( 1 ) 时间复杂度来计算 sumRange( i, j ) !

  以下是经过优化之后的 NumArray:

  使用一维表

  
  1. const UniqueID = Sup => class extends Sup {

  2.   constructor(...args){

  3.   super(...args);

  4.   Object.defineProperty(this, "id", {

  5.   value: Symbol(),

  6.   writable: false,

  7.   enumerable: false

  8.   });

  9.   }

  10.   }

  11.   const Immutable = Sup => class extends Sup {

  12.   constructor(...args){

  13.   super(...args);

  14.   Object.freeze(this);

  15.   }

  16.   }

  17.   const NumArray = (function(){

  18.   let sumTable = {};

  19.   return class extends Immutable(UniqueID(Array)){

  20.   constructor(...args){

  21.   super(...args);

  22.   let sum = 0;

  23.   let table = [0];

  24.   for(let i = 0; i < this.length; i++){

  25.   sum += this[i];

  26.   table.push(sum);

  27.   }

  28.   sumTable[this.id] = table;

  29.   }

  30.   sumRange(i, j){

  31.   let table = sumTable[this.id];

  32.   return table[j + 1] - table[i];

  33.   }

  34.   }

  35.   })();
复制代码


  上面的代码里,我们在构造 NumArray 的时候同时创建了一个私有属性 sumTable,它的第 1 个元素是 0,第 i + 1 个元素等于 sumRange(0, i),因此我们就可以快速通过:

  
  1. sumRange(i, j){

  2.   let table = sumTable[this.id];

  3.   return table[j + 1] - table[i];

  4.   }
复制代码


  来计算出 sumRange(i, j) 的值了。

  进一步优化

  上面的代码通过查表大大加快了 sumRange 的执行速度,由于数组 NumArray 是不可变的,因此我们在它被构造的时候创建好 sumTable,那么 sumRange 就完全只需要查表加上一次减法运算就可以完成了。这么做提升了 sumRange 的性能,代价是构造 NumArray 对象的时候带来额外的建表开销。

  不过,我们可以不在构造对象的时候建表,而在对象的 sumRange 方法第一次被使用的时候建表。这样的话,我们就将性能开销延从构造对象时迟到了第一次使用 sumRange 时,如果恰巧某种原因,NumArray 对象没有被使用,那么 sumTable 就永远也不会被创建。看下面的代码:

  将创建 sumTable 的工作放在 sumRange 第一次被调用时

  
  1. const UniqueID = Sup => class extends Sup {

  2.   constructor(...args){

  3.   super(...args);

  4.   Object.defineProperty(this, "id", {

  5.   value: Symbol(),

  6.   writable: false,

  7.   enumerable: false

  8.   });

  9.   }

  10.   };

  11.   const Immutable = Sup => class extends Sup {

  12.   constructor(...args){

  13.   super(...args);

  14.   Object.freeze(this);

  15.   }

  16.   };

  17.   const NumArray = (function(){

  18.   let sumTable = {};

  19.   return class extends Immutable(UniqueID(Array)){

  20.   sumRange(i, j){

  21.   if(!sumTable[this.id]){

  22.   let table = [0], sum = 0;

  23.   for(let i = 0; i < this.length; i++){

  24.   sum += this[i];

  25.   table.push(sum);

  26.   }

  27.   sumTable[this.id] = table;

  28.   }

  29.   let table = sumTable[this.id];

  30.   return table[j + 1] - table[i];

  31.   }

  32.   }

  33.   })();
复制代码

  以上是今天我们讨论的内容。上面的代码其实还可以优化,因为我们将建表的工作推迟到 sumRange 第一次被调用时执行,这很好,但这给 sumRange 带来了一次 if 判断操作的额外开销,实际上我们应该也有办法消除这个开销,我把这个问题留给大家吧,欢迎大家讨论。

原文作者:十年踪迹 来源:开发者头条
发表于 2016-6-1 22:52:32 | 显示全部楼层
赞一个
使用道具 举报

回复

发表于 2016-6-1 23:57:59 | 显示全部楼层
赞一个
使用道具 举报

回复

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

关于我们
联系我们
  • 电话:010-86393388
  • 邮件:udn@yonyou.com
  • 地址:北京市海淀区北清路68号
移动客户端下载
关注我们
  • 微信公众号:yonyouudn
  • 扫描右侧二维码关注我们
  • 专注企业互联网的技术社区
版权所有:用友网络科技股份有限公司82041 京ICP备05007539号-11 京公网网备安1101080209224 Powered by Discuz!
快速回复 返回列表 返回顶部