2014年 12月 の投稿一覧

JavaScriptの処理時間を計測する(console.time / console.timeEnd)

肝心なところ知らないこと多い...。

console.timeconsole.timeEnd で挟んだ部分の時間を計測できる。引数にはラベル名を指定できてそのラベルで対応した範囲の時間が計測される。

// Indexing
console.time("indexing");
var stream = byline(fs.createReadStream('/tmp/foo.txt', { encoding: 'utf8' }));
var i=0;
stream.on('data', function(line) {
indexing(i, line);
i++;
});
stream.on('finish', function(){
console.timeEnd("indexing");
// Search
console.time("search");
var res = search("コロスケ", 2);
console.timeEnd("search");
// Results
var resultOut = _.template("文書番号=<%=no %> : 文字位置=<%=pos %>")
_.each(res, function(v){
console.log(resultOut(v));
});
});

こうすると、以下の様な形で処理時間を計測できる。

$ node test.js
indexing: 5ms
search: 1ms
文書番号=0 : 文字位置=15
文書番号=2 : 文字位置=8
文書番号=2 : 文字位置=35

2014年を振り返る

このブログに書いた記事を眺めながら1年を振り返ってみました。
なんだかんだそれなりにアウトプットできた1年になったのでよかったと思えるので、質・量ともにもっと上げていける様にしたいと思います。

また来年は公私ともにいろいろ変化する年になりそうなので、肩に力入れない様にしつつも、必死に食らいついて行こうと思います。

今年の出来事

*1:仕事が忙しかった...

node.jsで1行毎にテキストファイルを読む – byline: buffered Stream for reading lines

素朴に便利だったのでメモエントリ。

$ npm install byline --save

npmからインストールして以下の様な形で使える。

var byline = require('byline');
var fs = require('fs');
var stream = byline(fs.createReadStream('/tmp/foo.txt', { encoding: 'utf8' }));
stream.on('data', function(line) {
console.log(line);
});
stream.on('finish', function(){
console.log("ファイル読み終わり");
});

redisの型について整理した

redisの型の認識が何気だったので改めて整理してみた。自分の頭の整理用に図も描いたりしたのでせっかくなので掲載。


文字列型

一番シンプルな形。

127.0.0.1:6379> SET key1 value1
OK
127.0.0.1:6379> SET key2 value2
OK
127.0.0.1:6379> GET key1
"value1"
127.0.0.1:6379> GET key2
"value2"
127.0.0.1:6379> MGET key1 key2
1) "value1"
2) "value2"

expireを設定することもできるのでキャッシュとして用いる場合はこれを利用する。

127.0.0.1:6379> SETEX cache1 5 cache-val1
OK
127.0.0.1:6379> GET cache1
"cache-val1"
(5秒経過後)
127.0.0.1:6379> GET cache1
(nil)

リスト型

双方向な線形リストで構成。要素の追加の方向は基本先頭か末尾。

これを利用することでスタックやキューを構成することができる。

スタック(LIFO)

LPUSH , LPOP を利用するとスタックを構成できる。LPOPで取り出されている要素を確認すると一番最後に格納した要素から取り出せている。

127.0.0.1:6379> LPUSH list1 1
(integer) 1
127.0.0.1:6379> LPUSH list1 2
(integer) 2
127.0.0.1:6379> LPUSH list1 3
(integer) 3
127.0.0.1:6379> LPOP list1
"3"
127.0.0.1:6379> LPOP list1
"2"
127.0.0.1:6379> LPOP list1
"1"
127.0.0.1:6379> LPOP list1
(nil)

キュー(FIFO)

RPUSH, LPOPを利用するとキューを構成できる。LPOPから取り出されている要素を確認すると最初に格納した要素が取り出せている。

127.0.0.1:6379> RPUSH list1 1
(integer) 1
127.0.0.1:6379> RPUSH list1 2
(integer) 2
127.0.0.1:6379> RPUSH list1 3
(integer) 3
127.0.0.1:6379> LPOP list1
"1"
127.0.0.1:6379> LPOP list1
"2"
127.0.0.1:6379> LPOP list1
"3"
127.0.0.1:6379> LPOP list1
(nil)

リスト操作

リストに対して部分操作ができる。例えば先頭から2要素を抽出するときは LRANGE コマンドを使う。

127.0.0.1:6379> RPUSH list1 1
(integer) 1
127.0.0.1:6379> RPUSH list1 2
(integer) 2
127.0.0.1:6379> RPUSH list1 3
(integer) 3
127.0.0.1:6379> RPUSH list1 4
(integer) 4
127.0.0.1:6379> LRANGE list1 0 1
1) "1"
2) "2"

