長時間かかる反復メソッド(each,map,reduce等)の実行をtimerで飛ばしながら休み休み行うUnderscore.js用mixin

underscore.interval-iterator.js

/*
 * Underscore.js plugin
 * http://documentcloud.github.com/underscore/
 */
(function(){
  var root = this;
  var console = root.console;
  var optionsTable = {};
  var setResultTable = {};
  var lib = {};
  var internal = {};

  /*
   * no operation function
   */
  function noop(){}

  /*
   * class definition utility
   */
  function extend(C,Super,methods){
    function Class(){
    }
    Class.prototype = Super.prototype;
    C.prototype = new Class();
    if( !methods ) {
      return;
    }
    var methodName;
    for (methodName in methods) {
      C.prototype[methodName] = methods[methodName];
    }
  }
  function ResultsAggregator(){}
  extend(ResultsAggregator, Object, {
    setEachResult : noop
    ,returnResult : noop
    ,iteratorCall : noop
  });

  function EachResultsAggregator(){
  }
  extend(EachResultsAggregator, ResultsAggregator, {
    returnResult : function returnResult(resultCallback) {
      console || console.info('EachResultsAggregator#returnResult(this._results)',this._results);
      (resultCallback || noop)();
    }
    ,iteratorCall : function iteratorCall(params){
      params.iterator.call(params.context, params.element, params.index, params.list, params.setResult, params.id);
    }
  });

  function MapResultsAggregator(){
    this._results = [];
  }
  extend(MapResultsAggregator, ResultsAggregator, {
    setEachResult : function setEachResult(index,result){
      this._results[index] = result;
    }
    ,returnResult : function returnResult(resultCallback){
      console || console.info('MapResultsAggregator#returnResult(this._results)',this._results);
      (resultCallback || noop)(this._results);
    }
    ,iteratorCall : function iteratorCall(params){
      params.iterator.call(params.context, params.element, params.index, params.list, params.setResult, params.id);
    }
  });

  function ReduceResultsAggregator(){
    this._memo = undefined;
  }

  extend(ReduceResultsAggregator, ResultsAggregator, {
    setEachResult : function setEachResult(index, result, element){
      if (index === 0) {
        // initialValue
        this._memo = element;
      } else {
        this._memo = result;
      }
    }
    ,returnResult : function returnResult(resultCallback){
      console || console.info('ReduceResultsAggregator#returnResult(this._memo)',this._memo);
      (resultCallback || noop)(this._memo);
    }
    ,iteratorCall :function iteratorCall(params){
      params.iterator.call(params.context, this._memo, params.element, params.setResult, params.id);
    }
  });
  function Wrapper(obj,opions){
    this._wrapped = obj;
    this._queue = [];
    this._opions = opions;
  }
  (function() {
    function Task(args,AggregatorClass){
      this._iterator = _.toArray(args)[0];
      this._class = AggregatorClass;
    }
    extend(Task, Object, {
      createFn : function createFn(params){
        var AggregatorClass = this._class;
        params.iterator = this._iterator;
        function __value_fn(result){
          intervalIterateInternal.apply(null,[result,params,new AggregatorClass()]);
        }
        return __value_fn;
      }
    });
    extend(Wrapper, Object, {
      each : function each(){
        var task = new Task(arguments,EachResultsAggregator);
        this._queue.push(task);
        return this;
      }
      ,map : function map(){
        var task = new Task(arguments,MapResultsAggregator);
        this._queue.push(task);
        return this;
      }
      ,reduce : function reduce(){
        var task = new Task(arguments,ReduceResultsAggregator);
        this._queue.push(task);
        return this;
      }
      ,value : function value(resultCallback){
        var tasks = this._queue.reverse();
        var firstTask = tasks[tasks.length - 1];
        //var chainId = _.uniqueId('chain_id_');
        var options = this._opions;
        var isTop = typeof options === 'object';
        if ( !isTop ) {
          var iteratorId = options;
          options = optionsTable[iteratorId];
          resultCallback = setResultTable[iteratorId];
        }
        tasks.unshift(resultCallback);
        _(tasks).reduce(function(fn,task){
          var isFirst = firstTask === task;
          var params = {
            isChained :true
            ,isFirst : isFirst
            ,isTop : isTop && isFirst
            //,chainId : chainId
            ,options : options
          };
          params.resultCallback = fn;
          return task.createFn(params);
        })(this._wrapped);
      }
    });
  })();

  
  lib.intervalChain = intervalChain;
  function intervalChain(obj,opions){
    return new Wrapper(obj,opions);
  }
  lib.intervalEach = intervalEach;
  function intervalEach(obj, iterator, resultCallback, options/* execTime,interval,context*/) {
    var params = {};
    var isTop = params.isTop = typeof resultCallback === 'function';
    params.iterator = iterator;
    if (isTop) {
      params.options = options || {};
      params.resultCallback = resultCallback;
    } else {
      var iteratorId = params.iteratorId = resultCallback;
      params.options = _(optionsTable[iteratorId]).clone();
      params.resultCallback = setResultTable[iteratorId];
    }
    intervalIterateInternal(obj,params,new EachResultsAggregator());
  }
  lib.intervalMap = intervalMap;
  // Topレベルの場合(obj, iterator, resultCallback, options)
  // 内側の場合(obj, iterator, iteratorId)
  function intervalMap(obj, iterator, resultCallback, options/* execTime,interval,context*/) {
    var params = {};
    var isTop = params.isTop = typeof resultCallback === 'function';
    params.iterator = iterator;
    if (isTop) {
      params.options = options || {};
      params.resultCallback = resultCallback;
    } else {
      var iteratorId = params.iteratorId = resultCallback;
      params.options = _(optionsTable[iteratorId]).clone();
      params.resultCallback = setResultTable[iteratorId];
    }
    intervalIterateInternal(obj,params,new MapResultsAggregator());
  }
  lib.intervalReduce = intervalReduce;
  function intervalReduce(obj, iterator, resultCallback, options/* execTime,interval,context*/) {
    var params = {};
    var isTop = params.isTop = typeof resultCallback === 'function';
    params.iterator = iterator;
    if (isTop) {
      params.options = options || {};
      params.resultCallback = resultCallback;
    } else {
      var iteratorId = params.iteratorId = resultCallback;
      params.options = _(optionsTable[iteratorId]).clone();
      params.resultCallback = setResultTable[iteratorId];
    }
    intervalIterateInternal(obj,params,new ReduceResultsAggregator());
  }
  function intervalIterateInternal(obj, params, resultAggregator) {
    var isTop = params.isTop;
    var iterator = params.iterator;
    var resultCallback = params.resultCallback;
    var options = params.options;

    var execTime = options.execTime || 1000;
    var interval = options.interval || 100;
    var checkAllowExec;
    if (isTop) {
      checkAllowExec = createAllowExecChecker(execTime, interval);
      options.__checkAllowExec = checkAllowExec;
    } else {
      checkAllowExec = options.__checkAllowExec;
    }
    var context = options.context;
    var length = obj.length;
    var i = 0;
    var recursiveCallNum = 0;
    function exec() {
      var element = obj[i]
          ,index = i
          ,list = obj;
      var id = _.uniqueId('iterator_id_');
      // ToDo setResultが呼ばれた時点で再帰的な呼び出しから戻ってきていると言えるのでsetResultTable[id],optionsTable[id]を削除して良い
      setResultTable[id] = setResult;
      optionsTable[id] = options;
      function setResult(result) {
        resultAggregator.setEachResult(index, result, element);
        i++;
        console && console.log('intervalMap setResult (result,index,length,count)', result, index, length, i);
        // last
        if (length === i) {
          resultAggregator.returnResult(resultCallback);
        } else {
          // If exec isn't allowed,wait by timer.
          if (!checkAllowExec()) {
            recursiveCallNum = 0;
            checkAllowExec(exec);
            return;
          }
          if (recursiveCallNum < 100) {
            recursiveCallNum++;
            exec();
          } else {
            recursiveCallNum = 0;
            _.defer(exec);
          }
        }
      }
      // each iterator (element, index, list)
      // map iterator (element, index, list)
      // reduce iterator (memo, element)
      resultAggregator.iteratorCall({
        iterator:iterator
        ,context:context
        ,element:element
        ,index:index
        ,list:list
        ,setResult:setResult
        ,id:id
      });
    }
    exec();
  }
  /*
   * checkAllowExec関数を返す関数
   * checkAllowExec関数は今処理を実行して
   * いいならtrueを、ダメならfalseを返す
   * 関数を渡した場合、実行していいなら即実行、ダメなら実行していい時間になったら実行されるようにtimerで投げる
   * 処理を実行していい時間、ダメな時間はそれぞれexecTime,intervalTime ミリ秒交互
   */
  function createAllowExecChecker(execTime,intervalTime) {
    var id =_.uniqueId();
    var supportNow = !!Date.now;
    var startTime = supportNow ? Date.now() : new Date - 0;
    function checkAllowExec(fn){
      var timeDelta = (supportNow ? Date.now() : new Date - 0) - startTime;
      var alowExec = (timeDelta % (execTime + intervalTime)) < execTime;
      console && console.log('intervalMap checkAllowExec (id,execTime,intervalTime,timeDelta,alowExec)'
          ,id,execTime,intervalTime,timeDelta,alowExec);

      if (!!fn) {
        if (alowExec) {
          fn();
        } else {
          _.delay(fn,(execTime + intervalTime) - (timeDelta % (execTime + intervalTime)));
        }
        return;
      }
      return alowExec;
    }
    return checkAllowExec;
  }
  _.mixin(lib);
})();
// }).call({}); // no console

