クラス図
| MAP | PageMixer ドキュメント > 設計ノート > シンボルの比較 |
本節では、
String 比較コストの低減に関して説明します。
本ドキュメントでは、 クラスは全てクラス名のみで表記されています。 完全な名称は以下の通りです。
| 表記 | 完全名 |
|---|---|
| Attribute | jp.ne.dti.lares.foozy.pagemixer.Attribute |
| HTMLSymbolSet | jp.ne.dti.lares.foozy.pagemixer.HTMLSymbolSet |
| Symbol | jp.ne.dti.lares.foozy.pagemixer.Symbol |
| SymbolSet | jp.ne.dti.lares.foozy.pagemixer.SymbolSet |
| Token | jp.ne.dti.lares.foozy.pagemixer.Token |
PageMixer では、
Token や Attribute の名前のといった、
２つの文字列の等価性比較が必要です。
一般的に、
等価性比較には "String#equals(Object)" が多用されていますが、
JDK の String クラスのソースファイルによれば、
比較対照オブジェクトが自分自身と異なる場合、
その処理には以下のような手順が必要となるため、
そのコストは非常に高くつきます。
String であることを
instanceof により確認するObject から String へのダウンキャスト実のところ、
(1) のinstanceof および (2) のダウンキャストは、
コスト的に決してリーズナブルではありません。
備考：
instanceof 比較が実施されたのと同じクラスに対し、
その実施に引き続いてダウンキャストした場合、
単独でのダウンキャストよりは左程コストが高くつかないようです。
続けて実施される（ダウン）キャストの際には、 最適化処理がクラス確認を省略するのでしょう。
(4) における１文字づつの比較における計算量は、
文字列の長さに比例する（O(n)）であるため、
以下のような他のメソッドも、
String#equals(Object) と同様のコストがかかります。
String#equalsIgnoreCase(String)
String#compareTo(String)
String#compareToIgnoreCase(String)
PageMixer は、 可能であれば文字の大小を無視して文字列の透過性を確認すべきですが、 上記のようなケース無視比較メソッドでは、 実行時に小文字化変換をしています。 大量のデータを処理する場合、 それはリーズナブルではありません。
２つの文字列の等価性を素早く確認するための方法の一つに、 参照の比較があります。
しかし、 参照比較によって文字列等価性を確認する実装は、 文字列への２つの参照が異なっていることを検出した時、 何をすれば良いでしょう？
String#equals や同様の機能を利用して、
文字列内容の透過性を確認するのは、
コストが高くつきます。
しかし、
文字列への参照が異なることは、
文字列内容が異なる十分な根拠には成り得ないので、
２つの参照の違いを文字列の違いと結論付けるのは、
誤った判断の原因となります。
参照の違いを文字列の違いとする理由付けを行うには、 全ての文字列が事前に列挙されている必要がありますが、 そのような制約は応用性の面で現実味がありません。
２つの文字列の等価性確認を参照比較によって行うために、
PageMixer では、
String 参照の直接比較を行う代わりに、
以下に示す "Symbol" およびその派生クラスを定義しています。
このクラス設計は、 既知の文字列同士の比較を効率化するだけでなく、 既知／未知の文字列の混在した比較も可能にします。
Symbol は、
他のオブジェクトとの等価性確認のためのメソッドとして、
"isSameAs(Symbol)"
メソッドを抽象メソッドとして定義しています。
"Symbol.Resolved#isSameAs(Symbol)"
は以下のように実装されます。
以下の例では、参照の比較だけで等価性を確認しています。
public boolean isSameAs(Symbol symbol){
return (value_ == symbol.value_);
}
Symbol.Resolved クラスにおける
isSameAs(Symbol)一方で、
"Symbol.Unresolved#isSameAs(Symbol)"
は以下のように実装されます。
以下の例では、効率的ではありませんが、
String#equals(Object) により等価性を確認しています。
public boolean isSameAs(Symbol symbol){
return (value_.equals(symbol.value_));
}
Symbol.Unresolved クラスにおける
isSameAs(Symbol)Symbol.Resolved は既知の文字列に対して、
Symbol.Unresolved は未知の文字列に対して使用されます。
事前に知られている文字列に関しては、
SymbolSet#add(String) により
Symbol.Resolved インスタンスが
SymbolSet に対して格納されていると仮定します。
SymbolSet#lookup(String) に既知の文字列を指定した場合、
Symbol として
Symbol.Resolved が、
未知の文字列を指定した場合、
Symbol として
Symbol.Unresolved が取得できます。
既知の文字列同士の比較は、
Symbol.Resolved の
isSameAs(Symbol) により行われ、
結果は文字列（への参照）の等価性に応じたものになります。
一方で、
既知の文字列と未知の文字列の比較は、
（Symbol.Resolved の場合は）
String への参照が異なり、
（Symbol.Unresolved での
String#equals(Object) の場合は）
String の内容が異なることから、
確実に失敗するでしょう。
更に、
未知の文字列同士の比較は
Symbol.Unresolved によって行われ、
結果は文字列内容の等価性に応じたものになります。
| "this" | 引数 | |
|---|---|---|
| 既知 | 未知 | |
| 既知 | 参照比較 | 参照比較（→失敗） |
| 未知 | String#equals(Object)（→失敗） |
String#equals(Object) |
文字の大小を無視した比較を行いたい場合には、
（SymbolSet#lookup(String) の際に）
大文字か小文字、
どちらか一方に決めた方に変換した文字列で照会する必要があります。
Symbol の照会は処理の実行段階ではなく、
事前の準備段階でのみ必要なので、
ケース変換処理コストが高くつくとしても、
左程深刻なものになるとは思われません。
PageMixer は、
よく知られた HTML のタグおよび属性の名前に対応する
Symbol の取得の簡便性の為に、
SymbolSet 派生クラスの
"HTMLSymbolSet" を提供しています。
例えば：
// 対応する名前
Symbol a = HTMLSymbolSet.SET.A; // "A"
Symbol html = HTMLSymbolSet.SET.HTML; // "HTML"
Symbol img = HTMLSymbolSet.SET.IMG; // "IMG"
Symbol color = HTMLSymbolSet.SET.COLOR; // "COLOR"
Symbol equiv = HTMLSymbolSet.SET.HTTP_EQUIV; // "HTTP-EQUIV"
Symbol の取得| MAP | PageMixer ドキュメント > 設計ノート > シンボルの比較 |