Репликация строки.разделение с помощью StringTokenizer
https://stackoverflow.com/questions/986543
-
13-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Воодушевленный это, и тот факт, что у меня есть миллиарды строк для синтаксического анализа, я попытался изменить свой код, чтобы принять StringTokenizer вместо того , чтобы Строка[]
Единственное, что осталось между мной и получением этого восхитительного повышения производительности x2, - это тот факт, что когда вы делаете
"dog,,cat".split(",")
//output: ["dog","","cat"]
StringTokenizer("dog,,cat")
// nextToken() = "dog"
// nextToken() = "cat"
Как я могу добиться аналогичных результатов с помощью StringTokenizer?Есть ли более быстрые способы сделать это?
Решение
Вы на самом деле токенизируете только запятые?Если да, то я бы написал свой собственный токенизатор - он вполне может оказаться даже более эффективным, чем StringTokenizer более общего назначения, который может искать несколько токенов, и вы можете заставить его вести себя так, как вам хочется.Для такого простого варианта использования это может быть простая реализация.
Если бы это было полезно, вы могли бы даже реализовать Iterable<String> и получите расширенную поддержку цикла со строгой типизацией вместо Enumeration поддержка, оказанная StringTokenizer.Дайте мне знать, если вам нужна помощь в кодировании такого зверя — это действительно не должно быть слишком сложно.
Кроме того, я бы попробовал провести тесты производительности на ваших реальных данных, прежде чем отходить слишком далеко от существующего решения.Вы хоть представляете, сколько времени занимает ваше выполнение? на самом деле провел в String.split?Я знаю, что вам нужно проанализировать много строк, но если вы впоследствии сделаете с ними что-то важное, я ожидаю, что это будет гораздо более важно, чем разделение.
Другие советы
После того, как повозился с StringTokenizer класс, я не смог найти способ удовлетворить требования для возврата ["dog", "", "cat"].
Кроме того, StringTokenizer класс оставлен только по соображениям совместимости и использования String.split находится в окружении.Из спецификации API для StringTokenizer:
StringTokenizerявляется устаревшим классом который сохранен по соображениям совместимости , хотя его использование не рекомендуется в новом коде. Рекомендуется всем, кто ищет эту функциональность, использоватьsplitспособ полученияStringили тотjava.util.regexвместо этого - пакет.
Поскольку проблема заключается в предположительно низкой производительности String.split метод, нам нужно найти альтернативу.
Примечание:Я говорю "предположительно низкая производительность", потому что трудно определить, что каждый вариант использования приведет к StringTokenizer превосходство над String.split способ.Более того, во многих случаях, если токенизация строк действительно не является узким местом приложения, определяемым правильным профилированием, я чувствую, что это в конечном итоге приведет к преждевременной оптимизации, если вообще что-либо произойдет.Я бы склонен был сказать, напишите осмысленный и простой для понимания код, прежде чем приступать к оптимизации.
Теперь, исходя из текущих требований, вероятно, запустить наш собственный токенизатор было бы не так уж сложно.
Запустим наш собственный токензер!
Ниже приведен простой токенизатор, который я написал.Я должен отметить, что нет оптимизации скорости и нет проверок на ошибки, чтобы предотвратить переход за конец строки - это быстрая и грязная реализация:
class MyTokenizer implements Iterable<String>, Iterator<String> {
String delim = ",";
String s;
int curIndex = 0;
int nextIndex = 0;
boolean nextIsLastToken = false;
public MyTokenizer(String s, String delim) {
this.s = s;
this.delim = delim;
}
public Iterator<String> iterator() {
return this;
}
public boolean hasNext() {
nextIndex = s.indexOf(delim, curIndex);
if (nextIsLastToken)
return false;
if (nextIndex == -1)
nextIsLastToken = true;
return true;
}
public String next() {
if (nextIndex == -1)
nextIndex = s.length();
String token = s.substring(curIndex, nextIndex);
curIndex = nextIndex + 1;
return token;
}
public void remove() {
throw new UnsupportedOperationException();
}
}
Тот самый MyTokenizer потребуется некоторое String для токенизации и String в качестве разделителя и используйте String.indexOf способ выполнения поиска разделителей.Токены производятся String.substring способ.
Я бы заподозрил, что можно было бы добиться некоторых улучшений производительности, поработав со строкой в char[] уровне, а не на String Уровень.Но я оставлю это в качестве упражнения для читателя.
Класс также реализует Iterable и Iterator для того, чтобы воспользоваться преимуществами for-each конструкция цикла, которая была введена в Java 5. StringTokenizer является Enumerator, и не поддерживает for-each сконструировать.
Это хоть немного быстрее?
Чтобы выяснить, работает ли это быстрее, я написал программу для сравнения скоростей следующими четырьмя способами:
- Использование
StringTokenizer. - Использование нового
MyTokenizer. - Использование
String.split. - Использование предварительно скомпилированного регулярного выражения с помощью
Pattern.compile.
В четырех методах строка "dog,,cat" был разделен на жетоны.Несмотря на то, что StringTokenizer включен в сравнение, следует отметить, что он не вернет желаемый результат ["dog", "", "cat].
Токенизация была повторена в общей сложности 1 миллион раз, чтобы у вас было достаточно времени, чтобы заметить разницу в методах.
Код, используемый для простого бенчмарка, был следующим:
long st = System.currentTimeMillis();
for (int i = 0; i < 1e6; i++) {
StringTokenizer t = new StringTokenizer("dog,,cat", ",");
while (t.hasMoreTokens()) {
t.nextToken();
}
}
System.out.println(System.currentTimeMillis() - st);
st = System.currentTimeMillis();
for (int i = 0; i < 1e6; i++) {
MyTokenizer mt = new MyTokenizer("dog,,cat", ",");
for (String t : mt) {
}
}
System.out.println(System.currentTimeMillis() - st);
st = System.currentTimeMillis();
for (int i = 0; i < 1e6; i++) {
String[] tokens = "dog,,cat".split(",");
for (String t : tokens) {
}
}
System.out.println(System.currentTimeMillis() - st);
st = System.currentTimeMillis();
Pattern p = Pattern.compile(",");
for (int i = 0; i < 1e6; i++) {
String[] tokens = p.split("dog,,cat");
for (String t : tokens) {
}
}
System.out.println(System.currentTimeMillis() - st);
Результаты
Тесты были запущены с использованием Java SE 6 (сборка 1.6.0_12-b04), и результаты были следующими:
Run 1 Run 2 Run 3 Run 4 Run 5
----- ----- ----- ----- -----
StringTokenizer 172 188 187 172 172
MyTokenizer 234 234 235 234 235
String.split 1172 1156 1171 1172 1156
Pattern.compile 906 891 891 907 906
Итак, как видно из ограниченного тестирования и всего пяти запусков, StringTokenizer на самом деле получилось быстрее всех, но MyTokenizer пришел как близкий 2-й.Затем, String.split было самым медленным, и предварительно скомпилированное регулярное выражение было немного быстрее, чем split способ.
Как и в случае с любым небольшим эталоном, он, вероятно, не очень репрезентативен для реальных условий, поэтому результаты следует оценивать с крупинкой (или горкой) соли.
Примечание:Проведя несколько быстрых тестов, Scanner оказался примерно в четыре раза медленнее, чем String.split.Следовательно, не используйте Scanner.
(Я оставляю этот пост, чтобы отметить тот факт, что Scanner в данном случае — плохая идея.(Читайте как:не минусуйте меня за предложение Сканера, пожалуйста...))
Предполагая, что вы используете Java 1.5 или выше, попробуйте Сканер, который реализует Iterator<String>, как это происходит:
Scanner sc = new Scanner("dog,,cat");
sc.useDelimiter(",");
while (sc.hasNext()) {
System.out.println(sc.next());
}
дает:
dog
cat
В зависимости от того, какие строки вам нужно токенизировать, вы можете написать свой собственный разделитель, например, на основе String.indexOf().Вы также можете создать многоядерное решение для дальнейшего повышения производительности, поскольку токенизация строк не зависит друг от друга.Работайте над партиями, скажем, по 100 строк на ядро.Выполните String.split() или что-то еще.
Вместо StringTokenizer вы можете попробовать класс StrTokenizer из Apache Commons Lang, который я цитирую:
Этот класс может разбить строку на множество меньших строк.Он призван выполнять работу, аналогичную StringTokenizer, однако предлагает гораздо больше контроля и гибкости, включая реализацию интерфейса ListIterator.
Пустые токены могут быть удалены или возвращены как нулевые.
Думаю, это то, что вам нужно?
Вы могли бы сделать что-то подобное.Это не идеально, но может сработать для вас.
public static List<String> find(String test, char c) {
List<String> list = new Vector<String>();
start;
int i=0;
while (i<=test.length()) {
int start = i;
while (i<test.length() && test.charAt(i)!=c) {
i++;
}
list.add(test.substring(start, i));
i++;
}
return list;
}
Если возможно, вы можете опустить элемент List и напрямую что-то сделать с подстрокой:
public static void split(String test, char c) {
int i=0;
while (i<=test.length()) {
int start = i;
while (i<test.length() && test.charAt(i)!=c) {
i++;
}
String s = test.substring(start,i);
// do something with the string here
i++;
}
}
В моей системе последний метод работает быстрее, чем решение StringTokenizer, но вы можете проверить, как оно работает для вас.(Конечно, вы могли бы сделать этот метод немного короче, опустив {} во втором просмотре while, и, конечно, вы могли бы использовать цикл for вместо внешнего цикла while и включить в него последний i++, но я этого не сделал. Я не делаю этого здесь, потому что считаю это плохим стилем.
Ну, самое быстрое, что вы могли бы сделать, это вручную пройти по строке, например.
List<String> split(String s) {
List<String> out= new ArrayList<String>();
int idx = 0;
int next = 0;
while ( (next = s.indexOf( ',', idx )) > -1 ) {
out.add( s.substring( idx, next ) );
idx = next + 1;
}
if ( idx < s.length() ) {
out.add( s.substring( idx ) );
}
return out;
}
Этот (неформальный тест) выглядит примерно в два раза быстрее, чем сплит.Однако выполнять итерацию таким способом немного опасно, например, он будет прерываться на экранированных запятых, и если в какой-то момент вам придется иметь с этим дело (потому что в вашем списке из миллиарда строк есть 3 экранированные запятые), к тому времени, как вы Если вы учтете это, вы, вероятно, потеряете часть преимущества в скорости.
В конечном счете, это, вероятно, не стоит беспокойства.
Я бы порекомендовал Гуаву от Google. Splitter.
Я сравнил это с куберд протестировал и получил следующие результаты:
Стрингтокенайзер 104
Google Гуава Сплиттер 142
String.split 446
регулярное выражение 299
Если ваш ввод структурирован, вы можете взглянуть на компилятор JavaCC.Он генерирует класс Java, читающий ваш ввод.Это будет выглядеть так:
TOKEN { <CAT: "cat"> , <DOG:"gog"> }
input: (cat() | dog())*
cat: <CAT>
{
animals.add(new Animal("Cat"));
}
dog: <DOG>
{
animals.add(new Animal("Dog"));
}
