Spiral group
_________________________________________________________________________________
< Раздел “Язык Java” > <
Раздел “Технологии Java” > < Основная страница >
Поиск
одиночного символа в строке типа String. Java JDK 1.6.
Статья опубликована: 31.07.2006
Последнее обновление: 18.03.2007
Поиск одиночного символа в подстроке зачастую воспринимается как поиск подстроки, состоящей из одного символа в заданной строке. В подобной ситуации не ясно каким из методов можно воспользоваться: indexOf(String s) или indexOf(int ch) ? Например, для поиска символа F можно воспользоваться записью indexOf("F") или indexOf('F').
В ряде статей советуется использование того или иного метода и не приводится ни одного теста. Некоторых программистов настораживает, что в роли аргумента выступает не переменная типа char а переменная типа int, которая может вместить любой код кодовой точки Unicode. И из-за отсутствия представления о кодовых точках Unicode, полная поддержка которых была введена в JDK 1.5, пользуются методом indexOf("F").
Объективный ответ можно получить только путем исследования исходных кодов JDK, которые могут изменяться от версии к версии, а также путем написания одного или нескольких тестов.
Следующая программа демонстрирует время поиска подстроки, состоящей их одиночного символа двумя способами:
— методом indexOf класса String с аргументом типа String;
— методом indexOf класса String с аргументом – символом (кодовая точка Unicode).
Файл SingleSymbolSearch.java
/**
* @author <a href="mailto:zagrebin_v@mail.ru">
Victor Zagrebin </a>.
*/
class SingleSymbolSearch
{
public static void
main(String args[])
{
int
pos = 0;
StringBuffer sb = new StringBuffer("CBABA");
for(int i=0; i<10000000;
i++)
{
sb.append("AAAAAABCADAAB");
}
sb.append("AAAAAAF");
String word = "AAAAAAF";
String str = sb.toString();
System.out.println("Characters number in source string="+str.length());
long start = System.currentTimeMillis();
pos = str.indexOf("F");
long end = System.currentTimeMillis();
System.out.println("indexOf method with String
character."+
" Elapsed
time: " + (end-start)+" msec");
System.out.println("indexOf method with String
character."+
" Found string at
position: "+pos);
start = System.currentTimeMillis();
pos = str.indexOf('F');
end = System.currentTimeMillis();
System.out.println("indexOf method with
character (Unicode code point)."+
" Elapsed
time: " + (end-start)+" msec");
System.out.println("indexOf method with
character (Unicode code point)."+
" Found string at
position: "+pos);
}
}
Компиляция:
javac SingleSymbolSearch.java
Запуск:
java –Xmx1024M SingleSymbolSearch
Для запуска требуется наличие достаточного места в оперативной памяти, если выводится ошибка нехватки памяти, то можно уменьшить в цикле for(int i=0; i<10000000; i++) максимальное значение индекса в несколько раз. В этом цикле создается строка достаточно большого размера для проведения теста.
Результаты вывода программы:
Characters
number in source string=130000012
indexOf
method with String character. Elapsed time: 437 msec
indexOf
method with String character. Found string at position: 130000011
indexOf
method with character (Unicode code point). Elapsed time: 641 msec
indexOf
method with character (Unicode code point). Found string at position: 130000011
В приведенной программе
в качестве аргумента явно задается символ 'F' , который будет трансформирован компилятором в код Unicode (кодовую
точку Unicode).
По результатам теста видно, что при поиске одиночного символа с помощью метода indexOf("F") вместо indexOf('F'), используя в качестве аргумента символ (кодовую точку Unicode), выигрыш по времени может составлять 0% - 20% в зависимости от длины строки и местоположения найденного символа. Средний выигрыш составляет 10%. Причину выигрыша по времени можно найти в исходных кодах класса String для семейства методов indexOf().
Опуская полный код класса String, ниже приводится код тех методов, которые задействуются при выполнении методов indexOf(String s) и indexOf(int ch) .
Для метода indexOf(int ch) :
public int
indexOf(int ch) {
return indexOf(ch, 0);
}
public int
indexOf(int ch, int fromIndex)
{
int
max = offset + count;
char v[] =
value;
if (fromIndex < 0) {
fromIndex = 0;
} else if (fromIndex
>= count) {
// Note: fromIndex
might be near -1>>>1.
return -1;
}
int
i = offset + fromIndex;
if (ch < Character.MIN_SUPPLEMENTARY_CODE_POINT)
{
// handle most cases here (ch is a BMP code point or a
// negative value (invalid code
point))
for (; i < max
; i++) {
if
(v[i] == ch) {
return i - offset;
}
}
return -1;
}
if (ch <= Character.MAX_CODE_POINT)
{
// handle supplementary characters
here
char[]
surrogates = Character.toChars(ch);
for (; i < max; i++) {
if (v[i] == surrogates[0]) {
if
(i + 1 == max) {
break;
}
if
(v[i+1] == surrogates[1]) {
return
i - offset;
}
}
}
}
return -1;
}
Для метода indexOf(String s) :
public int
indexOf(String str) {
return indexOf(str, 0);
}
public int
indexOf(String str, int fromIndex) {
return indexOf(value, offset, count,
str.value,
str.offset, str.count, fromIndex);
}
static int
indexOf(char[] source, int sourceOffset, int sourceCount,
char[]
target, int targetOffset, int targetCount,
int fromIndex) {
if (fromIndex >= sourceCount) {
return (targetCount == 0 ? sourceCount :
-1);
}
if (fromIndex < 0) {
fromIndex = 0;
}
if (targetCount == 0) {
return fromIndex;
}
char
first = target[targetOffset];
int
max = sourceOffset + (sourceCount
- targetCount);
for (int i = sourceOffset
+ fromIndex; i <= max; i++) {
/* Look for first character. */
if
(source[i] != first) {
while (++i <= max
&& source[i] != first);
}
/* Found first character, now look
at the rest of v2 */
if (i <= max) {
int j = i + 1;
int end = j + targetCount -
1;
for (int k = targetOffset + 1; j <
end && source[j] ==
target[k]; j++,
k++);
if (j
== end) {
/* Found whole string. */
return
i - sourceOffset;
}
}
}
return -1;
}
Как видно из этих примеров, основная масса кода выполняется не в самом методе, а в перегруженных методах. Делая предварительный вывод о том, что быстрее тот метод, который имеет меньше объем кода и менее сложный алгоритм, легко допустить серьезную ошибку.
Красным цветом выделены участки кода, которые являются узким местом и на которые приходится наибольшая нагрузка в вычислениях:
Для метода indexOf(int ch) :
for (; i
< max ; i++)
{
if (v[i] == ch)
{
return i - offset;
}
}
Для метода indexOf(String s) :
while (++i
<= max && source[i] != first);
Как видно, для варианта indexOf(int ch) используется цикл for c дополнительной проверкой if, в то время как метод indexOf(String s) обходится одним циклом while c проверкой, вложенной внутри цикла. Вполне очевидно, что приведенные методы рассчитаны на поиск с учетом смещений и для нашего примера несколько избыточны. Выделим и трансформируем необходимый код в отдельный тест.
Файл SingleSymbolSearch2.java
/**
* @author <a href="mailto:zagrebin_v@mail.ru">
Victor Zagrebin </a>.
*/
class SingleSymbolSearch2
{
public static void
main(String args[])
{
StringBuffer sb = new StringBuffer("CBABA");
for(int i=0; i<10000000;
i++)
{
sb.append("AAAAAABCADAAB");
}
sb.append("AAAAAAF");
String word = "AAAAAAF";
char[] s = sb.toString().toCharArray();
System.out.println("Characters number in source string="+s.length);
long start = System.currentTimeMillis();
int
i = 0;
int
pos = 0;
char first = 'F';
int
max = s.length;
while (++i < max && s[i] != first);
pos = i;
long end = System.currentTimeMillis();
System.out.println("indexOf method with String
character."+
"
Elapsed time: " + (end-start)+" msec");
System.out.println("indexOf method with String
character."+
"
Found string at position: "+pos);
start = System.currentTimeMillis();
i=0;
pos = 0;
for (; i < max ; i++)
{
if (s[i] == first)
{
pos =
i;
break;
}
}
end = System.currentTimeMillis();
System.out.println("indexOf method with character
(Unicode code point)."+
" Elapsed
time: " + (end-start)+" msec");
System.out.println("indexOf method with
character (Unicode code point)."+
" Found string at
position: "+pos);
}
}
Компиляция:
javac SingleSymbolSearch.java
Запуск:
java –Xmx1024M SingleSymbolSearch
Для запуска
требуется наличие достаточного места в оперативной памяти, если выводится
ошибка нехватки памяти, то можно уменьшить в строке for(int i=0; i<10000000; i++) максимальное значение индекса
в несколько раз.
Результаты вывода программы:
Characters
number in source string=130000012
indexOf
method with String character. Elapsed time: 407 msec
indexOf
method with String character. Found string at position: 130000011
indexOf
method with character (Unicode code point). Elapsed time: 469 msec
indexOf
method with character (Unicode code point). Found string at position: 130000011
По результатам можно сделать вывод о том, что причина быстродействия метода заключается в использовании компактного цикла с меньшим числом операторов. Поэтому в случае поиска одиночного символа рекомендуется использовать метод indexOf(String s) вместо indexOf(int ch).
Данный вывод распространяется на текущие используемые версии JDK (проверка проводилась для JDK 1.5, 1.6) и для других версий требует тщательной проверки.
Ссылки:
1. Class java.lang.String.
JavaTM 2 Platform
Standard Edition 6.0 API Specification.
2. Source code of java.lang.String class.
3. Fast String.indexOf()
blog.
|
Автор:
|
< Раздел “Язык Java” > < Раздел “Технологии Java” > < Основная страница >
