自動散策 by ストリートビュー

自作アプリ ストリートビュー

ストリートビューで自動散策するプログラム、AutoWalk by Street Viewを作成した。

自分のWEBサイトへの掲載方法

次のようなHTMLを作成することで、自分のWEBサイトに自動散策プログラムを埋め込むことができる。初期地点は自由に設定できるので、自分の街を自動散策するようなプログラムを埋め込むこともできる。

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
  "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="content-type" content="text/html; charset=utf-8" />
<title>AutoWalkのサンプル</title>
<script src="http://maps.google.com/maps?file=api&amp;v=2&amp;key=(取得したキー)"
	type="text/javascript"></script>
<script src="http://www.kappuccino.jp/autowalk.js"
	type="text/javascript"></script>
<script type="text/javascript">
//<![CDATA[
	// 初期位置
	var initialPosition = new GLatLng(35.003277, 135.774991);
	// 初期視線方向
	var initialPov = {yaw:0, pitch:0, zoom:0}
	// Googleマップの初期ズームレベル
	var initialZoomLevel = 18;
//]]>
</script>
</head>
<body onload="load()" onunload="GUnload()">
<div id="autowalk-street" style="width: 800px; height: 300px;"></div>
<div id="autowalk-map" style="width: 800px; height: 200px;"></div>
</body>
</html>
AutoWalk by Street Viewのサンプル


以下順に解説する。

Google Maps APIの読み込み

<script
	src="http://maps.google.com/maps?file=api&amp;v=2&amp;key=(取得したキー)"
	type="text/javascript"></script>

(取得したキー)の部分を取得したGoogle Maps APIのキーに置き換える必要がある。

AutoWalk by Street Viewの読み込み

<script src="http://www.kappuccino.jp/autowalk.js"
	type="text/javascript"></script>

初期位置の設定

GLatLngの引数は、緯度、経度の順。

// 初期位置
var initialPosition = new GLatLng(35.003277, 135.774991);

初期視線方向の設定（省略可）

視線方向のパラメータは次の通り。

プロパティ 型 解説
yaw Number 水平方向の角度。0〜360度で設定。0が北、90が東、180が南、270が西。
pitch Number 上下方向の角度。-90〜90度で設定。-90が真上、0が水平、90が真下。
zoom Number ズーム。0以上の値を設定。0は最も引いた状態。 
// 初期視線方向
var initialPov = {yaw:0, pitch:0, zoom:0}

Googleマップの初期ズームレベルの設定（省略可）

大きいほど地図が拡大した状態で始まる。あまり大きくしすぎると、地域によっては表示されない。

// Googleマップの初期ズームレベル
var initialZoomLevel = 18;

プログラムの実行

↓のonload属性でプログラムを呼び出す。

<body onload="load()" onunload="GUnload()">

ストリートビューの表示

id="autowalk-street"を指定されたHTML要素にストリートビューを表示。styleの部分は任意。CSSファイルで指定することも可能。

<div id="autowalk-street" style="width: 800px; height: 300px;"></div>

ストリートビューの表示（省略可）

id="autowalk-map"を指定されたHTML要素にGoogleマップを表示。省略してストリートビューのみを表示することもできる。

<div id="autowalk-map" style="width: 800px; height: 200px;"></div>

免責事項

AutoWalk by Street Viewの利用に関連した一切の損失に関して、作成者Kappuccinoは責任を持ちません。そのことに同意の上でご利用下さい。

ストリートビューのAPI

ストリートビューのAPIの使い方についてはこちらのエントリーをどうぞ。

ストリートビューのAPI（京都散策のサンプル）

ストリートビュー Google Maps API オススメ

(2008-08-15)『Googleマップ上でストリートビュー対応の道を青色ハイライト表示する（GStreetviewOverlay）』を追記しました


先日、Google Mapsのストリートビュー日本版が公開されたところですが、早速Google Maps APIを用いてストリートビューをいじってみました。ストリートビュー関連APIを使ったサンプルアプリケーションを紹介した上で、APIの使い方について説明します。

サンプルアプリケーション（京都散策 by Google Maps Street View）

京都散策 by Google Maps Street View

