Buzzurlの中の人日記
JavaScriptのオブジェクトって、ハッシュテーブルのようにアクセスできます。ハッシュテーブルが必要なときにはオブジェクト作ってキーをプロパティとして値を突っ込んでハッシュテーブルとして使ってます。

でも、プロパティへのアクセスがあまり早くないことはよく知られていて、特に大量(と言っても数万件とかのオーダー)のデータを取り扱ったりするとすごく重くなったりするのを体験したことがある方も多いと思います。
超超高級言語とはいえ、いくらなんでもこんな遅くはならんだろうと常々いぶかしく思ってたわけです。

ふと思い立って、なんかオブジェクトのプロパティへのアクセスはハッシュテーブルと同等と勝手に思い込んでたけどもしかしてキーの数nに対してO(n)とかそれより遅いのとかになってんじゃね?とか思って確かめてみた。
まずは仕様書の和訳をざっと眺めるけど、特にプロパティアクセスに対する要求は見当たらない。(斜め読みなので要件があったらごめんなさい)
じゃあと思って調査。

やり方はキーの数100から10000まで100刻みのハッシュを用意して10000回値の読み書きを試みた。(キー数が少なすぎるけど、あんまり多くするとブラウザで実行するのがつらくなるので・・)

結果:IEもFFも読み取り書き込みともにO(1)だった。

当たり前の結果でつまんないのでベンチのソースは略。
別にハッシュテーブルの実装が悪いわけじゃなくて根本的に遅いだけだった。
Perl で手軽にイタレータっぽいことをやりたいんだが
うぅむ、呼出し元にて丸括弧の中に中括弧があるのが、みっともないなぁ。もっと美しい書き方は無いものか。で、dankogai氏のページを見た: 404 Blog Not Found:perl - for(1..1e10) と Iterator

というのを見て、プロトタイプ宣言してやれば map とかみたいにコードブロック渡せるんじゃないか?とおもってやってみたら無理だったという話。

多分、元々やりたいことはRubyのiteratorみたいに
$sar->each {
   my ($time, $p) = @_;
   print ("$time : $p\n");
};

こんな風に書けるメソッドを書きたいということだろうと思う。

でも↓のbad_eachでは期待したようには動かない

勉強不足で知らなかったのだけど、コードブロックを使いたいときは最初の仮引数じゃないとダメらしい。

package Sar;
use strict;

sub new {
    my $class = shift;
    bless {
        "time" => { "a" => "1", "b" => "2" }
    }, $class;
}

#↓これはダメ。コードブロックは1番目の仮引数じゃないと
# my $sar = new Sar();
# $sar->bad_each {
#   my ($time, $p) = @_;
#   print ("$time : $p\n");
# };
# とは書けない。
#
# $sar->bad_each( sub {
#   my ($time, $p) = @_;
#   print ("$time : $p\n");
# } );
# でないとコンパイルエラー
sub bad_each ($&){
    my ($this, $yield) = @_;
    my %times = %{$this->{time}};
    map{
        &{$yield}($_, $times{$_})
    } sort keys %times;
    undef;
}

最初の仮引数じゃなきゃだめということは、メソッドとしては実装できないので関数でやるしかないっぽい。

組み込みのmap/grep/sortなんかとの整合性としては正しい仕様という気もするけれど。

# Perlでコードブロックを使いたいときは、
#メソッドじゃなくて関数として実装するしかない?
# my $sar = new Sar();
# Sar::good_each {
#   my ($time, $p) = @_;
#   print ("$time : $p\n");
# } $sar;
sub good_each (&$) {
    my ($yield, $obj) = @_;
    my %times = %{$obj->{time}};
    map{
        &{$yield}($_, $times{$_})
    }sort keys %times;
    undef;
}

1;

しかしコードブロックのあとに渡すのがリストじゃなくてオブジェクトなのは気持ち悪いことこの上ない。でもリストを渡そうとする場合、$sar->{time}を隠蔽できない。アクセサなりなんなり適切なアクセス手段を用意してやればいいのだけど、$sar->{time}の詳細を見せるんだったら eachメソッドなんていらないという話だろう。

