Мне нужен быстрый алгоритм замены ключа для Java

Question

Учитывая строку с ключами замены, как я могу наиболее эффективно заменить эти ключи значениями времени выполнения, используя Java ? Мне нужно делать это часто, быстро и на достаточно длинных строках (скажем, в среднем, 1-2 КБ). Форма ключей - мой выбор, так как здесь я также предоставляю шаблоны.

Вот пример (пожалуйста, не зацикливайтесь на том, что это XML; я хочу сделать это, если возможно, дешевле, чем с помощью операций XSL или DOM). Я хотел бы заменить все @[^@]*?@ шаблоны в этом на значения свойств из свойств бина, истинных Property свойств и некоторых других источников. Ключ здесь fast . Есть идеи?

<?xml version="1.0" encoding="utf-8"?>

<envelope version="2.3">

  <delivery_instructions>

    <delivery_channel>
      <channel_type>@CHANNEL_TYPE@</channel_type>
    </delivery_channel>

    <delivery_envelope>
      <chan_delivery_envelope>
    <queue_name>@ADDRESS@</queue_name>
      </chan_delivery_envelope>
    </delivery_envelope>

  </delivery_instructions>

  <composition_instructions>
    <mime_part content_type="application/xml">
      <content><external_uri>@URI@</external_uri></content>
    </mime_part>
  </composition_instructions>

</envelope>

Наивной реализацией является использование String.replaceAll(), но я не могу не думать, что это не идеально. Если мне удастся избежать добавления новых сторонних зависимостей, тем лучше.

Answer 1

Метод appendReplacement в Matcher выглядит как полезный, хотя я не могу ручаться за его скорость.

Вот пример кода из Javadoc:

Pattern p = Pattern.compile("cat");
Matcher m = p.matcher("one cat two cats in the yard");
StringBuffer sb = new StringBuffer();
while (m.find()) {
    m.appendReplacement(sb, "dog");
}
m.appendTail(sb);
System.out.println(sb.toString());

РЕДАКТИРОВАТЬ: Если это так сложно, как вы можете, вы могли бы довольно легко реализовать свой собственный конечный автомат. Вы в значительной степени будете делать то, что уже делает appendReplacement, хотя специализированная реализация может быть быстрее.

Answer 2

преждевременно переходить к написанию своих собственных. Я бы начал с наивного решения по замене, и фактически оценил бы это. Тогда я бы попробовал стороннее шаблонное решение. ТОГДА я бы сделал удар в пользовательской версии потока.

Пока вы не получите несколько точных цифр, как вы можете быть уверены, что стоит потратить усилия на его оптимизацию?

Answer 3

Есть ли в Java форма regexp replace (), где вызывается функция?

Я избалован методом Javascript String.replace () . (В этом отношении вы можете запустить Rhino и использовать Javascript, но почему-то я не думаю, что это будет так же быстро, как чистый вызов Java, даже если бы компилятор / интерпретатор Javascript были эффективными)

edit: неважно, у @mmyers, вероятно, лучший ответ.

беспричинное упущение: (и потому что я хотел посмотреть, смогу ли я сделать это сам:)

Pattern p = Pattern.compile("@([^@]*?)@");
Matcher m = p.matcher(s);
StringBuffer sb = new StringBuffer();
while (m.find()) 
{
    m.appendReplacement(sb,substitutionTable.lookupKey(m.group(1)));
}
m.appendTail(sb);
// replace "substitutionTable.lookupKey" with your routine

Answer 4

это то, что я использую, из проекта Apache Commons http://commons.apache.org/lang/api/org/apache/commons/lang/text/StrSubstitutor.html

Answer 5

Как уже говорили другие, appendReplacement () и appendTail () - инструменты, которые вам нужны, но есть кое-что, на что вы должны обратить внимание Если строка замены содержит какие-либо знаки доллара, метод попытается интерпретировать их как ссылки группы захвата. Если есть какие-либо обратные слэши (которые используются для избежания пения долларов), он либо съест их, либо выдаст исключение.

Если ваша замещающая строка генерируется динамически, вы можете заранее не знать, будет ли она содержать знаки доллара или обратную косую черту. Чтобы предотвратить проблемы, вы можете добавить замену непосредственно в StringBuffer, например так:

Pattern p = Pattern.compile("@([^@]*?)@");
Matcher m = p.matcher(s);
StringBuffer sb = new StringBuffer();
while (m.find()) 
{
    m.appendReplacement("");
    sb.append(substitutionTable.lookupKey(m.group(1)));
}
m.appendTail(sb);

Вы все равно должны вызывать appendReplacement () каждый раз, потому что именно это синхронизирует вас с позицией совпадения. Но этот трюк позволяет избежать бессмысленной обработки, которая может дать вам заметное повышение производительности в качестве бонуса.

Answer 6

Обработка текста всегда будет ограниченной, если вы не измените свою парадигму. Я не знаю, насколько гибок ваш домен, поэтому не уверен, что это применимо, но здесь идет речь:

попробуйте создать индекс, в котором находится ваша текстовая подстановка - это особенно хорошо, если шаблон не часто меняется, потому что он становится частью «компиляции» шаблона, в двоичный объект, который может принимать значение, требуемое для подстановки и стирать всю строку в виде байтового массива. Этот объект может быть кэширован / сохранен, и в следующий раз снова замените его новым значением, чтобы использовать его снова. Т.е. вы экономите на разборе документа каждый раз. (реализация оставлена ​​в качестве упражнения для читателя = D)

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

Answer 7

пожалуйста, не зацикливайтесь на XML; Я хочу сделать это, если это возможно, дешевле, чем использование операций XSL или DOM

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

Какое точное преимущество @ Foo @ имеет перед стандартным & Foo; Синтаксис уже встроен в библиотеки XML, которые поставляются с Java?

Answer 8

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

При желании можно превратить текст в поток. Читайте его как символ, передавая каждый символ в выходную строку / поток, пока не увидите @, затем прочитайте следующий @, выплескивая клавишу, подставляя ключ в вывод: повторяйте до конца потока.

Я знаю, что это обычный старый скот, но, наверное, лучший.

Я предполагаю, что у вас есть разумное предположение о том, что "@" не просто "отображается" независимо от ваших токенов на входе. :)

Answer 9

Rythm - движок Java-шаблонов, выпущенный с новой функцией Режим интерполяции строк , которая позволяет вам делать что-то вроде:

String result = Rythm.render("Hello @who!", "world");

В приведенном выше примере показано, что вы можете передавать аргумент в шаблон по позиции. Ритм также позволяет передавать аргументы по имени:

Map<String, Object> args = new HashMap<String, Object>();
args.put("title", "Mr.");
args.put("name", "John");
String result = Rythm.render("Hello @title @name", args);

Поскольку содержимое вашего шаблона относительно длинное, вы можете поместить его в файл и затем вызвать Rythm.render, используя тот же API:

Map<String, Object> args = new HashMap<String, Object>();
// ... prepare the args
String result = Rythm.render("path/to/my/template.xml", args);

Примечание. Rythm компилирует ваш шаблон в байт-код Java, и это довольно быстро, примерно в 2 раза быстрее, чем String.format

Ссылки

• Проверьте полнофункциональную демонстрацию
• читать краткое введение в Ритм
• загрузить последний пакет или
• вилка это

Answer 10

... Чий прав. Если это шаблон, который нужно запускать так много раз, что скорость имеет значение, найдите индекс своих токенов замещения, чтобы иметь возможность получить к ним прямой доступ без необходимости запускать каждый раз в начале. Абстрагируйте «компиляцию» в объект с хорошими свойствами, они должны обновляться только после изменения шаблона.