XSLT中使用的XPath表達式中元素的索引訪問的時間複雜度是多少？

XSLT中以下XPath表達式的索引訪問的時間複雜度是多少？XSLT中使用的XPath表達式中元素的索引訪問的時間複雜度是多少？

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

O（日誌（N））
O（1）或
爲O（n）

我有一個分類 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"/>

是我的需要過於緩慢。它執行線性搜索嗎？

來源

2012-12-17 Ivo

爲什麼不使用'xsl：key'？ –

/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-17 06:14:18

感謝您的回覆。我計劃在完成其他任務後進行優化，所以我還沒有時間來測試它。在我的情況下，xsl：key查找的複雜性是什麼？我可以選擇SaxonHE9和xsltproc。 – Ivo

'xsl：key'創建一個索引，所以O（1）。這不是純粹的優化：它大大簡化和抽象代碼，並可用於在XSLT 1.0中進行分組。 –

當我問這個問題時，我不認爲它是相關的，但是我將用戶保存在一個變量中，因爲它們存儲在與輸入不同的助手文檔中。根據我的測試和研究，在'xsl：key'的定義中不可能使用這個變量，或者我有錯嗎？我正在考慮將用戶輔助文件的內容包含到我的實際輸入文件中，以便能夠使用'xsl：key'。 – Ivo

這一切都取決於實施。 Saxon-HE將通過線性搜索實現User [idPerson = $ targetId]，Saxon-EE可能會構建一個索引。

這兩種產品都有時間複雜度O（n），用於像User [2]，中那樣對子軸進行數字濾波，但如果使用變量（$ User [2]），訪問將需要一定的時間。

來源

2012-12-17 10:42:09

感謝您的回答。如果我理解正確，那麼將所有用戶存儲在一個變量中（）將保證我在$ users [2]上有O（1）訪問權限（或$ users [4000]）和SaxonHE9？如果我編寫二進制搜索函數，我打算僅將它用於此特定用戶文件，並且我希望能夠在O（log（n））中進行搜索。 – Ivo

是的，這是正確的（一般來說：只有當你看到完整的代碼時，你才能真正知道優化器做了什麼）。 –

爲了不依賴於特定的XSLT處理器的實現，我建議的關鍵應使用：

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

然後，當你需要一個User通過idPerson訪問，做只是這：

key('kUserById', $targetId)

大多數XSLT處理器高效地實現關鍵索引（即使用一個哈希表），因此，如果idPerson對於每個User都是唯一的，使用如上所示的key()函數進行訪問的時間爲O（1） - 常量。

關於你提到的其他問題：

什麼是在XSLT以下 XPath表達式的索引訪問的時間複雜度？
<xsl:value-of select="User[2]/username"/> 

因爲這將是最有可能的O（1），但是，對於一個文檔，其中Users不僅User兒童所提供的XML文檔，但與其他名孩子也一樣，訪問時間可以是O（ N） - 假設有1000名兒童名爲Customer，最後兩名兒童名爲User。

我想在XSLT 2.0 寫一個二進制搜索功能（需要快速索引訪問），以獲得更快的搜索

二進制搜索算法假設要搜索的對象是一種array（並且在一個數組中，索引的訪問時間爲O（1））。這種假設對於XSLT/XPath來說是錯誤的，其中仍然沒有數組結構。

某些XSLT處理器（如Saxon）可能以有效的方式（使用向量）實現序列，並有時間訪問O（1），但其中很多不會執行此操作。

因此，爲了訪問：

$seq[$mid]

通常花費O（N），和施加在這樣的序列的二進制搜索算法是O（N^2）。

來源

2012-12-17 17:36:16

感謝您的一般和具體的案例解釋。我不介意堅持一個特定的xslt處理器，我的xml文件是根據'idPerson'排序的，不會改變。我想知道是否給這些先決條件一個真正的二進制搜索將是可能的。在我看來，它是（用SaxonHE9）。糾正我，如果我錯了。 – Ivo

@Ivo，Dr.邁克爾凱是權威人士。根據我的經驗，撒克遜沒有將所有序列作爲向量來實現 - 這意味着對於某些序列，BS會很快，但對於某些序列來說，它可能非常緩慢。如果生成一個基於向量的序列有一個確定的方法，那麼我會使用BS，否則我不確信它的實用性。無論如何，如果可能的話，爲什麼不堅持使用鑰匙？或者，如果您可以使用XSLT 3.0，則可以使用地圖數據結構以便通過其值高效地搜索密鑰。 –

'在這樣的序列上應用的二進制搜索算法是O（N^2）' 只是爲了記錄，是不是O（n * log（n））？ O（log（n））查找和O（n）每次查找的成本（所有最壞情況）。我只是無法弄清楚爲什麼O（n²）。 – Ivo

XSLT中使用的XPath表達式中元素的索引訪問的時間複雜度是多少？

回答

相關問題