とはいえ、Perlとしてはこうやるのが自然という気がする。(iyahayaさんは$sar->{time}を隠蔽したりしたいのだろうから、これは邪道だけど)

my $sar = new Sar();
    my %times = %{$sar->{time}};
    map {
        print "$_ : $times{$_}\n"
    }sort keys %times;
id:JavaBlackさんから以下のようなツッコミをいただいた。トラックバックくれればいいのに

おれおれオブジェクト指向は何が違うのか


Java/C++/C#のオブジェクト指向的機能というのは、数学的なモデルとしては「包含関係を持つ集合をプログラマが任意に定義できる機能」と言える。包含関係というのはaggregationのことじゃなくて、集合としての包含関係なので、汎化/特化のことだ(つまり継承だ)。

http://blog.ajiyoshi.org/Entry/263/

たぶん,この人も全く分かってないと思う.憂鬱系のおれおれオブジェクト指向だと,こんな感じになります.


僕がオブジェクト指向をどうとらえているかというと、この定義がすっきりしていて綺麗だと思っている。

Rees Re: OO

以下に示すのは、[オブジェクト指向にまつわる]用語に関連づけられる機能や特性のメニューだ。オブジェクト指向というのは、このリストのいろいろなサブセットとして定義されているようだ。


  1. カプセル化 - 型の実装を構文的に隠蔽できること。例えばCやPascalでは何かが構造体であるか配列であるか常に意識することになるが、CLUやJavaではその違いを隠すことができる。


  2. 保護 - 型の使用者がその実装をのぞくことができないこと。これによって、ふるまいさえ変えなければ、実装を変更しても型の使用者に影響を与えないことが保障でき、またパスワードのような情報が漏れ出さないようにすることもできる。


  3. アドホックポリモルフィズム - 関数やパラメータつきデータ構造がたくさんの異なる型の値をとることができる。


  4. パラメトリックポリモルフィズム - 関数やデータ構造が任意の値 (例:任意のオブジェクトのリスト)に対してパラメタライズできること。 MLとLispはこれを持つ。Javaは非Objectな型のために、これを完全に持つとは言えない。


  5. 全てはオブジェクトなり - 全ての値はオブジェクト。Smalltalkでは真だが、 Javaでは (int等のため) 真ではない。


  6. メッセージを送ることだけができる (All you can do is send a message, AYCDISAM) = Actorモデル - オブジェクトを直接いじることはできず、それと通信する、もしくはそれを起動することのみができる。Javaにおけるfieldの存在はこれに反する。


  7. 仕様継承 = サブタイピング - ふたつの異なる型で、一方の型の値がもう一方の型の値として使われても型の正当性を破らないことを言語が保障できるようなもの。(例: Javaのインタフェース継承)。


  8. 実装継承, 再利用 - ひとまとまりのコードを書いたら、それと似たコード (そのスーパーセット) が制御された方法で生成できる。つまりコードをコピーして編集する必要がない。制限された、特殊な抽象化である。 (例: Javaのクラス継承)。


  9. 「関数の積和(sum-of-product-of-function)」パターン - オブジェクトは (実質的に)有限の簡単な名前の集合から選ばれるキー引数を第一引数に取り、それによってメソッドを呼び出す関数として動作する。




元記事は2002年に書かれたらしいので
Javaは {1,2,3,7,8,9} があるからオブジェクト指向だ。

と書かれているけど、今日のJavaにはGenericがあるので4も備えているだろう。
mixiでJavaScriptはオブジェクト指向言語か?という論争があったみたいだけど、上記の整理によるならば、{3,4,8,9}をもつからオブジェクト指向言語と言えるんじゃない?(4はダックタイピングにより実現されていると思う。genericとかC++のtemplateは静的な強い型を持つ言語で部分的にダックタイピングを実現するための仕組みであると言えると思う。8はprototypeベースというユニークで強力なやり方で実現されている。)

