Главная » XSLT » Обращение строки

0

Задача

Требуется изменить порядок символов в строке на противоположный.

Решение XSLT 1.0

Приведенный ниже шаблон обращает строку $input неочевидным, но весьма эффективным способом.

<xsl:template name="reverse"> <xsl:param name="input"/>

<xsl:variable name="len" select="string-length($input)"/> <xsl:choose>

<!— Строки длиной меньше 2 обращаются тривиально –> <xsl:when test="$len &lt; 2">

<xsl:value-of select="$input"/> </xsl:when>

<!– Строки длины 2 также обращаются тривиально –> <xsl:when test="$len = 2">

<xsl:value-of select="substring($input,2,1)"/> <xsl:value-of select="substring($input,1,1)"/> </xsl:when> <xsl:otherwise>

<!– Шаблон рекурсивно применяется сначала ко второй, а потом к первой половине входной строки —> <xsl:variable name="mid" select="floor($len div 2)"/> <xsl:call-template name="reverse"> <xsl:with-param name="input"

select="substring($input,$mid+1,$mid+1)"/> </xsl:call-template> <xsl:call-template name="reverse"> <xsl:with-param name="input"

select="substring($input,1,$mid)"/> </xsl:call-template> </xsl:otherwise> </xsl:choose> </xsl:template>

XSLT 2.0

В версии 2.0 обращение строки выполняется тривиально.

<xsl:function name="ckbk:reverse">

<xsl:param name="input" as="xs:string"/> <xsl:sequence select="codepoints-to-string(

reverse(string-to-codepoints($input)))"/>

</xsl:function>

Обсуждение XSLT 1.0

Приведенный алгоритм не самый очевидный, зато эффективный. Он успешно обращает даже очень длинные строки, на которые у других, более понятных, алго­ритмов уходит слишком много времени или дело вообще кончается переполнени­ем стека. Основная идея заключается в том, чтобы переставить две половины строки местами и продолжать рекурсивное применение алгоритма к каждой по­ловине, пока не останутся строки длины 2 или менее, обращение которых триви­ально. Следующий пример иллюстрирует работу алгоритма. На каждом шаге зна­ком + отмечено место расщепления и конкатенации строки.

1.              reverse(«abcdef») (входная строка)

2.              reverse(«def») + reverse(«abc»)

3.              reverse(«ef») + «d» + reverse(«bc») + «a»

4.              «f» + «e» + «d» + «с» + «b» + «a»

5.              fedcba (результат)

Поучительно будет рассмотреть более понятные реализации обращения стро­ки на языке XSLT. Это покажет вам, как следует и как не следует реализовывать рекурсивные решения в других контекстах.

Один из самых худших алгоритмов – тот, что в первый момент приходит в голову. Его идея состоит в том, чтобы переставить местами первый и последний символ, затем второй и предпоследний и продолжать так до тех пор, пока не дойдем до середины строки. Такое решение мог бы предложить программист на языке C, поскольку оно очень эффективно в языке, где можно получить доступ к любому элементу строки для чтения и записи, а итерация встречается чаще рекурсии. Од­нако в XSLT этот алгоритм придется реализовывать рекурсивно, а роскоши мани­пулировать переменными «на месте» вы лишены (см. пример 2.1).

Пример 2.1. Очень плохая реализация reverse

<xsl:template name="reverse"> <xsl:param name="input"/>

<xsl:variable name="len" select="string-length($input)"/> <xsl:choose>

<!— Строки длиной меньше 2 обращаются тривиально —> <xsl:when test="$len &lt; 2">

<xsl:value-of select="$input"/> </xsl:when>

<!– Строки длиной 2 также обращаются тривиально —> <xsl:when test="$len = 2">

<xsl:value-of select="substring($input,2,1)"/> <xsl:value-of select="substring($input,1,1)"/> </xsl:when> <xsl:otherwise>

<!– Конкатенировать last + reverse(middle) + first —> <xsl:value-of select="substring($input,$len,1)"/> <xsl:call-template name="reverse"> <xsl:with-param name="input"

select="substring($input,2,$len – 2)"/> </xsl:call-template>

<xsl:value-of select="substring($input,1,1)"/> </xsl:otherwise> </xsl:choose> </xsl:template>

Основной недостаток этого решения в том, что оно годится лишь для очень коротких строк. Проблема возникает из-за того, что рекурсия здесь не хвостовая (см. врезку «Хвостовая рекурсия»). Многие процессоры XSLT (в частности, Saxon) оптимизированы для выполнения хвостовой рекурсии, поэтому код следу­ет структурировать так, чтобы эта оптимизация стала возможной. В примере 2.2 это решение переделано так, чтобы переместить рекурсию в хвост. Для этого при каждом рекурсивном вызове в начало строки перемещается только последний символ. При таком подходе рекурсию можно оптимизировать.

Пример 2.2. Неэффективная реализация с применением хвостовой ре­курсии

<xsl:template name="reverse"> <xsl:param name="input"/>

