Home of: [工房 "藤車"] > [SourceForge.net における 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 では、 TokenAttribute の名前のといった、 2つの文字列の等価性比較が必要です。

一般的に、 等価性比較には "String#equals(Object)" が多用されていますが、 JDK の String クラスのソースファイルによれば、 比較対照オブジェクトが自分自身と異なる場合、 その処理には以下のような手順が必要となるため、 そのコストは非常に高くつきます。

  1. 指定されたオブジェクトが String であることを instanceof により確認する
  2. Object から String へのダウンキャスト
  3. 文字列長の比較
  4. 1文字づつの比較

実のところ、 (1) のinstanceof および (2) のダウンキャストは、 コスト的に決してリーズナブルではありません。

備考: instanceof 比較が実施されたのと同じクラスに対し、 その実施に引き続いてダウンキャストした場合、 単独でのダウンキャストよりは左程コストが高くつかないようです。

続けて実施される(ダウン)キャストの際には、 最適化処理がクラス確認を省略するのでしょう。

(4) における1文字づつの比較における計算量は、 文字列の長さに比例する(O(n))であるため、 以下のような他のメソッドも、 String#equals(Object) と同様のコストがかかります。

PageMixer は、 可能であれば文字の大小を無視して文字列の透過性を確認すべきですが、 上記のようなケース無視比較メソッドでは、 実行時に小文字化変換をしています。 大量のデータを処理する場合、 それはリーズナブルではありません。

参照の比較

2つの文字列の等価性を素早く確認するための方法の一つに、 参照の比較があります。

しかし、 参照比較によって文字列等価性を確認する実装は、 文字列への2つの参照が異なっていることを検出した時、 何をすれば良いでしょう?

String#equals や同様の機能を利用して、 文字列内容の透過性を確認するのは、 コストが高くつきます。 しかし、 文字列への参照が異なることは、 文字列内容が異なる十分な根拠には成り得ないので、 2つの参照の違いを文字列の違いと結論付けるのは、 誤った判断の原因となります。

参照の違いを文字列の違いとする理由付けを行うには、 全ての文字列が事前に列挙されている必要がありますが、 そのような制約は応用性の面で現実味がありません。

PageMixer における判断

2つの文字列の等価性確認を参照比較によって行うために、 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.ResolvedisSameAs(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"

よく知られた HTML 名称に対応する Symbol の取得