id:JavaBlackさんが過去にオブジェクト指向について書いた記事ざっと眺めると、id:JavaBlackさんはJava的なオブジェクト指向がオブジェクト指向のすべてである、ととらえてるように思える。まあ、これは推測に過ぎないので、id:JavaBlackさんのオブジェクト指向の定義を聞いてみたいところ


その上で、僕から見るとJava的オブジェクト指向というのは、静的で強い型システムと

File f = new Pipe(/* */);

のようなポインタ代入を両立させるための仕組み、としか思えない。これは結構な矛盾なので、強力な機能ではある。
(ああ、うん。確かに現実世界では継承じゃなくて委譲で解決する方がスマートな場合が多いですよね。でもそれは、継承によって解決できる問題領域が狭いということを示している。Javaにおけるオブジェクト指向的機能が解決している問題領域が主に「静的で強い型と継承を両立すること」であることを認めるならば、委譲の方がスマートっていうのはJavaのオブジェクト指向的な問題解決が力の弱い抽象化でしかなかったということを示すことになる。ということはむしろ昨日書いた文章の意図(=Java的なオブジェクト指向の設計は間違っていた/力が弱かった)を支持することになる。)
この機能によってどんなご利益があるかというと、例えばGoFデザインパターンみたいなのを自然に記述できるようになる。Cで同じようなことをしようとしたら、C++やJavaのコンパイラがやってくれる仕事を一部自分でするはめになる。

オブジェクト指向における再利用のためのデザインパターン

オブジェクト指向における再利用のためのデザインパターン
価格 : ¥5040 (税込)
メーカー : ソフトバンククリエイティブ
→Amazonで詳細を見る
→ECナビリストで詳細を見る
おすすめ度 :


一方僕の意見はなぜArcはとりたててオブジェクト指向でないのかとほとんど一緒。関数的な抽象が使えるなら、オブジェクト指向的抽象は別にイラネ。
もちろん関数的な抽象とオブジェクト指向という抽象は背反ではないけどね。実際Rubyなんかはブロック構文やらLambdaクラスやらで関数的な機能を部分的にサポートし始めているし。
でもそろそろオブジェクト指向をどうこう言ってる場合じゃなくて関数型言語やそのエッセンスをいかに身に付けるかという段階じゃないのかなぁ。(この点で自分が使う言語を自分で選べない職種の人はかわいそうだ)

なぜオブジェクト指向は嫌われているのか?

ざっと見たところ「設計が難しいよね」っていう意見が多いように思う。
このスレはたぶんプログラマ板だから想定されているオブジェクト指向言語はJava/C++/C#とかかな。
ここで言う「設計」というのはクラス設計のことだと考えていいだろう。もうちょっと大枠の設計の話になるとプログラミング言語はあんまり関係ないから。

んで、「Java/C++/C#はクラス設計が難しいから嫌われるよね」とする。
クラス設計が難しいのは色々考えると自明に思えるので、だから嫌われるんだとすると、Java/C++/C#のオブジェクト指向はそもそも解いている問題が不適切だった=設計が間違っていた、ということになるかなぁと思う。


なぜクラス設計が難しいのが自明かの説明を試みる。
Java/C++/C#のオブジェクト指向的機能というのは、数学的なモデルとしては「包含関係を持つ集合をプログラマが任意に定義できる機能」と言える。
包含関係というのはaggregationのことじゃなくて、集合としての包含関係なので、汎化/特化のことだ(つまり継承だ)。
例えば「FileInputStreamはInputStreamの一種である」とか、UNIX的なファイルの抽象化:「open/close/read/writeできるものは通常ファイルもデバイスもパイプもソケットもみんなファイルである」とかのことだ。
隠蔽も継承も多態も、みんなこれをプログラミング言語として自然に表現するための機能だ。

数学の集合の記述風に(いい加減な書き方だが)こんな風に書くのは
File = { x | x.open() / x.close() / x.read() / x.write() できるもの }
プログラミング言語では(擬似的にJava風に書くと)