z.1.demo-interval.js

function format(time){
  return [time.getMinutes(),time.getSeconds(),time.getMilliseconds()].join(':');
}
function __wait(num) {
  _.range(num).map(function ___wait() {
  });
}
var array = _.range(500);
_(array).intervalEach(
    function __iterator(n,i,list,setResult){
      __wait(10000);
      setResult(n * 2);
    }
    ,function(results){
      console.info('complete');
    }
    ,{
      execTime : 300
      ,interval : 1000
    }
    );
_(array).intervalMap(
    function __iterator(n,i,list,setResult){
      __wait(10000);
      setResult(n * 2);
    }
    ,function(results){
      console.info(results);
    }
    ,{
      execTime : 300
      ,interval : 1000
    }
    );
_(array).intervalReduce(
    function __iterator(memo,n,setResult){
      __wait(10000);
      setResult(memo+n);
    }
    ,function(result){
      console.info(result);
    }
    ,{
      execTime : 300
      ,interval : 1000
    }
    );

z.2.demo-interval-chained.js

function format(time){
  return [time.getMinutes(),time.getSeconds(),time.getMilliseconds()].join(':');
}
function __wait(num) {
  _.range(num).map(function ___wait() {
  });
}
var array = _.range(500);
_(array).intervalChain({
      execTime : 300
      ,interval : 1000
    }).map(function __iterator1(n,i,list,setResult){
      __wait(10000);
      setResult(n * 2);
    }).map(function __iterator2(n,i,list,setResult){
      __wait(10000);
      setResult(n * 2);
    }).reduce(function __iterator3(memo,n,setResult){
      __wait(10000);
      setResult(memo + n);
    }).value(function(results){
      console.info(results);
    });