Google Maps APIのストリートビュー関連の機能を使ったサンプルアプリケーションを作成してみました。京都市内を勝手に歩き回ります。分かれ道まで来るとランダムにルートを選んで進んで行きます。

（自動散策プログラムを自分のサイトに埋め込めるようになりました。初期位置を指定してストリートビューで自動散策します。）

ストリートビューのAPIの使い方

Google Maps APIリファレンス日本語版にはまだストリートビュー関連機能は掲載されていないようです。英語版であれば、こちらにリファレンスがあります。これを見ながらいくつかの機能を触ってみたので紹介します。


ストリートビュー関連機能を使うには、まずGoogle Maps APIのキーを取得する必要があります。すでにGoogle Maps APIのキーを持っている人はそのまま使うことができます。

ストリートビューを表示する一番簡単なソースは次のようになります。（実行結果はこちら）

streetviewsample.js
function load() {
	// 初期位置の緯度、経度からGLatLngオブジェクトを生成。
	var startingPosition = new GLatLng(35.003277,135.774991);
	
	// Google Street Viewに渡すオプションを生成（この例では初期位置のみ）。
	panoramaOptions = {latlng:tartingPosition};
	
	// Google Street Viewを表示するGStreetviewPanoramaオブジェクトの生成。
	//   第1引数:Google Street Viewを埋め込むHTML要素（この例ではidをstreetviewerにした）。
	//   第2引数:Google Street Viewに渡すオプションを生成（この例では初期位置のみ）。
	var panorama = new GStreetviewPanorama(
		document.getElementById("streetviewer"),panoramaOptions
		);
	
	// エラー処理のためにリスナーを追加（handleNoFlashに関しては後で定義）。	
	GEvent.addListener(panorama,"error",handleNoFlash);
}

// Flash Playerを検出できない場合の処理用関数。
function handleNoFlash(errorCode) {
	if (errorCode == FLASH_UNAVAILABLE) {
		alert("Error:Flash Playerをインストールして下さい。");
		return;
	}
}
streetviewsample.html
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
  "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="content-type" content="text/html; charset=utf-8" />
<title>Street View Sample of Google Maps API</title>
<script src="http://maps.google.com/maps?file=api&amp;v=2&amp;key=(取得したGoogle Maps APIのキー)"
	type="text/javascript"></script>
<script src="streetviewsample.js" type="text/javascript"></script>
</head>
<body onload="load()" onunload="GUnload()">
<div id="streetviewer" style="width:800px; height:450px;"></div>
</body>
</html>

視線方向を決める（GPov）

ストリートビューはぐりぐりと視線方向を回転させられるのが売りの一つですが、その視線方向を設定するためのクラスがGPovです（厳密には方向だけでなく、ズームの度合いも扱う）。

GPovクラス
プロパティ 型 解説
yaw Number 水平方向の角度。0〜360度で設定。0が北、90が東、180が南、270が西。
pitch Number 上下方向の角度。-90〜90度で設定。-90が真上、0が水平、90が真下。
zoom Number ズーム。0以上の値を設定。0は最も引いた状態。

GPovには上記のように、yaw、pitch、zoomの三つのパラメータがあります。


GPovにはyaw、pitch、zoomを設定するメソッドがないので、次のように直接パラメータを設定します。

var pointOfView = new Object(); // GPovにはコンストラクタがない。
pointOfView.yaw = 180; // 0〜360度で設定。0が北、90が東、180が南、270が西。
pointOfView.pitch = 90; // -90〜90度で設定。-90が真上、0が水平、90が真下。
pointOfView.zoom = 0; // 0以上の値を設定。0は最も引いた状態。

上記のプログラムはオブジェクトリテラルを用いて次のようにも書けます（この方法で書く方が一般的）。

var pointOfView = {yaw:80, pitch:0, zoom:};
GPovの使い方

GPovを初期状態で渡すには次のようにします。

// GPovの作成。
var pointOfView = {yaw:180, pitch:90, zoom:};

// 初期位置の緯度、経度からGLatLngオブジェクトを生成。
var startingPosition = new GLatLng(35.003277, 135.774991);

// Google Street Viewに渡すオプションを生成（povにGPovを渡すと初期視点方向を設定）。
panoramaOptions = {latlng:tartingPosition, pov:ointOfView};

