Как я могу ускорить мой шаблон XSLT «разделяй и властвуй», который заменяет определенные символы в строке?
ОБНОВЛЕНИЕ: Я добавил ответ на этот вопрос , который включает почти все предложения, которые были даны. Исходному шаблону, приведенному в приведенном ниже коде, потребовалось 45605 мс , чтобы закончить вводный документ реального мира (английский текст о программировании сценариев). Измененный шаблон в вики-ответе сообщества уменьшил время выполнения до 605 мс !
Я использую следующий шаблон XSLT для замены нескольких специальных символов в строке их экранированными варианты; он вызывает себя рекурсивно, используя стратегию «разделяй и властвуй», в конечном итоге просматривая каждый отдельный символ в данной строке. Затем он решает, должен ли символ быть напечатан как есть, или необходима какая-либо форма экранирования:
"\""
"@"
"|"
"#"
"\\"
"}"
"&"
"^"
"~"
"/"
"{"
Этот шаблон учитывает большую часть времени выполнения, которое требуется моему сценарию XSLT. Замена вышеупомянутого шаблона escape-text просто
делает время выполнения моего скрипта XSLT с 45 секунд до менее одной секунды на одном из моих документов.
Отсюда мой вопрос: как я могу ускорить мой шаблон escape-текста ? Я' используя xsltproc , и я бы предпочел чистое решение XSLT 1.0. Решения XSLT 2.0 также приветствуются. Тем не менее, внешние библиотеки могут быть бесполезны для этого проекта - я все равно был бы заинтересован в любых решениях, использующих их.
8 ответов
Другой (дополнительной) стратегией было бы досрочное завершение рекурсии, прежде чем длина строки уменьшится до 1, если условие translate ($ s, $ vChars, '') = $ s верно. Это должно обеспечить гораздо более быструю обработку строк, которые вообще не содержат специальных символов, которых, вероятно, большинство из них. Конечно, результаты будут зависеть от того, насколько эффективна реализация translate () в xsltproc.
Вот более улучшенная версия, основанная на ответе @Dimitre:
<xsl:template match="text()" name="escape-text">
<xsl:param name="s" select="."/>
<xsl:param name="len" select="string-length($s)"/>
<xsl:choose>
<xsl:when test="$len > 1">
<xsl:variable name="halflen" select="round($len div 2)"/>
<!-- no "left" and "right" variables necessary! -->
<xsl:call-template name="escape-text">
<xsl:with-param name="s" select="substring($s, 1, $halflen)"/>
</xsl:call-template>
<xsl:call-template name="escape-text">
<xsl:with-param name="s" select="substring($s, $halflen + 1)"/>
</xsl:call-template>
</xsl:when>
<xsl:otherwise>
<xsl:choose>
<xsl:when test="not(contains($vChars, $s))">
<xsl:value-of select="$s"/>
</xsl:when>
<xsl:when test="contains('\"', $s)">
<xsl:value-of select="concat('"\', $s, '"')" />
</xsl:when>
<!-- all other cases can be collapsed, this saves some time -->
<xsl:otherwise>
<xsl:value-of select="concat('"', $s, '"')" />
</xsl:otherwise>
</xsl:choose>
</xsl:otherwise>
</xsl:choose>
</xsl:template>
Должна быть еще немного быстрее, но я не тестировал ее. Во всяком случае короче. ; -)
Очень маленькая поправка улучшила скорость в моих тестах примерно в 17 раз .
Есть дополнительные улучшения, но я думаю, что пока этого хватит ... :)
<xsl:stylesheet version="1.0"
xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
xmlns:my="my:my">
<xsl:output omit-xml-declaration="yes" indent="yes"/>
<xsl:strip-space elements="*"/>
<xsl:variable name="vChars">"@|#\}&^~/{</xsl:variable>
<xsl:template match="node()|@*">
<xsl:copy>
<xsl:apply-templates select="node()|@*"/>
</xsl:copy>
</xsl:template>
<xsl:template match="text()" name="escape-text">
<xsl:param name="s" select="."/>
<xsl:param name="len" select="string-length($s)"/>
<xsl:choose>
<xsl:when test="$len >= 2">
<xsl:variable name="halflen" select="round($len div 2)"/>
<xsl:variable name="left">
<xsl:call-template name="escape-text">
<xsl:with-param name="s" select="substring($s, 1, $halflen)"/>
<xsl:with-param name="len" select="$halflen"/>
</xsl:call-template>
</xsl:variable>
<xsl:variable name="right">
<xsl:call-template name="escape-text">
<xsl:with-param name="s" select="substring($s, $halflen + 1)"/>
<xsl:with-param name="len" select="$halflen"/>
</xsl:call-template>
</xsl:variable>
<xsl:value-of select="concat($left, $right)"/>
</xsl:when>
<xsl:otherwise>
<xsl:choose>
<xsl:when test="not(contains($vChars, $s))">
<xsl:value-of select="$s"/>
</xsl:when>
<xsl:when test="$s = '"'">
<xsl:text>"\""</xsl:text>
</xsl:when>
<xsl:when test="$s = '@'">
<xsl:text>"@"</xsl:text>
</xsl:when>
<xsl:when test="$s = '|'">
<xsl:text>"|"</xsl:text>
</xsl:when>
<xsl:when test="$s = '#'">
<xsl:text>"#"</xsl:text>
</xsl:when>
<xsl:when test="$s = '\'">
<xsl:text>"\\"</xsl:text>
</xsl:when>
<xsl:when test="$s = '}'">
<xsl:text>"}"</xsl:text>
</xsl:when>
<xsl:when test="$s = '&'">
<xsl:text>"&"</xsl:text>
</xsl:when>
<xsl:when test="$s = '^'">
<xsl:text>"^"</xsl:text>
</xsl:when>
<xsl:when test="$s = '~'">
<xsl:text>"~"</xsl:text>
</xsl:when>
<xsl:when test="$s = '/'">
<xsl:text>"/"</xsl:text>
</xsl:when>
<xsl:when test="$s = '{'">
<xsl:text>"{"</xsl:text>
</xsl:when>
</xsl:choose>
</xsl:otherwise>
</xsl:choose>
</xsl:template>
</xsl:stylesheet>
Что бы это ни стоило, вот моя текущая версия шаблона escape-text , которая включает в себя большинство (отличных!) Предложений, которые люди дали в ответ на мой вопрос . Для справки, моя исходная версия в среднем занимала около 45605 мсек в моем образце документа DocBook. После этого время выполнения было уменьшено в несколько этапов:
- Удаление переменных
leftиrightвместе с вызовомconcat ()снизило время выполнения до 13052 мс; эта оптимизация была взята из ответа Томалака . - Перемещение общего регистра (а именно: данный символ не требует специального экранирования) сначала во внутренний элемент
- Досрочное прерывание рекурсии путем первой проверки наличия в данной строке каких-либо специальных символов привело к сокращению времени выполнения до 612 мсек. Эта оптимизация была предложена Майклом .
- Наконец, я не смог удержаться от микрооптимизации после прочтения комментария Димитра в Ответ Томалака : Я заменил
В итоге функция заняла 606 мс вместо 45605 мс. Впечатляющий!
<xsl:variable name="specialLoutChars">"@|#\}&^~/{</xsl:variable>
<xsl:template name="escape-text">
<xsl:param name="s" select="."/>
<xsl:param name="len" select="string-length($s)"/>
<xsl:choose>
<!-- Common case optimization:
no need to recurse if there are no special characters -->
<xsl:when test="translate($s, $specialLoutChars, '') = $s">
<xsl:value-of select="$s"/>
</xsl:when>
<!-- String length greater than 1, use DVC pattern -->
<xsl:when test="$len > 1">
<xsl:variable name="halflen" select="round($len div 2)"/>
<xsl:call-template name="escape-text">
<xsl:with-param name="s" select="substring($s, 1, $halflen)"/>
<xsl:with-param name="len" select="$halflen"/>
</xsl:call-template>
<xsl:call-template name="escape-text">
<xsl:with-param name="s" select="substring($s, $halflen + 1)"/>
<xsl:with-param name="len" select="$len - $halflen"/>
</xsl:call-template>
</xsl:when>
<!-- Special character -->
<xsl:otherwise>
<xsl:text>"</xsl:text>
<!-- Backslash and quot need backslash escape -->
<xsl:if test="$s = '"' or $s = '\'">
<xsl:text>\</xsl:text>
</xsl:if>
<xsl:value-of select="$s"/>
<xsl:text>"</xsl:text>
</xsl:otherwise>
</xsl:choose>
</xsl:template>
Как насчет использования EXSLT? Строковые функции в EXSLT имеют функцию с именем replace. Я думаю, что это то, что поддерживается довольно многими реализациями XSLT.
После того, как @Frerich-Raabe опубликовал вики-ответ сообщества, который объединяет все предложения и обеспечивает (по его данным) ускорение в 76 раз – большие поздравления всем!!!
Я не удержался и не пошел дальше:
<xsl:stylesheet version="1.0"
xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
<xsl:variable name="specialLoutChars">"@|#\}&^~/{</xsl:variable>
<xsl:key name="kTextBySpecChars" match="text()"
use="string-length(translate(., '"@|#\}&^~/', '') = string-length(.))"/>
<xsl:template match="node()|@*">
<xsl:copy>
<xsl:apply-templates select="node()|@*"/>
</xsl:copy>
</xsl:template>
<xsl:template match="text()[key('kTextBySpecChars', 'true')]" name="escape-text">
<xsl:param name="s" select="."/>
<xsl:param name="len" select="string-length($s)"/>
<xsl:choose>
<xsl:when test="$len >= 2">
<xsl:variable name="halflen" select="round($len div 2)"/>
<xsl:call-template name="escape-text">
<xsl:with-param name="s" select="substring($s, 1, $halflen)"/>
<xsl:with-param name="len" select="$halflen"/>
</xsl:call-template>
<xsl:call-template name="escape-text">
<xsl:with-param name="s" select="substring($s, $halflen + 1)"/>
<xsl:with-param name="len" select="$len - $halflen"/>
</xsl:call-template>
</xsl:when>
<xsl:when test="$len = 1">
<xsl:choose>
<!-- Common case: the character at hand needs no escaping at all -->
<xsl:when test="not(contains($specialLoutChars, $s))">
<xsl:value-of select="$s"/>
</xsl:when>
<xsl:when test="$s = '"' or $s = '\'">
<xsl:text>"\</xsl:text>
<xsl:value-of select="$s"/>
<xsl:text>"</xsl:text>
</xsl:when>
<xsl:otherwise>
<xsl:text>"</xsl:text>
<xsl:value-of select="$s"/>
<xsl:text>"</xsl:text>
</xsl:otherwise>
</xsl:choose>
</xsl:when>
</xsl:choose>
</xsl:template>
</xsl:stylesheet>
Это преобразование обеспечивает (по моим данным) дальнейшее ускорение в 1,5 раза. Таким образом, общее ускорение должно быть более чем в 100 раз.
Обновление: Я исправил это, чтобы оно действительно работало; теперь это не ускорение!
На основе ответа @Wilfred...
После того, как я повозился с функцией EXSLT replace(), я решил, что это достаточно интересно, чтобы опубликовать другой ответ, даже если он бесполезен для ОП. Это вполне может быть полезно другим.
Это интересно из-за алгоритма: вместо основного алгоритма, работающего здесь (выполнение бинарного рекурсивного поиска, деление пополам при каждой рекурсии, обрезка всякий раз, когда 2^n-я подстрока не содержит специальных символов, и итерация по выбор специальных символов, когда строка length=1 действительно содержит специальный символ), алгоритм EXSLT Джени Теннисон помещает итерацию по набору поисковых строк во внешний цикл. Поэтому внутри цикла он ищет только одну строку за раз и может использовать substring-before()/substring-after() для разделения строки вместо слепого деления пополам.
[Устарело: Думаю, этого достаточно, чтобы значительно ускорить работу. Мои тесты показывают ускорение 2,94x по сравнению с последним тестом @Dimitre (в среднем 230 мс против 676 мс). ] Я тестировал Saxon 6.5.5 в XML-профилировщике Oxygen. В качестве входных данных я использовал XML-документ размером 7 МБ, который представлял собой в основном один текстовый узел, созданный из веб-страниц о javascript, повторяющихся. Мне кажется, что это представляет задачу, которую ОП пытался оптимизировать. Мне было бы интересно узнать, какие результаты получают другие, с их тестовыми данными и средами.
Зависимости
При этом используется XSLT-реализация замены, основанная на exsl:node-set(). Похоже, что xsltproc поддерживает эту функцию расширения (возможно, ее раннюю версию). Так что это может сработать для вас нестандартно, @Frerich; и для других процессоров, как это было с Saxon.
Однако, если нам нужен 100% чистый XSLT 1.0, я думаю, не составит большого труда модифицировать этот шаблон замены, чтобы он работал без exsl:node-set(), при условии, что 2-й и 3-й параметры передаются как наборы узлов. , а не RTF.
Вот код, который я использовал, который вызывает шаблон замены. Большая часть длины занята подробным способом, которым я создал наборы узлов поиска/замены... которые, вероятно, можно было бы сократить. (Но вы не можете выполнить поиск или заменить узлы атрибуты, так как в настоящее время написан шаблон замены. Вы получите сообщение об ошибке при попытке поместить атрибуты в элемент документа.)
<xsl:stylesheet version="1.0" xmlns:str="http://exslt.org/strings"
xmlns:foo="http://www.foo.net/something" xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
<xsl:import href="lars.replace.template.xsl"/>
<foo:replacements>
<replacement>
<search>"</search>
<replace>"\""</replace>
</replacement>
<replacement>
<search>\</search>
<replace>"\\"</replace>
</replacement>
<replacement>
<search>@</search>
<replace>"["</replace>
</replacement>
<replacement>
<search>|</search>
<replace>"["</replace>
</replacement>
<replacement>
<search>#</search>
<replace>"["</replace>
</replacement>
<replacement>
<search>}</search>
<replace>"}"</replace>
</replacement>
<replacement>
<search>&</search>
<replace>"&"</replace>
</replacement>
<replacement>
<search>^</search>
<replace>"^"</replace>
</replacement>
<replacement>
<search>~</search>
<replace>"~"</replace>
</replacement>
<replacement>
<search>/</search>
<replace>"/"</replace>
</replacement>
<replacement>
<search>{</search>
<replace>"{"</replace>
</replacement>
</foo:replacements>
<xsl:template name="escape-text" match="text()" priority="2">
<xsl:call-template name="str:replace">
<xsl:with-param name="string" select="."/>
<xsl:with-param name="search"
select="document('')/*/foo:replacements/replacement/search/text()"/>
<xsl:with-param name="replace"
select="document('')/*/foo:replacements/replacement/replace/text()"/>
</xsl:call-template>
</xsl:template>
<xsl:template match="node()|@*">
<xsl:copy>
<xsl:apply-templates select="node()|@*"/>
</xsl:copy>
</xsl:template>
</xsl:stylesheet>
Импортированный таблица стилей изначально была этой.
Однако, как отметил @Frerich, это никогда не давало правильного результата! Это должно научить меня не публиковать данные о производительности без проверки правильности!
В отладчике я вижу, где что-то идет не так, но я не знаю, работал ли когда-нибудь шаблон EXSLT или он просто не работает в Saxon 6.5.5... любой вариант был бы неожиданным.
В любом случае, функция str:replace() в EXSLT предназначена для выполнения большего, чем нам нужно, поэтому я изменил ее так, чтобы
- требовать, чтобы входные параметры уже были наборами узлов
- , как следствие, не требуется exsl :node-set()
- не сортировать строки поиска по длине (в этом приложении все они состоят из одного символа)
- не вставлять строку замены между каждой парой символов, когда соответствующая строка поиска пуста
]Вот измененный шаблон замены:
<xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
xmlns:str="http://exslt.org/strings">
<!-- By Lars Huttar
based on implementation of EXSL str:replace() by Jenni Tennison.
http://www.exslt.org/str/functions/replace/str.replace.template.xsl
Modified by Lars not to need exsl:node-set(), not to bother sorting
search strings by length (in our application, all the search strings are of
length 1), and not to put replacements between every other character
when a search string is length zero.
Search and replace parameters must both be nodesets.
-->
<xsl:template name="str:replace">
<xsl:param name="string" select="''" />
<xsl:param name="search" select="/.." />
<xsl:param name="replace" select="/.." />
<xsl:choose>
<xsl:when test="not($string)" />
<xsl:when test="not($search)">
<xsl:value-of select="$string" />
</xsl:when>
<xsl:otherwise>
<xsl:variable name="search1" select="$search[1]" />
<xsl:variable name="replace1" select="$replace[1]" />
<xsl:choose>
<xsl:when test="contains($string, $search1)">
<xsl:call-template name="str:replace">
<xsl:with-param name="string"
select="substring-before($string, $search1)" />
<xsl:with-param name="search"
select="$search[position() > 1]" />
<xsl:with-param name="replace"
select="$replace[position() > 1]" />
</xsl:call-template>
<xsl:value-of select="$replace1" />
<xsl:call-template name="str:replace">
<xsl:with-param name="string"
select="substring-after($string, $search)" />
<xsl:with-param name="search" select="$search" />
<xsl:with-param name="replace" select="$replace" />
</xsl:call-template>
</xsl:when>
<xsl:otherwise>
<xsl:call-template name="str:replace">
<xsl:with-param name="string" select="$string" />
<xsl:with-param name="search"
select="$search[position() > 1]" />
<xsl:with-param name="replace"
select="$replace[position() > 1]" />
</xsl:call-template>
</xsl:otherwise>
</xsl:choose>
</xsl:otherwise>
</xsl:choose>
</xsl:template>
</xsl:stylesheet>
Одним из дополнительных преимуществ этого более простого шаблона является то, что теперь вы можете использовать атрибуты для узлов ваших параметров поиска и замены. Это сделало бы данные
Производительность: С этим переработанным шаблоном работа выполняется примерно за 2,5 с по сравнению с моими 0,68 с для недавних тестов ведущего конкурента, таблицы стилей XSLT 1.0 @Dimitre. Так что это не ускорение. Но опять же, у других результаты тестов сильно отличаются от моих, поэтому я хотел бы услышать, что другие получают с этой таблицей стилей.
Хорошо, добавлю. Хотя это не так интересно, как оптимизация версии XSLT 1.0, вы сказали, что решения XSLT 2.0 приветствуются, так что вот мое.
<xsl:stylesheet version="2.0"
xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
<xsl:template name="escape-text" match="text()" priority="2">
<xsl:variable name="regex1">[@|#}&^~/{]</xsl:variable>
<xsl:variable name="replace1">"$0"</xsl:variable>
<xsl:variable name="regex2">["\\]</xsl:variable>
<xsl:variable name="replace2">"\\$0"</xsl:variable>
<xsl:value-of select='replace(replace(., $regex2, $replace2),
$regex1, $replace1)'/>
</xsl:template>
<xsl:template match="node()|@*">
<xsl:copy>
<xsl:apply-templates select="node()|@*"/>
</xsl:copy>
</xsl:template>
</xsl:stylesheet>
Это просто использует регулярное выражение replace() для замены \ или " на "\" или "\"" соответственно; состоит из другого регулярного выражения replace(), чтобы окружить любой из других экранируемых символов кавычками.
В моих тестах это работает хуже, чем последнее предложение Dimitre XSLT 1.0, более чем в 2 раза. Я хотел бы знать, какие результаты получают другие.)
Почему производительность ниже? Я могу только догадываться, потому что поиск регулярных выражений медленнее, чем поиск фиксированных строк.
Обновление: с использованием строки анализа
Согласно предложению @Alejandro, здесь используется строка анализа:
<xsl:template name="escape-text" match="text()" priority="2">
<xsl:analyze-string select="." regex='([@|#}}&^~/{{])|(["\\])'>
<xsl:matching-substring>
<xsl:choose>
<xsl:when test="regex-group(1)">"<xsl:value-of select="."/>"</xsl:when>
<xsl:otherwise>"\<xsl:value-of select="."/>"</xsl:otherwise>
</xsl:choose>
</xsl:matching-substring>
<xsl:non-matching-substring><xsl:value-of select="."/></xsl:non-matching-substring>
</xsl:analyze-string>
</xsl:template>
Хотя это кажется хорошей идеей, к сожалению, это не дает нам выигрыша в производительности: В моей настройке это постоянно занимает около 14 секунд, по сравнению с 1-1,4 секунды для шаблона replace() выше. Назовем это замедлением в 10-14x. :-( Это наводит меня на мысль, что разбиение и объединение множества больших строк на уровне XSLT намного дороже, чем двойной обход большой строки во встроенной функции.