セット型

値の重複を許さない文字列型の集合で且つ集合同士の操作ができる。例えば SINTER コマンドを使うと積集合を得ることができる。

下の例だと集合 set1set2 に対して SINTER コマンドを発行すると両方の集合に対して属している 3 が取り出せている。

127.0.0.1:6379> SADD set1 1
(integer) 1
127.0.0.1:6379> SADD set1 2
(integer) 1
127.0.0.1:6379> SADD set1 3
(integer) 1
127.0.0.1:6379> SADD set2 3
(integer) 1
127.0.0.1:6379> SADD set2 4
(integer) 1
127.0.0.1:6379> SADD set2 5
(integer) 1
127.0.0.1:6379> SINTER set1 set2
1) "3"

ソート済みセット型

セット型で更にそれぞれの要素はスコアを持ち、そのスコアにもとづいてソートされた形で格納される。

127.0.0.1:6379> ZADD sortset 5 A
(integer) 1
127.0.0.1:6379> ZADD sortset 10 B
(integer) 1
127.0.0.1:6379> ZADD sortset 8 C
(integer) 1
127.0.0.1:6379> zrangebyscore sortset -inf +inf
1) "A"
2) "C"
3) "B"

ハッシュ型

こちらはそのまま。集合内の要素は全てキーと値で一意となるハッシュとして管理される。

127.0.0.1:6379> HSET hash1 foo 10
(integer) 1
127.0.0.1:6379> HSET hash1 bar 20
(integer) 1
127.0.0.1:6379> HSET hash1 hoge 30
(integer) 1
127.0.0.1:6379> HGET hash1 foo
"10"
127.0.0.1:6379> HGET hash1 bar
"20"
127.0.0.1:6379> HGET hash1 hoge
"30"
127.0.0.1:6379> HGET hash1 hoge2
(nil)

REMPチーム忘年会

餃子の様子です。

会社の近くの中華屋さんでREMPチームの忘年会だった。

特にコースなどは頼まず食べたいものをどんどん頼もうスタイルで餃子、ビール、酢豚、紹興酒ピータン豆腐、レモンハイ、麻婆豆腐...(以下続く)... などと食欲をひたすら満たす感じでとても満足。

今年はCastoを作ったり、Casto用のcliツールを作ったりと今年もあれこれできてとても良かった。

ふと思ったけど、この面々で続けられているのは、とにかく「無理せず細く長く気が向いた時にガッとやる」ところが長続きできているコツかもしれないと勝手に思ってる。


転置インデックスを利用して検索してみる

n-gram及び、転置インデックス を作ってみたので実際に検索してみます。

var _ = require('underscore');
// (snip)
var search = function (query, n) {
  var grams = ngram(query, n),
    firstPostingList = invertedIndex[grams[0]],
    results = [];
  var searchProcess = function (positions, key) {
    positions.forEach(function (pos) {
      if (query.length <= n) {
        results.push({
          no: key,
          pos: pos
        });
      } else {
        for (var i = 1; i < grams.length; i++) {
          postingList = invertedIndex[grams[i]];
          if (postingList[key]) {
            var targetList = postingList[key];
            if (_.contains(targetList, pos + i)) {
              if (i == grams.length - 1) {
                results.push({
                  no: key,
                  pos: pos
                });
              }
            } else {
              continue;
            }
          }
        }
      }
    });
  };
  _.each(firstPostingList, searchProcess);
  return results;
}
// Indexing
var text = ["本日は晴天なり。いい天気なり。コロスケなり。", "コロばない様にスケートボートに乗ります", "今日は黒豆を煮てコロスケとコロコロコミックとコロッケを買いに行きます。コロスケ〜。"];
for (var i = 0; i < text.length; i++) {
  indexing(i, text[i]);
}
// Search
var res = search("コロスケ", 2);
// Results
var resultOut = _.template("文書番号=<%=no %> : 文字位置=<%=pos %>")
_.each(res, function (v) {
  console.log(resultOut(v));
});

これを実行してみると、「コロスケ」で検索した結果が出力されます。

文書番号=0 : 文字位置=15
文書番号=2 : 文字位置=8
文書番号=2 : 文字位置=35

インデックスに投入した文書とくらべて、検索した単語が含まれる文書が抽出できていて且つ、出現位置も正しく特定できています。