// Google Street Viewを表示するGStreetviewPanoramaオブジェクトの生成。
//   第1引数:Google Street Viewを埋め込むHTML要素（この例ではidをstreetviewerにした）。
//   第2引数:Google Street Viewに渡すオプションを生成（この例では初期位置のみ）。
var panorama = new GStreetviewPanorama(
	document.getElementById("streetviewer"),panoramaOptions
);


後から視線方向を変えるにはGStreetviewPanorama#setPOVメソッドを使います。

// GStreetviewPanorama#setPOVメソッドにGPovを引数として渡す。
panorama.setPov(pointOfView);

setPOVでは不連続的にそちらの方向に視線が切り替わりわすが、突然そっちの方向を向くのではなく滑らかに連続的に視線方向を変化させたい場合はGStreetviewPanorama#panToメソッドを使います。

// GStreetviewPanorama#panToメソッドにGPovを引数として渡す。
panorama.panTo(pointOfView);

また、GStreetviewPanorama#getPOVメソッドで、現在の視線方向をGPovとして取得することができます。

// GStreetviewPanorama#getPovメソッドでGPovを取得。
var pov = panorama.getPOV();


※リファレンスではGPovのpitchの上と下が逆に書かれているようです。↓のようになっていますが、試してみると-90が上、90が下でした。

pitch


The camera pitch in degrees,relative to the street view vehicle. Ranges from 90 degrees (directly upwards) to -90 degrees (directly downwards). (Since 2.104)

http://code.google.com/apis/maps/documentation/reference.html#GPov

現在位置を取得する（initializedイベント）

現在位置を取得する方法は意外と難しいです。GStreetviewPanorama#getLocationメソッドみたいなものがあればいいのですが、そんなメソッドはありません。そこで、GStreetviewPanoramaのinitializedイベントを使うことになります。initializedイベントは、その位置への移動が完了し初期化されたときに呼び出されるイベントです。

initializedイベントを用いると、現在位置の緯度、経度をGLatLngで、その場所のID（panoIdと呼ばれる。すべてのストリートビューの位置に振られている固有のID）を取得することができます。

// initializedイベントのハンドラを作成。
function handleInitialization(location) {
	// ここに処理を書く。
	//locationから、現在位置のGLatLngや、panoIdを取得することができる。
	
	// 例:現在位置の取得
	var latlng = location.latlng;
	
	// 例:panoIdの取得
	var panoId = location.panoId;
}

// initializedイベントを追加。
GEvent.addListener(panorama,"initialized",handleInitialization);


なお、このとき得られるlocationはGStreetviewLocationオブジェクトで、GStreetviewDataは次のような値を持ちます。

GStreetviewLocationクラス
プロパティ 型 解説
latlng GLatLng 緯度、経度による位置。
pov GPov 視線方向。
description String その地点に関する説明。
panoId String その地点を表すID。
(2008-08-11追記)

initializedイベントは、道をたどって移動した場合（followLinkメソッドを含む）にだけ起こるようです。ユーザーが進む道の矢印をクリックして進んだときや、GStreetviewPanorama#followLinkメソッド（↓で説明）によって移動したときには起こりますが、GStreetviewPanoramaオブジェクト生成時（初回）やGStreetviewPanorama#setLocationAndPOVメソッド（↓で説明）で位置を指定したときには、新しい場所が表示されてもinitializedイベントは起こりません。

この仕様は現在見直しが検討されており、将来的にはGStreetviewPanoramaオブジェクト生成時にもinitializedイベントが起こるようになるかもしれません。

This event is fired when the panorama is initialized after moving to a new location. The location is a GStreetviewLocation object. Note: the initialized event is not sent when the panorama is first rendered; this is a known issue and we plan to fix this in a future release. (Since 2.104)

http://code.google.com/apis/maps/documentation/reference.html#GStreetviewPanorama

移動する（setLocationAndPOV, followLink）

緯度、経度で移動先を指定するにはGStreetviewPanorama#setLocationAndPOVメソッドを使います。

// GStreetviewPanorama#setLocationAndPOV
//  第1引数(GLatLng):移動先の緯度、経度
//  第2引数(GPov):視線方向（省略化）
panorama.setLocationAndPOV(new GLatLng(35.003277,135.774991),pointOfView);


