Blog

jsdo.itで遊ぶ

jsdo.it – share JavaScript, HTML5 and CSS
wonderflのHTML5版、おもしろいですね。
JavascriptだけでなくHTMLやCSSも編集できるので、制作さんのマークアップの練習にも利用できます。

wonderflとの一番の違いは、その利用者層の広さだと思っています。
前述のように制作さんでもHTML+CSSのプレイグラウンドとして利用できるし、
デベロッパのJavascriptの書き方も人それぞれで幅広く、見ていて飽きません。
手続き型で情熱的に勢いよく書きまくっている人。
関数オブジェクト、prototype等を効果的に使って緻密に書いている人。
Actionscript3.0な世界よりも広大に見えます。
潜在的な開発者数はFlashよりも多いのでそれは当然のことなのかもしれません。

2003,4年頃(? でしょうか。
AS1.0のonClipEvent()から少しずつprototypeをいじり倒すようになり、そしてAS2.0のclassへ。
jsdo.itでもそれに似た成長過程をたくさんのコードの中で目にするようになるんじゃないかと思います。
とても楽しみです。


Möbius Strip – jsdo.it

 

Tags: ,

ActionScriptでSuffix Array

今回は画像処理ではなく文字列処理について。Suffix Arrayというデータ構造を扱います。

Suffix Array (接尾辞配列)は、もともと生物情報学の分野でゲノムデータベースの解析などに用いられてきたらしいのですが、そこからテキスト圧縮/検索などの自然言語文書を索引対象とした応用が広がり、全文検索エンジンの文字列索引(インデックス)としても利用されているデータ構造です。

Suffix(接尾辞)とは、索引対象となる文字列T内の任意の位置からTの末尾までの範囲の文字列のことで、Tの長さがNであればN個のSuffixが定義されインデックスが付与されます。Tの各Suffixは辞書順にソートされ、そのインデックスを配列にしたのがSuffix Arrayです。Suffixは辞書順にソートされているため、検索対象文字列をSuffix Array内で二分探索することにより、大規模テキストに対する高速な検索を可能にします。

詳細については以下のサイトにて詳しく解説されています。
suffix array

Suffix ArrayのActionScriptでのコード例を示します。
1: “abracadabra” という文字列データが入ったファイルを読み込み、そのデータでSuffix Arrayを構築(クイックソート使用)
2: Suffix Array構築完了後、”ac” という部分文字列を探索(二分探索)して出現位置を返却

package {
  import flash.display.Sprite;
  import flash.events.*;
  import flash.net.URLLoader;
  import flash.net.URLRequest;

  public class Test extends Sprite {
    private var sa:SuffixArray;
    private var urlLoader:URLLoader;

    public function Test() {
      urlLoader = new URLLoader();
      urlLoader.addEventListener(Event.COMPLETE, completeHandler, false, 0, true);
      urlLoader.addEventListener(IOErrorEvent.IO_ERROR, errorHandler, false, 0, true);
      urlLoader.load(new URLRequest("data.txt")); // abracadabra
    }
    private function completeHandler(e:Event):void {
      sa = new SuffixArray();
      var substring:String = "ac";
      sa.addEventListener(SuffixArray.BUILD_COMPLETE, function():void {
        trace(sa);
        trace("\nindex: " + sa.search(substring));
      }, false, 0, true);
      sa.build(e.target.data, SuffixArray.QUICK_SORT);
    }
    private function errorHandler(e:IOErrorEvent):void {
      trace(e);
    }
  }
}

import __AS3__.vec.Vector;
import flash.events.Event;
import flash.events.EventDispatcher;
import flash.utils.getTimer;

class SuffixArray extends EventDispatcher {
  public static const BUILD_COMPLETE:String = "build_complete";
  public static const QUICK_SORT:String = "quicksort";
  private var suffixes:Vector.<String>;
  private var len:int;
  private var _time:Number;

  public override function toString():String {
    return suffixes.join("\n");
  }
  /**
   * search substring, using binary search O(mlogn)
   */
  public function search(substring:String):int {
    if(len == 0) return substring.length == 0 ? 0 : -1;
    var low:int = 0, high:int = suffixes.length - 1;
    while(low < high) {
      var middle:int = low + (high - low)/2;
      if(suffixes[middle] >= substring) high = middle;
      else low = middle + 1;
    }
    if(suffixes[high].indexOf(substring, 0) == 0) {
      return len - suffixes[high].length;
    }
    return -1;
  }
  /**
   * build Suffix Array, O(n^2logn)
   */
  public function build(str:String, sortFunc:String = null):void {
    try {
      _time = getTimer();
      len = str.length;
      suffixes = new Vector.<String>(len, true);
      for(var i:int = 0; i < len; i++) {
        suffixes[i] = str.substring(i);
      }
      this[sortFunc]();
      _time = getTimer() - _time;
      dispatchEvent(new Event(BUILD_COMPLETE));
    }catch(e:ReferenceError) {
      suffixes.sort(
        function(x:String, y:String):int {
          return x > y ? 1 : x < y ? -1 : 0;
        }
      );
      _time = getTimer() - _time;
      dispatchEvent(new Event(BUILD_COMPLETE));
    }
  }
  public function get time():Number {
    return _time;
  }
  /**
   * apply Quick Sort
   */
  private function quicksort():void {
    _quicksort(suffixes, 0, suffixes.length - 1);
  }
  private function _quicksort(data:Vector.<String>, low:int, high:int):void {
    if(low > high) return;
    var i:int = low + 1, p:int = low, c:int = int((low + high)/2), pivot:String = data[c];
    data[c] = data[low];
    while(i <= high) {
      if(data[i] < pivot) {
        var tmp:String = data[++p];
        data[p] = data[i];
        data[i] = tmp;
      }
      i++;
    }
    data[low] = data[p];
    data[p] = pivot;
    _quicksort(data, low, p - 1);
    _quicksort(data, p + 1, high);
  }
}

• 実行結果

a
abra
abracadabra
acadabra
adabra
bra
bracadabra
cadabra
dabra
ra
racadabra

index: 3

ここで、テキスト圧縮技術の評価によく用いられるCalgary/Canterburyコーパス(書籍、ニュース、プログラムソースコード、ゲノム列(E.coli)などが含まれる)を用いてSuffix Arrayの構築時間を測ってみました。組み込みソート(Vector.sort())、クイックソート、マルチキークイックソート(Ternary Search Tree)での処理時間は以下の通りです(5回の計測時間の平均)。

• 環境:
Mac OSX 10.6.2: 2.26GHz / 2GB RAM
Flash Player: 10.0.45 (Debug)
Flex SDK: 4.0.0.14159

sorting time on texts (sec)
data size(byte) Vector.sort() QuickSort Multikey QuickSort
progc 39611 0.407 0.341 0.100
news 377109 5.022 4.285 1.323
book1 768771 10.819 9.958 3.144
world192 2473400 39.781 35.322 15.366
E.coli 4638690 Error #1502 Error #1502 29.258

4MB程度のデータ(E.coli)でも効率の悪いソート法だとFlash Playerがギブアップしてしまいます。。Suffix Arrayの欠点は構築に多くの時間がかかる点です。この問題を解決するためにマルチキークイックソートやMSD radix sort (基数ソート法, O(nlogn))、Two-Stage sort (二段階ソート法, O(n)) など数々の手法が提案されています。機会があればTwo-Stage sortあたりは一度書いてみたいなと思います。まぁでもFlashで大規模データは扱わないですよね。

Suffix Arrayは、整列(ソート)や探索、データ構造などをまとめて勉強できる教材として新人のC言語研修などに利用できるという話を聞きました。文字列配列を扱うのでポインタの勉強にも効果的かと。僕の所属部署では課題としては出ませんでしたが、検索事業などを持ってる部署ではN-gramと併せて課題の一つになってるみたいです。

あと、Suffix Arrayの構造を理解する為の小さなコードをwonderflに投稿しておきましたのでもし興味があれば。
Suffix Array | wonderfl build flash online

• 参考
CiNii 論文 -  Suffix arrayの効率的な構築法
suffix array
Sorting and Searching Strings

 

Tags:

CassandraのMemtableについて

引き続きCassandraについて調査中で、今回はCassandraの内部構造のひとつ、Memtableについて。

Cassandraでの書き込み操作はまずディスク上のCommitLog(書き込み操作のログ)に対して行われ、それからメモリ上のMemtableと呼ばれる構造体に対して書き込まれます。Memtableの構造は以下のようになっていて、ColumnFamily毎に保持されています。Key の列の Token は書き込み要求時にデータを保持するノードを決める際に計算されるものです。

Memtable関連の設定について

conf/storage-conf.xml にMemtable関連の設定項目があります。これらはMemtableがディスクにフラッシュされる(ディスク上のSSTableに非同期で書き込まれる)までの種々のしきい値を設定しています。

MemtableThroughputInMB
総データ操作量のしきい値
デフォルトは64(MB)、ColumnFamily単位で設定される

MemtableOperationsInMillions
保持されるカラム数のしきい値
デフォルトは0.3(Millionsなので300,000個)、ColumnFamily単位で設定される

MemtableFlushAfterMinutes
時間のしきい値
ここで設定した時間が経ってもまだフラッシュされてない場合は強制的にフラッシュされる
デフォルトは60(分)、プロダクション環境では1440などの大きな値の設定が推奨されている(storage-conf.xmlでのコメントより)

メモリ不足でノードが落ちてしまわないように、ColumnFamilyの数とそれぞれのColumnFamilyのカラム数などからきちんとこれらのしきい値を設定しておく必要があります。

分散ストレージ周りは個人で検証環境を用意するのは大変なので、会社のデータセンターを使わせてもらって検証しています。社内導入も真剣に考えていきたいなと思っていますがなかなか難しそうです;

・関連記事
Cassandra Java Client
Cassandra Thrift APIのConsistencyLevel
Cassandraについて

 

Tags:

CSSの解釈について

業務の合間に制作部の社内勉強会にちょこちょこ参加していろいろ学んだのでメモ。
ここではCSSの最適化について。

* ブラウザはCSSをどう解釈している?
ルールを照合するとき、右端のセレクタから調べ始めて、順に左のセレクタを調べていく。

ということは、

#contents > li { font-weight: bold; }

のようなルールの場合「contents という id を持つ要素を探して、その直接の子要素が li 要素かどうかを調べる」ではなく「すべての li 要素について、その直接の親要素が contents という id を持つかを調べる」となり高コストです。子孫セレクタの場合はさらに高くつき、

#contents a { color: #0099ff; }

のようなルールの場合「すべての a 要素について、contents という id を持つ祖先要素をツリー構造をさかのぼって探す」ということになります。子供セレクタであれば1つ上の階層のノードだけ調べれば済みますが、子孫セレクタの場合はさらにさかのぼって探索しなければなりません。Win IE6対応を無視してもいいなら、子孫セレクタから子供セレクタに置き換えた方がいいです。ただ、その子供セレクタも高コストには違いないので、それを1つの class に置き換えます。

#contents > li > a { font-weight: bold; }

ではなく

.list-anchor { font-weight: bold; }

のように要素と関連づけた名前で class を作ってスタイルを適用させることで、探索時間をさらに短くすることができます。

* ユニバーサルセレクタについて

* { margin: 0; padding: 0; }

一時期よく使われていたユニバーサルセレクタは最近では見かけなくなりました。社内の制作さんは、「パフォーマンスが悪くなる」という点よりも「ブラウザのデフォルトのスタイルを活かす」という点の方を重視しているみたいでしたが、ここまで述べてきた内容からパフォーマンスも相当悪くなるのは明らかです。その点について stevesouders.com さんが検証していました。
CSS Selectors: Universal
上述の子供セレクタや子孫セレクタによる読み込み時間の違いは小さなものですが、ユニバーサルセレクタを使用した場合はケタ違いに読み込みが遅くなっています。

* リフロー時間について
ブラウザがスタイルを適用し要素をレイアウトするのにかかる時間をリフロー時間と呼ぶそうです。スタイルの適用はページの読み込み時のみとは限りません。というのは、最近のWebサイトはJavascriptを多用していて、リッチな表現を行うためにDOM要素の style プロパティを頻繁に書き換えている例が多く見られます。

document.getElementById("id").style.property="value"
// 例
document.getElementById("contents").style.fontSize = "larger";

// 実際は上記のような処理がラップされたjQueryなどのライブラリを利用している場合が多い
// 制作工数とパフォーマンスのバランスを考えて使う
$("#contents").css("border", "1px solid #333333");

style プロパティを書き換えるとブラウザはその度にルールを照合しなおしています。もし、DOM要素が body などの多くの子孫を持つ要素の場合、効率の悪いセレクタがあるとページの反応が遅くなってしまいます。ページの読み込み時だけでなくWebアプリケーションがユーザと情報をやりとりしている間の動作に及ぶ影響にも注意することが重要です。

参加したのは新卒向けの勉強会だったので得られたのはこの程度の内容ですが、通常業務でも制作さんといっしょに仕事する機会ができたので、もう少し深い部分も聞いてみたいと思います。

 

Tags: , ,

Cassandra Java Client

前回 Cassandra Thrift APIのConsistencyLevel と内容的に前後してしまいますが、Cassandra APIのテストコードを一応載せておきます。データ操作(取得/登録/削除)に関するAPIはひととおり使用してあるので、コードを見ればだいたいの使い方は理解できると思います。また、各APIのシグネチャはCassandraのホームディレクトリにjavadocディレクトリがあるのでそこで確認できます。
(org.apache.cassandra.thrift.CassandraServer を参照)

以下のコードは、例としてブログ記事をデータとして扱っています。
・ColumnFamily は Entry
・entry* という key は title、category、tag の3つをcolumnを持つ

import java.util.*;
import java.io.UnsupportedEncodingException;
import org.apache.cassandra.thrift.*;
import org.apache.thrift.protocol.TBinaryProtocol;
import org.apache.thrift.protocol.TProtocol;
import org.apache.thrift.transport.TSocket;
import org.apache.thrift.transport.TTransport;
import org.apache.thrift.TException;
import org.apache.thrift.transport.TTransportException;

public class TestClient {
  private static final String KEYSPACE = "Keyspace1";
  private static final String COLUMN_FAMILY = "Entry";
  private TTransport transport = null;
  private Cassandra.Client client = null;
  TestClient() {
    client = getConnection();
  }
  private Cassandra.Client getConnection() {
    try {
      transport = new TSocket("localhost", 9160);
      TProtocol protocol = new TBinaryProtocol(transport);
      Cassandra.Client client = new Cassandra.Client(protocol);
      transport.open();
      return client;
    }catch(TTransportException e) {
      e.printStackTrace();
    }
    return null;
  }
  private void closeConnection() {
    try {
      transport.flush();
      transport.close();
    }catch(TTransportException e) {
      e.printStackTrace();
    }
  }
  private void selectEntry(String key) {
    try {
      SlicePredicate slicePredicate = new SlicePredicate();
      SliceRange sliceRange = new SliceRange();
      sliceRange.setStart(new byte[] {});
      sliceRange.setFinish(new byte[] {});
      slicePredicate.setSlice_range(sliceRange);
      ColumnParent columnParent = new ColumnParent(COLUMN_FAMILY);
      List<ColumnOrSuperColumn> results = client.get_slice(KEYSPACE, key, columnParent, slicePredicate, ConsistencyLevel.ONE);
      printData(key, results);
    }catch(Exception e) {
      e.printStackTrace();
    }
  }
  private void selectAllEntry() {
    try {
      KeyRange keyRange = new KeyRange();
      keyRange.setStart_key("");
      keyRange.setEnd_key("");
      SliceRange sliceRange = new SliceRange();
      sliceRange.setStart(new byte[] {});
      sliceRange.setFinish(new byte[] {});
      SlicePredicate slicePredicate = new SlicePredicate();
      slicePredicate.setSlice_range(sliceRange);
      ColumnParent columnParent = new ColumnParent(COLUMN_FAMILY);
      List<KeySlice> keySlices = client.get_range_slices(KEYSPACE, columnParent, slicePredicate, keyRange, ConsistencyLevel.ONE);
      for(KeySlice keySlice : keySlices) {
        printData(keySlice.getKey(), keySlice.getColumns());
      }
    }catch(Exception e) {
      e.printStackTrace();
    }
  }
  private void insertEntry(String key, Map<String, String> data) {
    try {
      Map<String, List<ColumnOrSuperColumn>> cfmap = new HashMap<String, List<ColumnOrSuperColumn>>();
      List<ColumnOrSuperColumn> columns = new ArrayList<ColumnOrSuperColumn>();
      Column column;
      ColumnOrSuperColumn columnOrSuperColumn;
      long timestamp = System.currentTimeMillis();
      for(Map.Entry<String, String> e : data.entrySet()) {
        column = new Column(e.getKey().getBytes("utf-8"), e.getValue().getBytes("utf-8"), timestamp);
        columnOrSuperColumn = new ColumnOrSuperColumn();
        columnOrSuperColumn.setColumn(column);
        columns.add(columnOrSuperColumn);
      }
      cfmap.put(COLUMN_FAMILY, columns);
      client.batch_insert(KEYSPACE, key, cfmap, ConsistencyLevel.ALL);
    }catch(Exception e) {
      e.printStackTrace();
    }
  }
  private void deleteEntry(String key) {
    try {
      ColumnPath columnPath = new ColumnPath(COLUMN_FAMILY);
      client.remove(KEYSPACE, key, columnPath, System.currentTimeMillis(), ConsistencyLevel.ALL);
    }catch(Exception e) {
      e.printStackTrace();
    }
  }
  private void updateEntry(String key, Map<String, String> data) {
    try {
      Map<String, Map<String, List<Mutation>>> mutationMap = new HashMap<String, Map<String, List<Mutation>>>();
      List<Mutation> mutations = new ArrayList<Mutation>();
      Column column;
      ColumnOrSuperColumn columnOrSuperColumn;
      Mutation mutation;
      long timestamp = System.currentTimeMillis();
      for(Map.Entry<String, String> e : data.entrySet()) {
        column = new Column(e.getKey().getBytes("utf-8"), e.getValue().getBytes("utf-8"), timestamp);
        columnOrSuperColumn = new ColumnOrSuperColumn();
        columnOrSuperColumn.setColumn(column);
        mutation = new Mutation();
        mutation.setColumn_or_supercolumn(columnOrSuperColumn);
        mutations.add(mutation);
      }
      Map<String, List<Mutation>> mutationsForColumnFamily = new HashMap<String, List<Mutation>>();
      mutationsForColumnFamily.put(COLUMN_FAMILY, mutations);
      mutationMap.put(key, mutationsForColumnFamily);
      client.batch_mutate(KEYSPACE, mutationMap, ConsistencyLevel.ALL);
    }catch(Exception e) {
      e.printStackTrace();
    }
  }
  private void printData(String key, List<ColumnOrSuperColumn> results) {
    try {
      System.out.println("Key: '" + key + "'");
      for(ColumnOrSuperColumn c : results) {
        if(c.getColumn() != null) {
          String name = new String(c.getColumn().getName(), "utf-8");
          String value = new String(c.getColumn().getValue(), "utf-8");
          long timestamp = c.getColumn().getTimestamp();
          System.out.println("  name: '" + name + "', value: '" + value + "', timestamp: " + timestamp);
        }
      }
    }catch(UnsupportedEncodingException e) {
      e.printStackTrace();
    }
  }
  /**
   * test cassandra api.
   */
  public static void main(String args[]) {
    TestClient c = new TestClient();
    // insert entry1
    Map<String, String> data = new HashMap<String, String>();
    data.put("title", "Cassandra Java Client");
    data.put("category", "tech/study");
    data.put("tag", "database");
    c.insertEntry("entry1", data);
    // insert entry2
    data = new HashMap<String, String>();
    data.put("title", "OpenCV 2.1 is out!");
    data.put("category", "tech/study");
    data.put("tag", "cv/im");
    c.insertEntry("entry2", data);
    // select entries
    System.out.println("select entries, using selectEntry()");
    c.selectEntry("entry1");
    c.selectEntry("entry2");
    // delete entry2
    System.out.println("delete entry2");
    c.deleteEntry("entry2");
    System.out.println("select entries, using selectEntry()");
    c.selectEntry("entry1");
    c.selectEntry("entry2");
    // update entry1
    System.out.println("update entry1: title, category");
    Map<String, String> updateData = new HashMap<String, String>();
    updateData.put("title", "change title");
    updateData.put("category", "change category");
    c.updateEntry("entry1", updateData);
    System.out.println("select entry1, using selectEntry()");
    c.selectEntry("entry1");
    // insert entry3
    c.insertEntry("entry3", data);
    // select all entries
    System.out.println("select all entries from Entry, using selectAllEntry()");
    c.selectAllEntry();
    c.closeConnection();
  }
}

データ登録では Cassandra.Client.batch_insert を使って複数のcolumnを一度にwriteしてますが、Cassandra.Client.insert という単一のcolumnをwriteするメソッドもあります。writeするcolumnが複数ある場合、その数だけ insert を呼ぶより batch_insert で一度にwriteした方が高速です。 ただし、”Deprecated in 0.6 – use batch_mutate instead” とAPIリファレンスに書いてあるように、データ登録時も Cassandra.Client.batch_mutate の利用が推奨されているようです。

CassandraのクライアントはThriftを利用しているので多言語対応していますが、やはり個人的にはJavaから操作するのがいいかなと思います。プロトタイピングでは Net::Cassandra(Perlの場合)などでさっと作って検証してから、Javaでじっくり書き直す感じになるでしょうか。

・関連記事
Cassandra Thrift APIのConsistencyLevel
Cassandraについて

 

Tags: ,