public interface File {
public void open(/**/);
public void close(/**/);
public void read(/**/);
public void write(/**/);
}

に相当するだろうし、

Fileの一種であり特別な場合であるPipeは集合としてはFileの部分集合である。集合風には
Pipe = { x | x ∈ File かつ x は パイプ }
Pipe ⊆ File
こう書けるし、プログラミング言語では例えば

public class Pipe implements File {
public void open(/**/){ /*実装*/ }
public void close(/**/){ /*実装*/ }
public void read(/**/){ /*実装*/ }
public void write(/**/){ /*実装*/ }
}

こうなるだろう。
クラス定義 ≡ 集合を定義
であり、
インスタンス作成 ≡ 集合から元を一つ取り出す
であり、
継承 ≡ 部分集合を定義
である。
Pipe ⊆ File (PipeはFileの部分集合である)なので、Pipeの元はいつもFileの元であり、PipeインスタンスはいつもFileポインタに代入可能である。

File f = new Pipe(/**/);

一方で、興味深い集合を定義するのはすごく難しい。
同じ問題を解決するにしても、それを解決するための一連の集合を定義するときには無数の選択肢がある。(「読み書きできるものはなんでもファイル」という素晴らしい抽象化の上でもこれは難しい問題だ。例えば↑のFileインターフェイスの各メソッドはどんなシグネチャにすべきだろうか?)面白い集合定義もあればつまらない集合定義もある。例えば数学で言うと群とか、結合法則と単位元と逆元の存在を仮定するだけというすごくシンプルなクラス設計でありながらものすごく色々な興味深い性質を持つ。しかしみんながみんなアーベルやガロアみたいに興味深いやり方で集合を定義できる、とは思えない。

うん。全然説明になってないな。どうみてもトートロジーです。本当にありがとうございました。


昔はオブジェクト指向大好きだったんだけど、PerlやJavaScriptのような関数をリテラルとして扱える言語を使うようになったら、この手の抽象化のほうがオブジェクト指向が取り扱う抽象化よりもよりシンプルでより強力なんじゃないかと思うようになった。
関数をリテラルとして扱うというのは、関数を関数の引数に渡したり、戻り値として返したり、変数に束縛したり、定数として用意したりすることだ。
数学モデルとしては、「関数を集合の元として扱うことを許す」みたいなことを意味する。そしてこれは数学的には自然というかよくやることだ。(例:実数係数の多項式全体からなる集合Fが自然な加算と定数倍についてベクトル空間となることを証明せよ)
#関係ないけどクロージャとかは数学的にはどういうものなんだろう。普通の写像とは違うような気がするけど。誰か偉い人教えてください。

Mash up Caravanで発表した資料です。 JavaScriptでHTMLを生成するやり方に関する基本的な内容ですが、意外とこの辺がまとまったドキュメントってWeb上にないのではないかなと思います。

↓の Prev Next でページ送りします

LingrTickrを使ってバックチャンネルのチャットを表示するように仕込んで行ったんですが、会場が地下だったためネットつながらなくてぽしゃったのが心残りでした。

Previous | Next

Mash up Caravan 技術セッション

JavaScriptによるHTML生成
実践ノウハウ

  • 株式会社ECナビ 須藤洋一
ブログ(*「ふっかつのじゅもんがちがいます」)
http://blog.ajiyoshi.org
ソーシャルブックマーク
http://buzzurl.jp/user/y-sudo