また、現在地点から道をたどって移動するにはGStreetviewPanorama#followLinkメソッドを使います。followLinkメソッドの引数はyawだけで、指定されたyaw方向に最も近い道を選んでその道を進みます（現在位置から進める道（移動方向のyawや移動先のpanoId）を得るには、GStreetviewClientとGStreetviewDataを使用）。

// GStreetviewPanorama#followLink
//  第1引数(Number):0〜360で表す移動方向（北:,東:0,南:80,西:70）
panorama.followLink(90);

Googleマップ上でストリートビュー対応の道を青色ハイライト表示する（GStreetviewOverlay）

Googleマップでストリートビューを使うと、ストリートビュー対応範囲が青色にハイライトされて表示されます。この対応範囲の青色ハイライトを行うにはGStreetviewOverlayを使います。単純に、GMap2#addOverlayの引数にGStreetviewOverlayオブジェクトを渡すだけでハイライト表示されます。

// GMap2オブジェクトが変数mapに格納されているとする。
map.addOverlay(new GStreetviewOverlay());

ある地点から進める道を取得する（GStreetviewClient, GStreetviewData）

GStreetviewClientとGStreetviewDataを用いて進める道を取得する方法に関しては後日書く予定。

関連ページ（追記）

(2008-08-09)

他にもストリートビューのAPIの使い方を解説しているエントリーを見つけたので挙げておきます。

日本でも始まったgoogleのストリートビュー。プライバシーがどうたらと騒がしいですが、とりあえずプログラムでいじってみたいと思い、昼から慣れない英語を見て色々いじってました。

Google Map APIを使ったことがない人でもわかるストリートビューの使い方

同期のためにVectorは使わない（VectorとCollections.synchronizedList）

Java コレクションフレームワーク オススメ

よくJavaの解説には、VectorとArrayListの違いはスレッドセーフであるかないかだということが書かれている。そのような解説を読むと、スレッドセーフな可変長配列がほしい場合にはVectorを使えば良いと思ってしまいそうだが、私は同期を目的としてもVectorは使うべきではないと思う。

Collections.synchronizedListメソッドによる同期

Vectorは単にArrayListのスレッドセーフ版ではなく、Java1.0のときに導入されたレガシークラスだ。Java1.2でCollections Frameworkが導入され、Vectorに代えてList（ArrayListやLinkedList）を用いることが推奨されるようになった。スレッドセーフなListを実現したいときには、VectorではなくCollections.synchronizedListメソッドを用いて次のように書くことができる。

// スレッドセーフなArrayListを生成。
List list = Collections.synchronizedList(new ArrayList());

Vectorを使うべきでない理由

公式にVectorよりもCollections.synchronizedListメソッドを用いるべきだと書かれている資料は見つけることができなかった。Javaのリファレンスを見ても、VectorでもCollections.synchronizedListメソッドでも「同期を実現できる」としか書かれていない。


しかし、WEB上の意見を集めてみたところ、「VectorではなくCollections.synchronizedListメソッドを用いるべきだ」という意見は複数見つかったが、逆は見つからなかった。Vectorを使うべきでない理由としては次のようなものがあった。

  • Vectorはレガシークラスなので、後方互換のために残されているだけで基本的に使うべきではない。
  • Collections.synchronizedListメソッドでListをラッピングすることで、明示的に同期化の意思を示すことができ、ソースの可読性が上がる。

もう一つ私が考える理由は次のようなものだ。

  • 内部的にリスト構造で実現されたスレッドセーフなListを作成することができる。

VectorはArrayListのように内部的に配列で実装されているが、Collections.synchronizedListメソッドを用いれば、内部的にリスト構造で実装されているLinkedListのスレッドセーフ版も作ることができる。挿入や削除が繰り返し行われるようなスレッドセーフなListがほしい場合は、

// スレッドセーフなLinkedListを生成。
List list = Collections.synchronizedList(new LinkedList());

とした方がVectorを用いるよりパフォーマンスが上がるだろう。そして、これを使うのであれば、挿入、削除よりも参照を主とするスレッドセーフなListを作成するときには、Vectorを使うよりもCollections.synchronizedList(new ArrayList())を使った方が自然だろう。