_(array).intervalChain({
      execTime : 300
      ,interval : 1000
    }).map(function __iterator1(n,i,list,setResult){
      __wait(10000);
      setResult(n * 2);
    }).each(function __iterator2(n,i,list,setResult){
      __wait(10000);
      setResult(n * 2);
    }).value(function(results){
      console.info('complete');
    });

z.3.demo-interval-nested.js

function __wait(num) {
  _.range(num).map(function ___wait() {
  });
}
var nestedArray = _(_.range(5)).map(function(n){
  return _(_.range(200)).map(function(n2){
    return n*200+n2;
  });
});
function format(time){
  return [time.getMinutes(),time.getSeconds(),time.getMilliseconds()].join(':');
}
// ネストしたintervalMapを使えるようにはした
_(nestedArray).intervalMap(
    function __outer_iterator(n,i,list,setResult,iteratorId){
      _(n).intervalMap(function __inner_iterator(n,i,list,setResult,iteratorId){
        __wait(10000);
        setResult(n*2);
      }
      ,iteratorId);
    }
    ,function(results){
      console.info(results);
    }
    ,{
      execTime : 300
      ,interval : 1000
    }
    );

z.4.demo-interval-chained-and-nested.js

function __wait(num) {
  _.range(num).map(function ___wait() {
  });
}
var nestedArray = _(_.range(5)).map(function(n){
  return _(_.range(200)).map(function(n2){
    return n*200+n2;
  });
});
function format(time){
  return [time.getMinutes(),time.getSeconds(),time.getMilliseconds()].join(':');
}
// nestした中でchainするのに対応
_(nestedArray).intervalMap(
    function __outer_iterator(n,i,list,setResult,iteratorId){
      _(n).intervalChain(iteratorId)
          .map(function __iterator1(n,i,list,setResult){
            __wait(10000);
            setResult(n * 2);
          }).map(function __iterator2(n,i,list,setResult){
            __wait(10000);
            setResult(n * 2);
          }).value();
    }
    ,function(results){
      console.info(results);
    }
    ,{
      execTime : 300
      ,interval : 1000
    }
    );

