Spiral, Пошук одиночного символу в рядку типу String
Spiralgroup
Пошук одиночного символу у рядку типуString.JavaJDK1.6.
Пошук одиночного символу в підрядку часто сприймається як пошук підрядка, що складається з одного символу в заданому рядку. У подібній ситуації не ясно яким із методів можна скористатися: 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).
public static void main(String args [])
StringBuffer sb = New StringBuffer ("CBABA");
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 withString character."+
" Elapsed time: " + (end-start)+" msec ");
System.out.println ( "indexOf method with String character."+
"Found string at position: "+pos);
pos=str.indexOf('F');
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);
java – Xmx 1024 M SingleSymbolSearch
Для запуску потрібна наявність достатнього місця в оперативній пам'яті, якщо виводиться помилка нестачі пам'яті, можна зменшити в циклі for ( int i =0; i
Результати виведення програми:
Characters number in source string=130000012
indexOf метод з String character. Elapsed time: 437 msec
indexOf метод з String character. Підписатися на сторінці: 130000011
indexOf метод з характером (Unicode code point). Elapsed time: 641 msec
indexOf метод з характером (Unicode code point). Підписатися на сторінці : 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 )
повернути indexOf (ch, 0);
public int indexOf ( int ch , int fromIndex )
int max = зсув + кількість;
> інакше, якщо ( fromIndex >= кількість)
// Примітка: fromIndex може бути близьким до -1>>>1.
int i = offset + fromIndex ;
// тут обробляємо більшість випадків ( ch — код BMP або a
// негативне значення (недійсний код))
return i - зсув;
// обробляти тут додаткові символи
char[ ] сурогати = Character.toChars ( ch );
якщо (v[ i ] == сурогати [0])
якщо (v[i+1] == сурогати[1])
return i - зсув;
Для методу indexOf (String s):
public int indexOf (String str )
повернути indexOf ( str , 0);
public int indexOf (String str , int fromIndex )
повертає indexOf (значення, зсув, кількість,
str.value, str.offset, str.count, fromIndex);
static int indexOf (char[] source, int sourceOffset, int sourceCount,
char[] target, int targetOffset, int targetCount,
if ( fromIndex >= sourceCount )
return ( targetCount == 0 ? sourceCount : -1);
якщо ( targetCount == 0)
char first = target [ targetOffset ];
int max = sourceOffset + ( sourceCount - targetCount );
for ( int i = sourceOffset + fromIndex ; i
/* Шукайте перший символ. */
якщо (джерело[ i ] != перший)
/* Знайдено перший символ, тепер подивіться на решту v2 */
int end = j + targetCount - 1;
for ( int k = targetOffset + 1; j
/* Знайдено весь рядок. */
return i - sourceOffset ;
Як видно з цихНаприклад, переважна більшість коду виконується над самому методі, а перевантажених методах. Роблячи попередній висновок про те, що швидше той метод, який має менше обсягу коду і менш складний алгоритм, легко припуститися серйозної помилки.
Червоним кольором виділені ділянки коду, які є вузьким місцем та на які припадає найбільше навантаження у обчисленнях:
Для методу indexOf(int ch):
return i - offset;
Для методу indexOf (String s):
Як видно, для варіанта indexOf (int ch) використовується цикл for c додатковою перевіркою if, у той час як метод indexOf (String s) обходиться одним циклом while c перевіркою, вкладеною всередині циклу. Цілком очевидно, що наведені методи розраховані на пошук з урахуванням зсувів і нашого прикладу дещо надмірні. Виділимо та трансформуємо необхідний код в окремий тест.
Файл SingleSymbolSearch 2. java
public static void main(String args [])
StringBuffer sb = New StringBuffer ("CBABA");
String word = "AAAAAAF";
char[] s = sb.toString(). до CharArray ();
System.out.println ( "Characters number in source string="+ s.length );
long start = System.currentTimeMillis();
int max = s.length;
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);
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);
java – Xmx 1024 M SingleSymbolSearch
Для запуску потрібна наявність достатнього місця в оперативній пам'яті, якщо виводиться помилка нестачі пам'яті, можна зменшити в рядку for ( int i =0; i
Результати виведення програми:
Characters number in source string=130000012
indexOf метод з String character. Elapsed time: 407 msec
indexOf метод з String character. Підписатися на сторінці: 130000011
indexOf метод з характером (Unicode code point). Elapsed time: 469 msec
indexOf метод з характером (Unicode code point). Підписатися на сторінці : 130000011
За результатами можна дійти невтішного висновку у тому, що причина швидкодії методу полягає у використанні компактного циклу з меншим числом операторів. Тому у разі пошуку одиночного символу рекомендується використовувати метод indexOf(String s) замість indexOf(int ch).
Цей висновок поширюється на поточні версії JDK (перевірка проводилася для JDK 1.5, 1.6) і для інших версій потребує ретельної перевірки.