Vectorを使うべきでないと書かれていたページ

情報を収集時に見つけたページの一部を挙げておく。

Vectorについては、基本的には下位互換のために用意されているレガシ実装であることから、特に理由がなければ使わない方がよいでしょう。マルチスレッド環境下で利用しなければならない場合でも、同期化ラッパーを使うことをお勧めします。同期化の手順を明示的に踏むことで、同期化しなければならない、というプログラマの意図を、コード中で明らかにしておくことができるからです。

http://www.atmarkit.co.jp/fjava/javatips/136java026.html

Multithreading is not a valid reason to use Vector since you can do:

List myList = java.util.Collections.synchronizedList(new ArrayList());

Supporting legacy is really the only reason to choose Vector.

http://www.velocityreviews.com/forums/t132806-arraylist-vs-vector.html

A java.util.Vector should (speaking from a purist point of view) only be
used if you wish to support VMs prior to 1.2.
The same can be said for java.util.Hashtable.

If you need thread-safety you synchronize your java.util.List using
java.util.Collections.
This is the *nice* way of doing it.

http://www.velocityreviews.com/forums/t132806-arraylist-vs-vector.html

Vector/Hashtable are almost "legacy" classes. They were base classes right back in Java 1.0.2
Java 1.1 introduced the collections framework with the "Collection", "List", "Map" interfaces. The "old" classes Vector and Hashtable were retrofitted to fit in with the collections framework so that existing code wouldn't break.

However basically, ArrayList was a replacement for Vector, and HashMap was a replacement for Hashtable.

I use the newer classes in preference to the older ones.

（中略）

Also using the "synchronized***" methods lets you synchronize any implementation you want to.

http://forums.sun.com/thread.jspa?threadID=5273164&tstart=195

ArrayList は非同期ですが、そのために、
Collections.synchronizedList(new ArrayList());
というコードで、同期化されたリストを
取得可能な方法が提供されていますので、
Vector の存在は必須ではありません。

（中略）

コレクションフレームワークを設計した人にとっては、
Vector は邪魔だし、削除できるものならしたかった
だろうと思います。

http://okwave.jp/qa777956.html

Hashtableも使うべきでない（Collections.synchronizedMapメソッドを使う）

同様の理由で、もちろんHashtableも使うべきではない。Hashtableと同様の機能がほしければ、

// スレッドセーフなHashMapを生成
Map map = Collections.synchronizedMap(new HashMap());

と書けばいいし、ソート済みの特性がほしければTreeMapを用いて

// スレッドセーフなTreeMapを生成
Map map = Collections.synchronizedMap(new TreeMap());

と書くことだってできる。

（余談ですが、HashMapとTreeMapの速度比較について過去に検証を行いましたので、興味のある方はこちらをご覧下さい）

結論: VectorやHashtableは使わない。代わりにCollections.synchronized*メソッドを使う。

結局、VectorやHashtableはレガシークラスなので使わない、同様の機能がほしければ

List list = Collections.synchronizedList(new ArrayList());
Map map = Collections.synchronizedMap(new HashMap());

のように書く。また、Collections.synchronized*メソッドを用いれば、スレッドセーフなLinkedListやTreeMapだって作れる*1。

*1:Collections.synchronizedSetメソッドを用いて、スレッドセーフなHashSetやTreeSetを作成することもできる。

任意の底を持つ対数を計算する方法

PHP Java JavaScript C/C++ Ruby

多くのプログラミング言語では、任意の底を持つ対数を計算するために一工夫が必要だ。

PHP

PHPで任意の底の対数得るのは簡単だ。log関数を用いて次のように書く。第二引数を省略するとネイピア数（自然対数の底）eが底となる。

<?php
// 底が2、真数が10の対数値。
$value = log(10.0, 2.0);
?>

しかし、このように書ける言語は少ない。

Java

JavaではMath.logメソッドもしくはMath.log10メソッドを使う。前者は自然対数（底はネイピア数e）、後者は常用対数（底は10）の値を返す。しかし、任意の底について計算をするようなメソッドは用意されていない。そこで、数学で習った対数の底の変換公式*1を用いて任意の底を持つ対数を計算する。


（対数の底の変換公式）