やっていることとしては、

  • 検索語をn-Gramで分割する (上の例なら "コロスケ" → "コロ", "ロス", "スケ")
  • 分割された最初の分割語を持つ文書とその出現位置を転置インデックスから得る
  • 得られた一つ目の文書について
    • 2番目の分割語がその文書に含まれているか確認する
    • 含まれていればその語の出現位置が1番目の検索語の次にあるかを確認する
    • 以下、検索語を分割した数だけ繰り返す
  • 以下、分割された最初の分割語が含まれる文書数繰り返す

といった手順。

ひとまず素朴な検索ができたけれど、このままだと転置インデックスが永続化されないですね。

では、次に何かしらのストレージを利用して永続化させることをやってみます。


一連のn-gram, 転置インデックス, 検索の話は以下の本を読んでいたら実際に手を動かして確認したくなったので試してみたのでした。

具体例も多く、読んでいても面白いですが実際に手を動かすともっと面白いのでお勧め。

今回の話は第4章「検索しよう」の内容を読みながら進めてみました。

monochromeというサイトをロリポタッチで作った

ロリポタッチ iPhone版でモノクロ写真ばかり載っけるホームページ作りました。

かの昔、FTPでアップロードしていたことを考えると本当に簡単にサイトが作れるの便利。


ハンバーグと目玉焼き

お昼ごはんに会社の近くのハンバーグ屋さんへ。ハンバーグは「上に目玉焼きを乗せると美味しい食べ物ランキング」のかなり上位に位置する。

ただ、対抗として白ご飯に目玉焼きを乗せて刻み海苔と醤油をかけた目玉焼き丼がいることは忘れてはいけないし、その後ろには焼きそば目玉焼きのせ迫っていることを忘れてはいけない。

ものすごくどうでもいいことを書いた気がする。

JavaScriptで転置インデックスを作る

先日ngramに分割する処理を書いたので次は転置インデックスを作ってみます。
今回は完全に単語の位置まで記録するものとし、

{'晴天': { '0': [ 3 ] }}

といった具合で2-gramで分割された単語とそれに対応する文書とその位置が管理されるものとします。上の例だと「晴天」という単語は文書番号0の3文字目に記録されているといった具合。

var invertedIndex = {}
var ngram = function(words, n) {
  var i;
  var grams = [];
  for(i=0; i<=words.length-n; i++) {
    grams.push(words.substr(i, n).toLowerCase());
  }
  return grams;
}

var indexing = function(no, str) {
  ngram(str, 2).forEach(function(gram, index, array) {
    var postingList;
    if (invertedIndex[gram]) {
      postingList = invertedIndex[gram];
    } else {
      postingList = {};
    }
    if (postingList[no]) {
      postingList[no].push(index);
    } else {
      postingList[no] = [index];
    }
    invertedIndex[gram] = postingList;
  });
}

これに対して文書を与えることで2-gramな転置インデックスが作成されます。

var text = [
"本日は晴天なり。いい天気なり。コロスケなり。",
"コロばない様にスケートボートに乗ります",
"今日は黒豆を煮てコロスケとコロコロコミックとコロッケを買いに行きます"
];
for(var i=0; i<text.length; i++) {
indexing(i, text[i]);
}

実際に転置インデックスを覗いてみます。

> console.log(invertedIndex)
{ '本日': { '0': [ 0 ] },
'日は': { '0': [ 1 ], '2': [ 1 ] },
'は晴': { '0': [ 2 ] },
'晴天': { '0': [ 3 ] },
'天な': { '0': [ 4 ] },
'なり': { '0': [ 5, 12, 19 ] },
'り。': { '0': [ 6, 13, 20 ] },
'。い': { '0': [ 7 ] },
'いい': { '0': [ 8 ] },
'い天': { '0': [ 9 ] },
'天気': { '0': [ 10 ] },
'気な': { '0': [ 11 ] },
'。コ': { '0': [ 14 ] },
'コロ': { '0': [ 15 ], '1': [ 0 ], '2': [ 8, 13, 15, 22 ] },
'ロス': { '0': [ 16 ], '2': [ 9 ] },
'スケ': { '0': [ 17 ], '1': [ 7 ], '2': [ 10 ] },
'ケな': { '0': [ 18 ] },
(以下省略)

といった具合。「コロ」という語が文書番号2(text変数の3番目の配列)に頻出しているので確認できやすいですね。

じゃ、次はこれを使って検索してみようということになるので、これはまた次回。