Перейти к содержанию

Обращение строки

Задача

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

Решение

XSLT 1.0

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
<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 обращение строки выполняется тривиально.

1
2
3
4
5
6
<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» + «c» + «b» + «a»
  5. fedcba (результат)

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

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
<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. Неэффективная реализация с применением хвостовой рекурсии

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
<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. Эффективная (но не идеальная) реализация

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
<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.

Комментарии