bは任意の底だ。この式を用いれば、任意の底を持つ対数も、自然対数や常用対数を用いて計算することができる。例えば、底が2で真数が10の対数を自然対数で書き換えると次のようになる。


これをJavaで書くと次のようになる。

// 底が2、真数が10の対数値。
double value = Math.log(10.0) / Math.log(2.0);

JavaScript

JavaScriptでは次のようになる。Javaと同じだ。

// 底が2、真数が10の対数値。
var value = Math.log(10.0) / Math.log(2.0);

C

せっかくなのでCの場合も。

#include <math.h>

...

double value = log(10.0) / log(2.0);

Ruby

Rubyだと。

value = Math.log(10.0) / Math.log(2.0)

結論: 多くの言語では対数の底の変換公式を使う必要がある

こうして見ると、多くの言語では任意の底を持つ対数を計算するためのメソッドや関数が用意されていないようだ*2。その場合は、対数の底の変換公式を用いることで任意の底を持つ対数を計算できる。


（対数の底の変換公式（再掲））

*1:底の変換公式を習うのは高校の数II。

*2:http://magicant.txt-nifty.com/main/2006/08/ln_log_log10.htmlを見る限り、PHPの他に任意を底を持つ対数を計算するためのメソッドや関数が用意されている言語には、DelphiやProlog、Pythonなどがあるようだ。

JavaのNaNがおかしい（というか、Doubleがおかしい）

Java 疑問

doubleはNaN*1を値として取ることができる（その他にも、正の無限大、負の無限大をとることもできる）。これはIEEE 754で決められている。


NaNはNaNと比較しても等しくないという性質を持っている。つまり、

// aはNaNになる。
double a = 0.0 / 0.0;
System.out.println(a == a);

とするとfalseと表示される。これはバグではない。仕様だ。

（上では0.0/0.0でNaNを発生させたが、Javaでは普通Double.NaNを用いる）


しかし、doubleのラッパークラス*2Doubleを用いて

// bはNaNを表すDoubleオブジェクトになる。
Double b = new Double(0.0 / 0.0);
System.out.println(b.equals(b));

とするとtrueとなってしまう。


これはDouble#equalsメソッドの実装ミスではないのだろうか。それとも、NaN同士の比較結果をfalseにしてしまうとComparatorやComparableの実装上の問題*3が生じるので、あえてtrueとしているのだろうか。

追記（2008-08-05）

リファレンスできちんと言及されていた。しっかり確認しないまま書いてしまった。

ほとんどの場合、Double クラスの d1 および d2 という 2 つのインスタンスについて、d1.equals(d2) の値が true になるのは、次の式の値が true になる場合だけです。

d1.doubleValue() == d2.doubleValue()

しかし、例外事項も 2 つあります。

* d1 と d2 の両方が Double.NaN を表し、Double.NaN==Double.NaN の値が false であるにもかかわらず、equals メソッドが true を返す場合
* d1 が +0.0 を表し、d2 が -0.0 を表すか、あるいは d1 が -0.0 を表し、d2 が +0.0 を表す場合で、+0.0==-0.0 の値が true であるにもかかわらず、equal テストの値が false の場合

この定義によって、ハッシュテーブルは正しく動作します。

Double#equals

*1:NaNはNot a Numberの略。非数を表す。例えば、0.0/0.0や√-1の演算結果などがNaNになる

*2:ラッパークラスとは、プリミティブ型であるbyte、short、int、long、float、double、char、boolean、voidを参照型として表したいときに用いる、Byte、Short、Integer、Long、Float、Double、Character、Boolean、Voidのことを指す。

*3:NaNとNaNは等しくないので、compareメソッドはNaN同士を比較したときに0を返してはいけない。しかし、負数を返しても正数を返しても、compareメソッドに与える引数を入れ替えると大小関係が反転してしまう。よって、どのような値を返しても不都合が起こる。

ハッシュは二分木（ツリー）より速い（ハッシュとツリーの速度比較）

C/C++ Java 性能評価 アルゴリズム コレクションフレームワーク オススメ

ハッシュは遅いという意見があるようだが、実装や使い方を誤らなければ、基本的にツリーよりハッシュの方が速い。

