pandazx's blog

Hadoop, データ分析など雑多な技術ブログ

お勉強(MVC, DOM, ツリー構造)

MVC

DDD - MVCの流れを簡単にまとめてみる - Qiita [キータ]
Twitterで流れてきたMVC変遷の流れに関する記事。
まだまだ疎結合に設計するための考え方、実装方法は進化しているんだな。

DOM

DOMとは何か
HTMLを操作する時に作るオブジェクトが「DOM」ということだけは知っていたが、
DOMって何なの?というのはイマイチわかっていなかった。
これを読んだ結果、抽象的な概念的仕様であることがわかった。

ツリー構造

高速かつ省メモリで文字列を扱うデータ構造「wavelet tree」 (1/2):CodeZine
処理の高速化と省メモリ化を行うためにはデータ構造をツリー構造に落とし込めるとよい。
そのための、wevelet treeについて。
wevelet treeを使うことで以下の効用がある。

  • 文字cのi番目の出現位置や、文字cの位置pまでの出現回数を定数時間で答えるデータ構造
  • 作業領域量は元テキストの約2倍

例えば、変換対象の文字列をHuffman符号で01のビット列に符号化し、
それをツリー構造に置き換えることでwevelet treeを構築する。

開発メモ: オンメモリB+木による省メモリ連想配列
Kyoto CabinetにB+木を使ってメモリ空間効率を重視したGlassDBを追加したという話。
トレードオフとして計算時間効率を落としている。