Каков наиболее эффективный способ замены текста в этой коллекции?

Question

Представьте, что у вас есть коллекция List<String>, которая может содержать десятки тысяч строк.Если некоторые из них имеют формат:

"This is ${0}, he likes ${1},${2} ... ${n}"

Каков наиболее эффективный (с точки зрения производительности) способ преобразования строки, подобной приведенной выше, в:

"This is %1, he likes %2,%3 ... %n"

Обратите внимание, что путь% начинается с 1. Вот мое решение:

import java.util.regex.*;
...
String str = "I am ${0}. He is ${1}";
Pattern pat = Pattern.compile("\\\$\\{(\\d+)\\}");
Matcher mat = pat.matcher(str)
while(mat.find()) {
   str = mat.replaceFirst("%"+(Integer.parseInt(mat.group(1))+1))
   mat = pat.matcher(str);
}
System.out.println(str);

Я надеюсь, что это правильный код Java, я только что написал его сейчас в GroovyConsole.Мне интересны более эффективные решения, так как я думаю, что применение стольких подстановок регулярных выражений для такого количества строк может быть слишком медленным.Код завершения будет работать как код Java, а не как код Groovy, я просто использовал Groovy для быстрого создания прототипов:)

Answer 1

Вот как бы я это сделал:

import java.util.regex.*;

public class Test
{
  static final Pattern PH_Pattern = Pattern.compile("\\$\\{(\\d++)\\}");

  static String changePlaceholders(String orig)
  {
    Matcher m = PH_Pattern.matcher(orig);
    if (m.find())
    {
      StringBuffer sb = new StringBuffer(orig.length());
      do {
        m.appendReplacement(sb, "");
        sb.append("%").append(Integer.parseInt(m.group(1)) + 1);
      } while (m.find());
      m.appendTail(sb);
      return sb.toString();
    }
    return orig;
  }

  public static void main (String[] args) throws Exception
  {
    String s = "I am ${0}. He is ${1}";
    System.out.printf("before: %s%nafter:  %s%n", s, changePlaceholders(s));
  }
}

протестируйте его на ideone.com

appendReplacement() выполняет две основные функции: добавляет любой текст, расположенный между предыдущим соответствием и текущим; и он анализирует строку замены для групповых ссылок и вставляет захваченный текст на их место. Нам не нужна вторая функция, поэтому мы обходим ее, передавая пустую строку замены. Затем мы сами вызываем метод append() StringBuffer's с сгенерированным текстом замены.

В Java 7 этот API будет открыт немного больше, что сделает возможной дальнейшую оптимизацию. Функциональность appendReplacement() будет разбита на отдельные методы, и мы сможем использовать StringBuilders вместо StringBuffers (StringBuilder еще не существовало, когда Pattern / Matcher был введен в JDK 1.4).

Но, вероятно, наиболее эффективной оптимизацией является компиляция шаблона один раз и сохранение его в переменной static final.

Answer 2

Я думаю, что было бы более эффективно использовать appendReplacement, поскольку тогда вы не создаете тонну новых объектов String, и поиск не возобновляется с самого начала каждый раз.

 String str = "I am ${0}. He is ${1}";
 Pattern pat = Pattern.compile("\\$\\{(\\d+)\\}");
 Matcher mat = pat.matcher(str);

 StringBuffer sb = new StringBuffer(str.length());

 while (mat.find()) {
    mat.appendReplacement(sb, "" + Integer.parseInt(mat.group(1)));
 }
 mat.appendTail(sb);

 System.out.println(sb.toString());

Печать:

Мне 0. Он 1

Answer 3

Попробуйте это:

String str = "I am ${0}. He is ${1}";
Pattern pat = Pattern.compile("\\$\\{(\\d+)\\}");
Matcher mat = pat.matcher(string);
StringBuffer output = new StringBuilder(string.length());
while(mat.find()) {
   m.appendReplacement(output, "%"+(Integer.parseInt(mat.group(1))+1));
}
mat.appendTail(output);
System.out.println(output);

(Скопировано в основном из Javadoc, с добавлением трансформации из вопроса.) Я думаю, что это действительно O (N).

Answer 4

Вы должны начинать соответствие с последнего проверенного индекса строки вместо первого индекса на каждом итеративном шаге. Как намекает упоминание в комментарии, ваше решение - O (n ^ 2), где оно должно быть O (n). Чтобы избежать ненужного копирования строк, используйте вместо этого StringBuilder:

StringBuilder str = new StringBuilder("I am ${0}. He is ${1}");
Pattern pat = Pattern.compile("\\\$\\{(\\d+)\\}");
Matcher mat = pat.matcher(str);
int lastIdx = 0;
while (mat.find(lastIdx)) {
    String group = mat.group(1);
    str.replace(mat.start(1), mat.end(1), "%"+(Integer.parseInt(group)+1));
    lastIdx = mat.start(1);
}
System.out.println(str);

Код не тестировался, поэтому могут быть ошибки "за одним".