（この記事は以前書いた「ハッシュは本当に遅いのか？いや、遅くない（反語）」を簡潔にまとめたものです）


ハッシュとツリーの速度を比較した結果が次のグラフだ（ハッシュはパラメータを適切に設定（後述））。挿入、参照（検索）、削除の合計時間を測定した。（横軸は要素数、縦軸は時間、横軸は対数スケール）
f:id:Kappuccino:20080723132258g:image

「ハッシュは本当に速いのか?」の検証

速いはずのハッシュが二分木にはかないません。ハッシュは速いという常識をくつがえす結果となりました。

http://www.s34.co.jp/cpptechdoc/article/hash/:itle=ハッシュは本当に速いのか?

Googleで「ハッシュ 速い」で検索すると上記のページが一番上に表示される（2008-08-04現在）。しかし、このページに掲載されている検証プログラムには問題がある。


次の部分では、データの挿入、削除をまとめて実行時間を測定している。

long tick = GetTickCount();
for ( i = 0; i < N; ++i )
    c.insert(data[i]);
for ( i = 0; i < N; ++i )
    c.erase(data[i]);
tick = GetTickCount() - tick;

そのため、ハッシュに要素を追加した際の、ハッシュテーブルの拡張にかかる時間がそのまま結果に反映されてしまっている。「テーブルの拡張にかかる時間もハッシュの性能のうち」という意見もありそうだが、それは違う。


ハッシュでは、ハッシュテーブルの初期容量を与えることができる*1。要素数がまったく検討がつかないというような状況でもない限り、ハッシュテーブルの拡張を最小限に抑えるように初期容量を設定すれば良い（冒頭で述べた適切な設定とはテーブルの拡張が起こらないように初期容量を設定すること）。

また、上記のページでは挿入と削除が一緒になって検証されているので、あたかもハッシュのすべての動作が遅いかのような印象を与えられる。しかし、削除や参照ではハッシュテーブルの拡張のような問題は起こらないため高速に動作する。

さらに、挿入と削除を繰り返すようなプログラムでは、一度大きなハッシュテーブルが構築された後は、要素数が際限なく増えることがない限り、以降の挿入ではテーブルの拡張が起こらない。つまり、この場合はプログラム実行初期の挿入は遅いが、それ以降の挿入は速いということになる。

要素が増えるとツリーは遅くなる。ハッシュは遅くならない。

冒頭のグラフを見ると、時間計算量がハッシュはO(1)*2、ツリーはO(log N)*3と、理論通りのきれいな結果となっていることがわかる。

つまり、要素が増えるにしたがってツリーは遅くなり、ハッシュは要素が増えても遅くならない。


検証はJavaのHashSetとTreeSetで行った。C++での結果への反論としてJavaで検証というのは不適切だという声が聞こえてきそうだが、JavaでO(1)を実現できているのに、C++でO(1)が実現できないとは考えにくい。

（検証プログラムや実験環境などの詳細は「ハッシュは本当に遅いのか？いや、遅くない（反語）」を参照）

結論:ハッシュは速い。初期容量と負荷係数を適切に設定する。

以上をまとめると次のとおり。

  • ハッシュは基本的にツリーより速い
  • ハッシュは初期容量を適切に設定しないと、テーブルの拡張によって挿入が遅くなることがある
  • 挿入と削除を繰り返す場合はテーブルの拡張が起こらなくなるので、やがて挿入も速くなる

ハッシュのパフォーマンスが問題になるのは、ハッシュテーブルの容量（バケット数）が大きすぎるときに、全要素への繰り返し参照の速度が低下してしまう*4ことや、負荷係数を大きくしすぎて参照コストが増大してしまう*5ことだ。


結論:ハッシュは速い。ただし、ハッシュを使うときには初期容量と負荷係数を適切に設定することが重要だ。


（余談だが、「ハッシュ 速い」より「ハッシュ 早い」で検索した方が多くのページがヒットするのだが、「早い」は時間的に前であることを表す言葉なので、この場合は「速い」が適切ではないだろうか。）

*1:初期容量や負荷係数の設定の仕方についてはHashMapのリファレンスが参考になる。

*2:O(1)とは、要素数が増えても実行時間が変化しないこと。定数時間とも言われる。