<xsl:variable name="len" select="string-length($input)"/> <xsl:choose>

<!— Строки длиной меньше 2 обращаются тривиально —> <xsl:when test="$len &lt; 2">

<xsl:value-of select="$input"/> </xsl:when>

<!— Строки длиной 2 также обращаются тривиально —> <xsl:when test="$len = 2">

<xsl:value-of select="substring($input,2,1)"/> <xsl:value-of select="substring($input,1,1)"/> </xsl:when>

<!— Конкатенировать last + reverse(rest) —> <xsl:otherwise>

<xsl:value-of select="substring($input,$len,1)"/> <xsl:call-template name="reverse"> <xsl:with-param name="input"

select="substring($input,1,$len – 1)"/>

</xsl:call-template> </xsl:otherwise> </xsl:choose>

</xsl:template>

При таком изменении мы избегаем переполнения стека, но для длинных строк алгоритм все равно работает неэффективно. Во-первых, отметим, что на каждом шаге перемещается лишь один символ. Во-вторых, каждый рекурсив­ный вызов должен обрабатывать строку, длина которой лишь на единицу меньше исходной. Для очень длинных строк это может привести к непосиль­ной нагрузке на подсистему управления памятью процессора XSLT. При ре­дактировании этого рецепта Джени Теннисон отметила, что есть еще один спо­соб ввести в решение хвостовую рекурсию – передавать оставшуюся строку (reverse) и $len в качестве параметров шаблона. В общем случае это хорошая стратегия, позволяющая добиться хвостовой рекурсии. Однако здесь она лишь позволяет слегка поправить дело, но не достигает той же эффективности, как вариант, приведенный в решении.

При реализации любого рекурсивного алгоритма следует стремиться струк­турировать его так, чтобы при каждом рекурсивном вызове сложность задачи уменьшалась хотя бы вдвое. Это позволяет быстрее добраться до «дна» рекурсии. Следуя этой рекомендации, мы приходим к реализации шаблона reverse, пока­занной в примере 2.3.

Пример 2.3. Эффективная (но не идеальная) реализация

<xsl:template name="reverse"> <xsl:param name="input"/>

<xsl:variable name="len" select="string-length($input)"/> <xsl:choose>

<xsl:when test="$len &lt; 2">

<xsl:value-of select="$input"/> </xsl:when> <xsl:otherwise>

<xsl:variable name="mid" select="floor($len div 2)"/> <xsl:call-template name="reverse"> <xsl:with-param name="input"

select="substring($input,$mid+1,$mid+1)"/> </xsl:call-template> <xsl:call-template name="reverse">

<xsl:with-param name="input"

select="substring($input,1,$mid)"/> </xsl:call-template> </xsl:otherwise> </xsl:choose> </xsl:template>

Это первое решение, которое я нашел, и оно приемлемо работает даже для длинных строк (1000 символов и более). Преимущество еще и в том, что оно коро­че варианта, приведенного в разделе «Решение». Единственная разница заключа­ется в том, что здесь тривиальными считаются только строки длиной 0 или 1. Чуть более быстрая реализация уменьшает число рекурсивных вызовов вдвое за счет непосредственного обращения также строк длиной 2.

Во всех показанных выше реализациях выполняется одно и то же число кон- катенаций, и я не думаю, что существует способ уменьшить это число, оставаясь в рамках XSLT. Однако, как показывает тестирование на строках длиной 1000, наилучшее решение быстрее наихудшего примерно в 5 раз. Лучшее и следующее за ним решение отличаются по быстродействию только в 1.3 раза.

ХВОСТОВАЯ РЕКУРСИЯ

Рекурсивный вызов называется хвостовым, если возвращенное им значение сразу же возвращается в виде значения вызывающей функции. Слово «хвосто­вой» намекает на то, что рекурсивный вызов находится в конце функции. Важ­ность хвостовой рекурсии обусловлена тем, что ее можно реализовать более эффективно, чем рекурсию общего вида. В общем случае для рекурсивного вы­зова нужно подготовить новый кадр стека, в котором будут храниться локальные переменные и другие необходимые данные. Поэтому, если объем входных дан­ных велик, то стек может быстро исчерпаться. Что же касается хвостовой рекур­сии, то распознающий ее процессор XSLT способен самостоятельно преобра­зовать рекурсию в итерацию.

XSLT 2.0

В XSLT 1.0 манипуляции со строками производятся на уровне подстрок, по­скольку не существует способа опуститься до уровня символов Unicode. В реше­нии для XSLT 2.0 применяются функции string-to-codepoints и codepoints- to-string, которые, вероятно, в большинстве реализации работают быстрее, так как во внутреннем представлении строка – это просто массив целых чисел в коди­ровке Unicode.

Мангано Сэл  XSLT. Сборник рецептов. – М.: ДМК Пресс, СПБ.: БХВ-Петербург, 2008. – 864 с.: ил.

По теме:

  • Комментарии