05月31, 2016

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

这是一道翻译小组的同学问我的题目,这道题很有意思,在 leetcode 上标记的难度为 Easy, 然而正确率出奇地低,只有不到 25%,看来这是一道看似简单实际上颇有挑战性的题目。

不可变数组的范围求和

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

例子:

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

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

注意:

  1. 假定数组的值不会改变(如上面代码,nums 因为 Object.freeze 的缘故可读不可写)
  2. sumRange 可能会被使用很多次,求不同范围的值
  3. 数组可能规模很大(比如超过 10000 个数),注意运行时间

解题思路

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

简单实现

function sumRange(i, j){
  var sum = 0;
  for(; i <= j; i++){
    sum += nums[i];
  }
  return sum;
}

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

  • sumRange 可能会被使用很多次
  • 数组的规模可能会很大

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

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

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


重构数组

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

重构数组

const Immutable = Sup => class extends Sup {
  constructor(...args){
    super(...args);
    Object.freeze(this);
  }
}

class NumArray extends Immutable(Array){
  sumRange(i, j){
    let sum = 0;
    for(; i <= j; i++){
      sum += this[i];
    }
    return sum;    
  }
}

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

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

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

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

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

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

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

查表

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

二维表?

R/C 012345
0-2-21-4 -2-3
103-2 0-1
23-2 0-1
3-5 -3-4
4 21
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:

使用一维表

const UniqueID = Sup => class extends Sup {
  constructor(...args){
      super(...args);
      Object.defineProperty(this, "id", {
        value: Symbol(),
        writable: false,
        enumerable: false
      });
    }
}

const Immutable = Sup => class extends Sup {
  constructor(...args){
    super(...args);
    Object.freeze(this);
  }
}

const NumArray = (function(){
  let sumTable = {};
  return class  extends Immutable(UniqueID(Array)){
    constructor(...args){
      super(...args);
      let sum = 0;
      let table = [0];

      for(let i = 0; i < this.length; i++){
        sum += this[i];
        table.push(sum);
      }
      sumTable[this.id] = table;
    }
    sumRange(i, j){
      let table = sumTable[this.id];
      return table[j + 1] - table[i];   
    }
  }
})();

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

sumRange(i, j){
  let table = sumTable[this.id];
  return table[j + 1] - table[i];   
}

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

进一步优化

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

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

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

const UniqueID = Sup => class extends Sup {
  constructor(...args){
    super(...args);
    Object.defineProperty(this, "id", {
      value: Symbol(),
      writable: false,
      enumerable: false
    });
  }
};

const Immutable = Sup => class extends Sup {
  constructor(...args){
    super(...args);
    Object.freeze(this);
  }
};

const NumArray = (function(){
  let sumTable = {};
  return class  extends Immutable(UniqueID(Array)){
    sumRange(i, j){
      if(!sumTable[this.id]){
        let table = [0], sum = 0;
        for(let i = 0; i < this.length; i++){
          sum += this[i];
          table.push(sum);
        }
        sumTable[this.id] = table;
      }
      let table = sumTable[this.id];
      return table[j + 1] - table[i];
    }
  }
})();

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

对于这道题,如果你有自己的解法,欢迎讨论。

本文链接:https://www.h5jun.com/post/range-sum-query-immutable.html

-- EOF --

Comments