Làm thế nào để tránh O (n^2) phức tạp khi nhóm các bản ghi trong XSLT?

Question

Tôi thường xuyên gặp sự cố về hiệu suất khi XSL chuyển đổi một lượng lớn dữ liệu thành HTML. Những thông tin này thường chỉ là một vài bảng rất lớn xấp xỉ hình thức này:

<table> 
    <record> 
    <group>1</group> 
    <data>abc</abc> 
    </record> 
    <record> 
    <group>1</group> 
    <data>def</abc> 
    </record> 
    <record> 
    <group>2</group> 
    <data>ghi</abc> 
    </record> 
</table> 

Trong chuyển đổi, tôi muốn trực quan nhóm các hồ sơ như

+--------------+ 
| Group 1  | 
+--------------+ 
| abc  | 
| def  | 
+--------------+ 
| Group 2  | 
+--------------+ 
| ghi  | 
+--------------+ 

Một thực hiện ngớ ngẩn này được cái này (bộ là từ http://exslt.org việc thực hiện thực tế là một chút khác nhau, đây chỉ là một ví dụ):.

<xsl:for-each select="set:distinct(/table/record/group)"> 
    <xsl:variable name="group" select="."/> 

    <!-- This access needs to be made faster : --> 
    <xsl:for-each select="/table/record[group = $group]"> 
    <!-- Do the table stuff --> 
    </xsl:for-each> 
</xsl:for-each> 

Thật dễ dàng để thấy rằng điều này có xu hướng có O(n^2) phức tạp. Thậm chí tệ hơn, vì có rất nhiều trường trong mỗi bản ghi. Các dữ liệu hoạt động trên có thể đạt đến vài chục MB, số lượng hồ sơ có thể lên đến 5000. Trong trường hợp xấu nhất, mỗi bản ghi có nhóm riêng và 50 trường. Và để làm cho mọi việc còn tồi tệ hơn nhiều, có là có một mức độ nhóm tốt, làm cho này O(n^3)

Bây giờ sẽ có khá một vài lựa chọn:

1. tôi có thể tìm ra một giải pháp Java để bản đồ liên quan đến điều này và cấu trúc dữ liệu lồng nhau. Nhưng tôi muốn cải thiện kỹ năng XSLT của mình, vì vậy đó thực sự là tùy chọn cuối cùng.
2. Tôi có thể không biết gì về một tính năng thoải mái tại Xerces/Xalan/Exslt, có thể xử lý nhóm tốt hơn nhiều
3. tôi có lẽ có thể xây dựng một chỉ số của một số loại cho /table/record/group
4. Bạn có thể chứng minh với tôi rằng <xsl:apply-templates/> cách tiếp cận nhanh hơn rất nhiều trong trường hợp sử dụng này so với cách tiếp cận <xsl:for-each/>.

Bạn nghĩ mức độ phức tạp này có thể giảm như thế nào?

Answer 1

Bạn chỉ có thể sử dụng phương pháp nhóm Muenchian wellknown trong XSLT 1.0 - không cần phải khám phá dữ liệu được sắp xếp và thực hiện các thuật toán phức tạp hơn và chậm hơn:

<xsl:stylesheet version="1.0" 
xmlns:xsl="http://www.w3.org/1999/XSL/Transform"> 
<xsl:output omit-xml-declaration="yes" indent="yes"/> 
<xsl:strip-space elements="*"/> 

<xsl:key name="kGroupByVal" match="group" use="."/> 

<xsl:template match="node()|@*"> 
    <xsl:copy> 
     <xsl:apply-templates select="node()|@*"/> 
    </xsl:copy> 
</xsl:template> 

<xsl:template match= 
    "group 
     [generate-id() 
     = 
     generate-id(key('kGroupByVal', .)[1]) 
     ]"> 
    <group gid="{.}"> 
    <xsl:apply-templates select="key('kGroupByVal', .)/node()"/> 
    </group> 
</xsl:template> 
<xsl:template match="group/text()"/> 
</xsl:stylesheet> 

Khi chuyển đổi này được áp dụng trên văn bản mà bạn cung cấp (đó không phải là ngay cả một tài liệu XML được hình thành đúng !!!) sau khi sửa nó thành một hình thức tốt,

phải mất 80ms cho 3 record các yếu tố.

Với văn bản tương tự có 1000 record yếu tố chuyển đổi kết thúc bằng 136ms.

Với 10000 record yếu tố thời gian thực hiện là 284ms.

Với 100000 record yếu tố thời gian thực hiện là 1667ms.

Độ phức tạp quan sát rõ ràng là tuyến dưới.

Sẽ rất khó (nếu có thể) để tìm giải pháp hiệu quả hơn nhóm Muenchian trong XSLT 1.0.

Answer 2

thuật toán hiện tại của bạn:

for every [group] record 
    for every [data] record 
    // actions 

tôi giả sử rằng nếu bạn thực hiện lặp đi lặp lại đơn giản thông qua tất cả các yếu tố và

for every [record] 
     take [data] 
     take [group] 
     add [data] to [group] 

Đối với đại diện nhóm bạn có thể sử dụng cây hoặc bản đồ.

Như bạn thấy, thuật toán này có độ phức tạp O (n)

Answer 3

Nếu dữ liệu được presorted bởi nhóm (như trong ví dụ của bạn), bạn có thể lặp kỷ lục thiết lập và kiểm tra xem nhóm các bản ghi là khác với nhóm bản ghi trước đó. Nếu nhóm thay đổi, bạn có thể thêm tiêu đề nhóm. Điều này sẽ thực hiện trong O (n) thời gian phức tạp.

Answer 4

Các phương pháp nhóm được đề xuất là xsl: cho mỗi nhóm trong XSLT 2.0 và nhóm Muenchian trong XSLT 1.0. Với bất kỳ bộ vi xử lý nửa nào, cả hai bộ xử lý này sẽ có hiệu suất (n * log (n)).

Hoặc bạn chỉ cần thay thế "/table/record[group = $group]" bằng một cuộc gọi đến hàm key().

Nếu bạn đã sẵn sàng trả tiền cho một bộ xử lý XSLT cấp doanh nghiệp như Saxon-EE, có khả năng những tối ưu hóa này sẽ được thực hiện tự động để bạn không phải lo lắng về chúng.