*3:O(log N)とは、要素数が倍になるにしたがって、一定量ずつ実行時間が増えていくこと。対数時間とも言われる。

*4:例えば、テーブルの容量が要素の10倍だと、その10倍のテーブルを走査して要素を取り出さなければならない。

*5:負荷係数を大きくするとハッシュ値の衝突が起こりやすくなる。ハッシュ値が衝突して、一つのハッシュ値にたくさんの要素がぶらさがると参照コストは増大する。

PHPのエスケープやエンコード関数

PHP

HTMLエスケープやURLエンコード、ハッシュ関数など、WEBアプリケーション作成においてよく使うPHPの関数をまとめた。

HTMLエスケープ

HTML中で使われる『&』や『<』、『>』などの記号を、『&amp;』や『&lt;』、『&gt;』などに書き換えるのがHTMLエスケープだ（元に戻すのはHTMLアンエスケープ）。HTMLエスケープを行わなければ、例えば<はタグの開始点とご認識されてしまうかもしれない。また、ユーザーが入力した内容をそのまま表示するようなアプリケーションでは、HTMLエスケープが行われていないと悪意あるHTMLタグやJavaScriptを埋め込まれる危険性がある。


HTMLエスケープ

<?php
htmlspecialchars('you & I > he & she');
// 結果: you &amp; I &gt; he &amp; she
?>


HTMLアンエスケープ

<?php
htmlspecialchars_decode('you &amp; I &gt; he &amp; she');
// 結果: you & I > he & she
?>


"や'のエスケープに関する設定や、より多くの文字をエスケープするhtmlentities()に関しては下記のマニュアルやリンク先を参照。変換テーブルはget_html_translation_table()で取得することができる。

htmlspecialchars()
htmlspecialchars_decode()
htmlentities()
html_entity_decode()
get_html_translation_table()
HTMLエンティティ

URLエンコード

URLエンコードをよく使うのはGETでパラメータを送る場合だ。URLに使える文字は決められているので、それ以外の文字を使う場合は『茶』→『%E8%8C%B6』のようにエンコードしなければならない（元に戻すのはURLデコード）。


URLエンコード

<?php
urlencode('私はMaryです。');
// 結果: %E7%A7%81%E3%81%AFMary%E3%81%A7%E3%81%99%E3%80%82
?>


URLデコード

<?php
urldecode('%E7%A7%81%E3%81%AFMary%E3%81%A7%E3%81%99%E3%80%82');
// 結果: 私はMaryです。
?>


これらの関数のマニュアルは↓。

urlencode()
urldecode()

ハッシュ関数（MD5、SHA-1）

ハッシュは与えられたデータから別のデータへの一方向（つまり、エンコードやエスケープと違い元に戻すことができない）の変換だ。例えば、『神はサイコロを振らない』→『5544aab3533a4dd52850659e54df490316837fdd』のようになる。ハッシュは、「パスワードをDBにそのまま格納するのを避けたい」というようなときによく使われる。DBにはハッシュ値を格納しておき、入力されたパスワードのハッシュ値を計算して比較すれば良い。

よく使われるハッシュのアルゴリズムはMD5とSHA-1だが、MD5は安全性の問題が指摘されているので、より安全なSHA-1を使った方が良い。


MD5（※MD5を使わずにSHA-1を使うべき）

<?php
md5('神はサイコロを振らない');
// 結果: 876bc50991c9adfe738fe1bb62c1c086
?>


SHA-1

<?php
sha1('神はサイコロを振らない');
// 結果: 5544aab3533a4dd52850659e54df490316837fdd
?>


これらの関数のマニュアルは次のリンクを参照。また、ハッシュの衝突耐性についての解説へのリンクも併せて記しておく。

md5()
sha1()
ハッシュの衝突耐性について

SQLのエスケープ

SQLインジェクションを防ぐために、よくaddslashes()やpg_escape_string()などを使う方法が紹介されているが、SQLインジェクションはプリペアードステートメントで対処する方がシンプルで安全だと思う。

DBにアクセスするのも、MySQL関数やPostgreSQL 関数などを使うのではなく、MDB2やPDOを使った方がいいと思う。その方がDBの移行はずっと楽になり、プログラムとしても美しい。

MDB2に関しては後日解説を書く予定。