自己紹介

  • ソーシャルブックマークBuzzurl(http://buzzurl.jp)のプロダクトマネージャ
  • 企画設計から開発テスト運用までなんでもやってます

バックチャンネル

http://www.lingr.com/room/buzzurl

  • ここで発言すると表示されるかもしれません

前提知識

  • JavaScriptを読み書きできること
  • prototype.jsを多少触ったことがあること
  • HTML/HTTPに関する基礎知識

取り扱わない話題

  • JavaScriptの書き方
  • 個別のライブラリの詳細な使い方

基本のおさらい

JavaScriptでHTMLを生成する(1)

  • Ajax/JSONPで何かするときはほぼ必須
  • Web上であまり情報が見つからない
  • どんな場合でも使える方法はおそらくない
    • LivedoorReaderのようなフルAjaxアプリケーション
    • フォームや読み込みを一部Ajax化
    • クライアントサイドマッシュアップ
    • Greasemonkey

JavaScriptでHTMLを生成する(2)

大きく2つの方法

  1. DOM操作APIを使う
  2. innerHTMLを使う

(1) DOM操作APIを使う

例:Buzzurlへのリンクを追加する

var url = "http://buzzurl.jp";
var a = document.createElement("a");
a.href = url;
a.appendChild(document.createTextNode("Buzzurl(バザール)"));
document.getElementById("target_1").appendChild(a); 

ここに追加されます

Issue:

DOM APIはかったるい

  • どんなHTMLになるか分かりにくい
  • 複雑なHTMLを作ろうと思うと辛い
  • 見栄えとロジックを分離しづらい

Solution:

  • 既存のライブラリを使う
    • jQuery
    • Mochikit.DOM
    • XMLBuilder
  • 自作のライブラリを作る
  • innerHTMLを使う

(2) innerHTMLを使う

サンプル

var html = "現在時刻:" + (new Date()).toString();
document.getElementById("target_2").innerHTML = html; 

ここに表示されます

Issue:

innerHTMLもかったるい

  • 文字列連結でHTMLを作るのは面倒
  • 変数を適切にエスケープしないとXSSの原因になりやすい(後述)

Solution:

テンプレートエンジンを使う

  • 既存のライブラリ
    • prototype.js
    • ajax pages
    • TrimPath
    • ...etc. etc.
  • 自前で作る

テンプレートエンジンを使う

例:prototype.jsのTemplate

<textarea id="templ_1">
	<a href="#{home}"><img src="#{photo}"></a>
</textarea>
var t = new Template($F("templ_1"));
var data = {
	home:"http://buzzurl.jp/user/y-sudo",
	photo:"http://file.blog.ajiyoshi.org/photo.jpg"
};
$("target_3").innerHTML = t.evaluate(data);

実践セキュリティ

実践セキュリティ

安全でないデータ

<textarea id="templ_1">
	<a href="#{home}"><img src="#{photo}"></a>
</textarea>
var t = new Template($F("templ_1"));
var unsafe = {
	home:"http://buzzurl.jp/user/y-sudo",
	photo:'http://file.blog.ajiyoshi.org/photo.jpg" onload="alert(\'xss\')'
};
$("target_4").innerHTML = t.evaluate(unsafe); 

実践セキュリティ

表示する直前にHTMLエスケープ

<textarea id="templ_0">
	<img src="http://file.blog.ajiyoshi.org/photo.jpg" onload="alert('XSS')">
</textarea>
function escape_html(str){
	str = str.replace(/&/g, "&amp;");
	str = str.replace(/"/g, "&quot;");
	str = str.replace(/'/g, "&#x27;");
	str = str.replace(/</g, "&lt;");
	str = str.replace(/>/g, "&gt;");
	return str;
}

var unsafe = $F("templ_0");
$("target_esc").innerHTML = escape_html(unsafe);

実践セキュリティ

HTMLエスケープ

<textarea id="templ_1">
	<a href="#{home}"><img src="#{photo}"></a>
</textarea>
var t = new Template($F("templ_1"));
var unsafe = {
	home:"http://buzzurl.jp/user/y-sudo",
	photo:'http://cdn.buzzurl.jp/user/y-sudo/photo" onload="alert(\'xss\')'
};
var escaped = {
	home:escape_html(unsafe.home),
	photo:escape_html(unsafe.photo)
};
$("target_5").innerHTML = t.evaluate(escaped);

実践セキュリティ

注意:prototype.jsは " や ' をエスケープしない

<textarea id="templ_1">
	<a href="#{home}"><img src="#{photo}"></a>
</textarea>
var t = new Template($F("templ_1"));
var unsafe = {
	home:"http://buzzurl.jp/user/y-sudo",
	photo:'http://file.blog.ajiyoshi.org/photo.jpg" onload="alert(\'xss\')'
};
var escaped = {
	home:unsafe.home.escapeHTML(), photo:unsafe.photo.escapeHTML()
};
$("target_6").innerHTML = t.evaluate(escaped);

実践セキュリティ

まとめ

  • 表示の直前でエスケープするのが鉄則
  • HTMLエスケープされた状態で受け取ることもありうる
  • アプリケーション側はエスケープ済みと期待すべきではない
  • 混在環境ではアンエスケープしてからエスケープする

実践パフォーマンス

実践パフォーマンス

次のことをすると とても 重い

  1. 巨大なDOMツリーを作成
  2. onclick等のイベントハンドラを含むとさらに重い(特にIE)
  3. imgはさらにさらに重い

実践パフォーマンス

単純な<a>タグ

function now(){ return (new Date()).getTime() }
var num = Math.floor($F('num_7'));
var html = (new Array(num)).map( function(){ return $F('templ_2') } ).join("");
$("target_7").innerHTML = "";
setTimeout(function(){
	var start = now();
	var p = document.createElement("p");
	p.innerHTML = html;
	$("target_7").appendChild(p);
	var end = now();
	var li = document.createElement("li");
	li.appendChild(document.createTextNode((end-start)+"msec to "+(num*100)+" elements"));
	$("score_7").insertBefore(li, $("score_7").firstChild);
}, 100);

実践パフォーマンス

イベントハンドラ付きの<a>

function now(){ return (new Date()).getTime() }
var num = Math.floor($F('num_8'));
var html = (new Array(num)).map( function(){ return $F('templ_3') } ).join("");
$("target_8").innerHTML = "";
setTimeout(function(){
	var start = now();
	var p = document.createElement("p");
	p.innerHTML = html;
	$("target_8").appendChild(p);
	var end = now();
	var li = document.createElement("li");
	li.appendChild(document.createTextNode((end-start)+"msec to "+(num*100)+" elements"));
	$("score_8").insertBefore(li, $("score_8").firstChild);
}, 100);

実践パフォーマンス

イベントハンドラ付きの<img>

function now(){ return (new Date()).getTime() }
var num = Math.floor($F('num_9'));
var html = (new Array(num)).map( function(){ return $F('templ_4') } ).join("");
$("target_9").innerHTML = "";
setTimeout(function(){
	var start = now();
	var p = document.createElement("p");
	p.innerHTML = html;
	$("target_9").appendChild(p);
	var end = now();
	var li = document.createElement("li");
	li.appendChild(document.createTextNode((end-start)+"msec to "+(num*100)+" elements"));
	$("score_9").insertBefore(li, $("score_9").firstChild);
}, 100);

DOM操作は重い

まとめ

  • なるべく巨大なDOMツリーの作成/更新をしない
  • 必要最小限の更新にとどめる
  • 文字列の構築と描画の間に制御を返す

おしまい

  • どうみても終わりです。
  • 本当にご清聴ありがとうございました。
<< 前のページ [1] [2] [3] [4] [5] [6] [7] [8] [9] 次のページ >>
プロフィール
HN:
ajiyoshi
性別:
男性
自己紹介:
プログラマです。
ソーシャルブックマークサービス「Buzzurl」の開発者です。

はてなブックマークカウンタ


旧*「ふっかつのじゅもんがちがいます」カウンタ
Buzzurl

powered by Buzzurl

Twitter

カレンダー
08 2010/09 10
S M T W T F S
1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30
最新コメント
[07/23 つらら]
[07/23 れいら]
[06/16 婚活]
[05/28 あっだ]
[05/28 もも]
最新トラックバック
バーコード
ブログ内検索
忍者ポイント
カウンター
アクセス解析
あわせて読みたい
あわせて読みたい
Powered by ニンジャブログ  Designed by ゆきぱんだ
Copyright c *「ふっかつのじゅもんがちがいます。」 All Rights Reserved
忍者ブログ / [PR]就職 保育士