1

XSLT の次の XPath 式のインデックス アクセスの時間計算量はどれくらいですか?

<xsl:value-of select="User[2]/username"/>
  1. O(ログ(n))
  2. O(1) または
  3. の上）

次のような何千人ものユーザーを含む並べ替えられたxmlファイルがあります。

<Users>
  <User>
    <idPerson>460</idPerson>
    <username>a_aker01</username>
  </User>
  <User>
    <idPerson>677</idPerson>
    <username>a_aker02</username>
  </User>
  <User>
    <idPerson>1844</idPerson>
    <username>a_aker03</username>
  </User>
  <User>
    <idPerson>2373</idPerson>
    <username>a_aker04</username>
  </User>
</Users>

検索を高速化するために、XSLT 2.0 (高速インデックス アクセスが必要) でバイナリ検索関数を作成することを考えています。

<xsl:variable name="targetId" select="2373" />
<xsl:value-of select="User[idPerson=$targetId]/username"/>

私のニーズには遅すぎます。線形検索を実行しますか?

4

3 に答える 3

3

の時間複雑度/Users/User[2]は実装固有です。ほとんどの場合、それは O(n) 線形検索になりますが、理想的な条件下で O(1) で実行できるほどスマートな実装が存在する可能性があります。

xsl:keyただし、バイナリ検索関数を作成する代わりに、単に使用しないのはなぜですか? (これは XSLT 1.0 でも機能します。)

<xsl:stylesheet xmlns:xsl="http://www.w3.org/1999/XSL/Transform" version="2.0">
  <xsl:output method="text"/>

  <xsl:key name="user-for-idPerson" match="/Users/User" use="number(idPerson)"/>

  <xsl:template match="/">
    <xsl:variable name="targetId" select="2373" />
    <xsl:value-of select="key('user-for-idPerson', $targetId)/username"/>
  </xsl:template>

</xsl:stylesheet>
于 2012-12-17T06:14:18.397 に答える
1

特定の XSLT プロセッサの実装に依存しないようにするために、キーを使用することをお勧めします。

<xsl:key name="kUserById" match="User" use="idPerson"/>

User次に、 byにアクセスする必要がある場合は、次のようにしますidPerson。

key('kUserById', $targetId)

ほとんどの XSLT プロセッサは、キーのインデックス作成を効率的に (つまり、ハッシュ テーブルを使用して) 実装します。したがって、idPersonがそれぞれに対して一意である場合、上記の関数をUser使用したアクセス時間は O(1) -- 一定です。key()

あなたの他の質問について：

次の XSLT の XPath 式のインデックス アクセスの時間計算量はどれくらいですか?

<xsl:value-of select="User[2]/username"/>

提供された XML ドキュメントの場合は O(1) である可能性が最も高いですが、子UsersだけUserでなく他の名前の子も含むドキュメントの場合、アクセス時間は O(N) になる可能性があります。Customer最後の 2 人の子の名前はUserです。

検索を高速化するために、XSLT 2.0 (高速インデックス アクセスが必要) でバイナリ検索関数を作成することを考えています。

二分探索アルゴリズムは、検索対象のオブジェクトが配列内にあることを前提としています(配列内では、インデックスによるアクセス時間は O(1) です)。この仮定は、まだ配列データ構造がない XSLT/XPath では間違っています。

一部の XSLT プロセッサ (Saxon など) は、効率的な方法で (ベクトルを使用して) アクセス時間を O(1) にしてシーケンスを実装する場合がありますが、多くのプロセッサはこれを行いません。

したがって、アクセスするには:

 $seq[$mid]

一般に O(N) を取り、そのようなシーケンスに適用されるバイナリ検索アルゴリズムは O(N^2) です。

于 2012-12-17T17:36:16.670 に答える
1

それはすべて実装に依存します。

Saxon-HE は線形検索で User[idPerson=$targetId] を実装し、Saxon-EE はインデックスを作成する可能性があります。

どちらの製品も、User[2] のように子軸の数値フィルタリングに O(n) の時間計算量がありますが、変数 ($User[2]) を使用すると、アクセスに一定の時間がかかります。

于 2012-12-17T10:42:09.063 に答える