配列の AND、非同期な AND 検索

配列の積集合・和集合

ちょっと用があって、複数の配列の共通要素を取り出す関数を作ってみました。Mochikit を使っています。

function intersection() {
  var len = arguments.length;
  var tmp = {};
  return filter(
    function(x) {
      tmp[x] || (tmp[x] = 0);
      return (++tmp[x] == len);
    },
    chain.apply(null, arguments)
  );
}

配列のイテレーションと同時に要素の出現回数を数えていき、全ての配列で出現しているものを抜き出します (各配列内での要素の重複は考慮に入れていません)。

このように、3 つ以上の配列でも簡単に AND を取ることが出来ます:

intersection(
  [1,3,6,8,9],
  [2,4,6,8],
  [6,7,8]
);
// -> [6,8]

さらにここから、テスト部分を抽象化してみることにしました:

function set_maker(pred) {
  var tmp = {};
  return function(lst) {
    return filter(
      function(x) {
	tmp[x] || (tmp[x] = 0);
	return pred(++tmp[x]);
      },
      chain.apply(null, lst)
    );
  }
}

要素の出現回数をテスト関数に渡してやるわけです。

そうすると、intersection (積集合) は次のように書けるようになります:

function intersection() {
  return set_maker(partial(operator.eq, arguments.length))(arguments);
}

和集合はこうです:

function union() {
  return set_maker(partial(operator.eq, 1))(arguments);
}

また、「3 分の 2 以上に含まれる」など条件を色々と調節することもできますが、その場合は (union や intersection と違い)、要素に重複が生じることがあります。

非同期な積集合・和集合

実は、複数の非同期通信から上がってくる配列をうまく一つに纏めたい、という目的が先にあったんですが、アイデアが浮かばなかったので取り敢えず上記のことを考えてみた次第です。

で、「数を数える」という方法が良いヒントになり、こんな関数を思いつきました:

function deferredIntersection(count, callback) {
  var lst = [];
  return function(x) {
    lst.push(x);
    if (lst.length == count) {
      callback(intersection.apply(null, lst));
    }
  };
}

予め来るべき配列の数 (非同期処理の数) を知らせておく必要がありますが、最後の処理 (もちろんどれが最後になるかは分かりません) が完了した時点で全配列の積を得ることが出来ます。

使い方は、

var cb = deferredIntersection(3, function(ary) {
  // ここに 3 つの配列の積が返ってくる
});

このようなコールバック関数 cb を作り、全ての非同期処理にコールしてもらいます:

d1 = doSimpleXMLHttpRequest(url1);
d1.addCallback(compose(cb, parse)); // parse は配列を返す関数
// ...

あとはただ待つだけです。

折角なのでこれも一般化しておきます:

function deferredSet(count, type, callback) {
  var lst = [];
  return function(x) {
    lst.push(x);
    if (lst.length == count) {
      callback(type.apply(null, lst));
    }
  };
}
function deferredIntersection(size, callback) {
  return deferredSet(size, intersection, callback);
}
function deferredUnion(size, callback) {
  return deferredSet(size, union, callback);
}

追記 [20070311]:

ブックマーク・コメントにて、複数の Deferred を纏めるための DeferredList というものがあるよ、ということを教えていただきました。有り難うございます。すっかり忘れてました。

ということで、DeferredList を使って同じ物が実装できるかどうか調べてみたんですが、どうも発想の仕方からして全然別物のようです。

DeferredList は複数の Deferred オブジェクトを纏めるものなのに対し、deferredIntersection は Deferred オブジェクトのコールバック関数を包み込むものです。

上のサンプル・コードでは Deferred オブジェクトへのアクセスが必要であるかのような書き方をしてしまいましたが、実際には非同期関数にコールバックを渡す、という以下の様な局面:

fetch_data(url, callback);

を、Deferred オブジェクトを見ることなくマルチ化できる、というものなんです:

exhaust(
  imap(
    fetch_data,
    imap(makeQueryUrl, qlist),
    repeat(deferredIntersection(qlist.length, callback))
  )
);

ちなみに、実際の私のコードでは deferredSequence という、Deferred オブジェクトを一度に一つずつしか作らない (つまり DeferredList が使えない、ということです) 非同期タスクと共に利用しています。

deferredSequence:

function deferredSequence(dfunc, iterable, /* optional */interval) {
  var item = next(iterable);
  if (isUndefinedOrNull(item)) {
    return;
  }

  var self = arguments.callee;
  var args = arguments;
  var d = dfunc(item);
  if (!(d instanceof Deferred)) {
    d = new Deferred();
    d.callback();
  }
  d.addBoth(function() {
    wait(interval||0).addCallback(partial.apply(null, extend([self],args)));
  });
  return d;
}

(そう言えばこれ、DeferredList が気に入らなくて作ったんでした)