Redisで全文検索

台風一過で天気が良いのでnodeとRedisのSETを転置インデックスに使った全文検索を作った.
wikipediaのタイトル一覧(約100万件)をtri-gramで分解しRedisに突っ込んだ結果,約800万件の転置インデックスを挿入するのにおよそ3分,サイズは700MB程度だった.
同じようなことをmongodbでもできるが挿入速度ではRedisが有利だろう.

転置インデックス作成

const redis = require('redis');
const byline = require('byline');
const fs = require('fs');
const client = redis.createClient();

const ngram = function(str, n) {
  n = n ? n : 3;
  var grams = [];
  for(var i = 0; i <= str.length - n; i++) {
    grams.push(str.substr(i, n).toLowerCase());
  }
  return grams;
};

if(process.argv.length < 3) {
  process.stderr.write('argv error\n');
  process.exit(1);
}
var rs = fs.createReadStream(process.argv[2], { encoding: 'utf8' });
var ls = byline.createLineStream(rs)
var titles = [];
var iis = [];
var index = 0;
var ic = 0;
ls.on('data', function (data, line) {
  titles.push('key-' + index);
  titles.push(data);
  var grams = ngram(data); // Tri-gram
  for(var i = 0; i < grams.length; i++) {
     iis.push(['sadd', grams[i], index]);
  }
  index++;

  if(titles.length > 100000) {
    ls.pause();
    client.mset(titles, function(err, res) {
      ls.resume();
    });
    titles = [];
  }

  if(iis.length > 500000) {
    ic += iis.length;
    ls.pause();
    client.multi(iis).exec(function(err, res) {
      ls.resume();
    });
    iis = [];
  }
});

ls.on('end', function () {
  client.mset(titles, function(err, res) {
    client.multi(iis).exec(function(err, res) {
      ic += iis.length;
      console.log(ic);
      client.end();
    });
  });
});

検索

const redis = require('redis');
const client = redis.createClient();
const byline = require('byline');
const fs = require('fs');
const ngram = function(str, n) {
  n = n ? n : 3;
  var grams = [];
  for(var i = 0; i <= str.length - n; i++) {
    grams.push(str.substr(i, n).toLowerCase());
  }
  return grams;
};

const search = function(str, n) {
  var grams = ngram(str, n);
  var t = new Date;
  client.sinter(grams, function(err, res) {
    res = res.map(function(e) { return 'key-' + e; });
    client.mget(res, function(err, res) {
      console.log(res);
      console.log('----------------------------------------');
      console.log('' + res.length + 'results(' + (new Date - t) + 'ms)');
      client.end();
    });
  });
};

if(process.argv.length < 3) {
  process.stderr.write('argv error\n');
  process.exit(1);
}

search(process.argv[2]);

無料で公衆無線LANを使う方法(mobilepoint;iPhoneユーザー限定)

しょっちゅう忘れるのでメモ.手段的にアウトかもしれない.
ブラウザはChrome,OSはWindows7を想定.
とりあえずmobilepointに接続.WEPキーはググれ.(この時点でhttp以外の通信はできてしまうようなのでVPNつなげりゃ普通にネットできる.)
Chromeへのショートカットをデスクトップに作成.リンク先の最後に次の文字列を追加しOKを押す.(UserAgent偽装と,プロファイル新規作成.両方必須.)

 --user-agent="Mozilla/5.0 (iPhone; U; CPU iPhone OS 3_1_2 like Mac OS X; ja-jp) AppleWebKit/528.18 (KHTML, like Gecko) Version/4.0 Mobile/7D11 Safari/528.16" --user-data-dir="hogehuga"

ショートカットをひらいて,適当なページに行くと次の画面に飛ばされる.
f:id:YarmUI:20110506111755p:image
ユーザーIDはiPhoneのi.softbank.jpの方のメールアドレス.@以下も必要.パスワードはSMS/MMSでSoftbankから最初に送られてくるメッセージに書かれてる奴.
ログインできたらショートカットからひらいたブラウザは閉じて,別のプロファイルのChromeでも別のブラウザでもネットが出来るはず.

人材募集企画 2011年版に応募した

人生を書き換える者すらいた。: 人材募集企画 2011年版
これに応募した,今日の24時以降にブログに答えとか書くの解禁なので一応書く.かなり適当なんで間違ってたらすみません.

第一問
f(unsigned int x)はx<=2^nとなる最小の2^nを返す.ただしunsigned intのサイズがが32bitなら,x>2^31のとき0が返る.

アロケータとかでメモリ再確保のサイズ決めるのに使ったりするのかな?適当に値入れて確かめてもだいたい推定できるし,32bitの範囲程度ならテストパターン全部書いて総当たりしても確かめれる.
3行目から7行目の処理で,3行目で一番左側で1になってるビットがどう広がるかに注目すれば理解できると思う.

第二問
以下rubyソースコード.落下をcompact!で,探索の外枠を配列の-1番目の要素が最後の要素を指す事を使ってる.単純な再帰.

$H = 14   #最上段数
$W = 6

#外枠代わりのnilを追加
def add_nil(puyo)
  puyo.each{|a| a[$H] = nil}
  puyo[$W] = []
  return puyo
end

#空のゲームを生成
def form
  puyo = []
  $W.times{|i| puyo << []}
  return add_nil(puyo)
end

#ゲーム表示
def print_puyo(puyo)
  $H.times do |h|
    h = $H - h - 1
    $W.times{|w| print puyo[w][h]? puyo[w][h] : '*'}
    puts ''
  end
end

#4つ以上の同色を消して自由落下させる
#一組でも消えるぷよがあるならtrue,全然消えないときはfalseを返す
def step(puyo)
  def search(puyo, sc, w, h, c = puyo[w][h])
    return 0 if puyo[w][h].nil?
    return 0 if sc.key?([w, h])
    return 0 if c != puyo[w][h]
    sc[[w, h]] = true
    res = 1
    res += search(puyo, sc, w-1, h, c)
    res += search(puyo, sc, w+1, h, c)
    res += search(puyo, sc, w, h-1, c)
    res += search(puyo, sc, w, h+1, c)
    return res
  end
  
  def clear(puyo, sc)
    sc.each_key{|k| puyo[k[0]][k[1]] = nil}
  end
  
  def fall(puyo)
    puyo.each{|r| r.compact!}
    return add_nil(puyo)
  end
  
  res = false
  $H.times do |h| $W.times do |w|
    if puyo[w][h]
      sc = {}
      count = search(puyo, sc, w, h)
      if count >= 4
        clear(puyo, sc)
        res = true
      end
    end
  end end
  fall(puyo) if res
  return res
end

def read_puyo(str)
  puyo = form
  inv = str.split("\n").reverse.map{|e| e.split(//)}
  h = 0
  inv.each do |e|
    $W.times{|w| puyo[w][h] = inv[h][w] == ' ' ? nil : inv[h][w]}
    h += 1
  end
  return puyo
end


str = <<EOS
GGR
YGG
EOS

puyo = read_puyo(str)
chain = 0

begin
  puts "#{chain}chain"
  print_puyo(puyo)
  puts ''
  chain += 1
end while step(puyo)

第三問
これ書く意味ないと思うけどいちおう.
自分が選択したのは(a).投機は投資と同じ市場に影響を与える点で賭博と明確な違いがある.
賭博が現在違法なのはトラブル防止のためで,自分は理にかなってると思う.