z.a.benchmark-interval-.js

function format(time){
  return [time.getMinutes(),time.getSeconds(),time.getMilliseconds()].join(':');
}
var array = _.range(5000);
// 179ms/5000
_(array).intervalMap(
    function __iterator(n,i,list,setResult){
      var start = (new Date);
      // wait
      // 635ms/814ms
      (function __wait() {
        _.range(100).map(function ___wait() {
        });
      })();
      var end = (new Date);
      // console.debug(n, end - start, format(start), format(end));
      setResult(n * 2);
    }
    ,function(results){
      console.info(results);
    }
    ,{
      execTime : 300
      ,interval : 1000
    }
    );

z.a.benchmark-normal-map.js

function format(time){
  return [time.getMinutes(),time.getSeconds(),time.getMilliseconds()].join(':');
}
var array = _.range(5000);
// 29ms/5000
_(array).map(
    function __iterator(n,i,list,setResult){
      var start = (new Date);
      // wait
      // 616ms/645ms
      (function __wait() {
        _.range(100).map(function ___wait() {
        });
      })();
      var end = (new Date);
      // console.debug(n, end - start, format(start), format(end));
      return n * 2;
    });

chain対応について考えていなかった

intervalChain(),intervalValue()メソッドをつくろう

nestとchainの組み合わせに対応

intervalEachを実装した。課題はeachの中断等。

何であるか
→長時間かかる反復メソッド(each,map,reduce等)の実行をtimerで飛ばしながら休み休み行うUnderscore.js用mixin

_.each,map,reduceとAPI的に変えざるをえない所
→どう休み休み実行するか(連続実行時間、休む時間)をoptionsとして渡す必要がある
→全件分の実行が完了するまでに休みが入る可能性があるので非同期処理になる可能性がある。つまり結果をreturnできないので、結果を渡すcallbackが必要になる。

二つのAPI
・_に生やしたメソッドintervalEach,intervalMap,intervalReduce。
_(array).intervalEachなどして使える。
options,resultCallbackを各interval* メソッドの引数として渡さないといけないので、引数が多くなって分かりにくい。

使用例：z.1.demo-interval.js等

・_.intervalChainメソッドによるメソッドチェーン版
_(array)
.intervalChain(options)
.map(iteratorFn)
.reduce(iteratorFn)
.value(resultCallback);
以上のように使う。
optionsはintervalChainメソッドの引数、resultCallbackはvalueメソッドの引数になっているため、各反復メソッドの引数は繰り返し実行する対象の関数のみ
反復メソッドの所属自体は_ではないので、_に生えている通常の反復メソッドと同じメソッド名になっている
反復メソッドをチェーンさせるつもりがなくても最低限intervalChain,valueで挟むためメソッドチェーンを書く必要がある

使用例：z.2.demo-interval-chained.js等

この2系統APIのうち、_の各interval* メソッドを廃止して、メソッドチェーン版のみ残そうかと思っているのですが、
JavaScripterの皆様にご意見を伺いたいところ

jquery deferredなどをつかえばsetResultとかを消せるかなーとか思ったので一から書いてみました.

https://gist.github.com/844020

ご期待に添えればなのですが...