Спирала, намиране на единичен знак в низ

Спирала група

Намиране на единичен знак в низ като Струна . Java JDK 1.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 кодова точка).

публична статична void main (String args [])

StringBuffer sb = нов StringBuffer ("CBABA");

Низова дума = "AAAAAAF";

Низ str = sb.toString ();

System.out.println ("Номер на символите в изходния низ =" + str.length ());

дълъг старт = System.currentTimeMillis ();

pos = str.indexOf ("F");

дълъг край = System.currentTimeMillis ();

System.out.println ("метод indexOf със символа String."+

"Изминало време:" + (край-старт) + "msec");

System.out.println ("метод indexOf със символа String."+

"Намерен низ в позиция:" + pos);

pos = str.indexOf ('F');

System.out.println ("метод indexOf със символ (кодова точка на Unicode)."+

"Изминало време:" + (край-старт) + "msec");

System.out.println ("метод indexOf със символ (кодова точка на Unicode)."+

"Намерен низ в позиция:" + pos);

java - Xmx 1024 M SingleSymbolSearch

За да започнете, се нуждаете от достатъчно място в RAM, ако се покаже грешка, свързана с липса на памет, тогава можете да я намалите в цикъла for (int i = 0; i

Резултати от програмата:

Номер на символите в изходния низ = 130000012

indexOf метод със String символ. Изминало време: 437 msec

indexOf метод със String символ. Намерен низ на позиция: 130000011

indexOf метод със символ (кодова точка на Unicode). Изминало време: 641 msec

indexOf метод с символ (кодова точка на Unicode). Намерен низ на позиция: 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 = отместване + брой;

> else if (fromIndex> = count)

// Забележка: fromIndex може да е близо до -1 >>> 1.

int i = отместване + отIndex;

// обработваме повечето случаи тук (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)

return indexOf (str, 0);

public int indexOf (String str, int fromIndex)

return 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)

връщане (targetCount == 0? sourceCount: -1);

ако (targetCount == 0)

char първо = target [targetOffset];

int max = sourceOffset + (sourceCount - targetCount);

за (int i = sourceOffset + fromIndex; i

/ * Потърсете първия знак. * /

ако (източник [i]! = първи)

/ * Намерен първи знак, сега погледнете останалата част от v2 * /

int край = j + targetCount - 1;

за (int k = targetOffset + 1; j

/ * Намерен цял низ. * /

return i - sourceOffset;

Както можете да видите от тези примери, по-голямата част от кода се изпълнява не в самия метод, а в претоварени методи. Правейки предварително заключение, че метод с по-малко код и по-малко сложен алгоритъм е по-бърз, лесно е да се направи сериозна грешка.

Разделите на кода, които представляват пречка и които носят най-голямо натоварване при изчисленията, са маркирани в червено:

За метода indexOf (int ch):

return i - отместване;

За метод indexOf (String s):

Както можете да видите, за варианта indexOf (int ch) се използва цикъл for с допълнителна проверка if, докато методът indexOf (String s) се заобикаля от един цикъл while с проверка, вложена вътре в цикъла. Съвсем очевидно е, че горните методи са предназначени за търсене, като се вземат предвид изместванията и са малко излишни за нашия пример. Изберете и трансформирайте необходимия код в отделен тест.

SingleSymbolSearch 2.java файл

публична статична void main (String args [])

StringBuffer sb = нов StringBuffer ("CBABA");

Низова дума = "AAAAAAF";

char [] s = sb.toString (). toCharArray ();

System.out.println ("Номер на символите в изходния низ =" + s.length);

дълъг старт = System.currentTimeMillis ();

int max = s.length;

дълъг край = System.currentTimeMillis ();

System.out.println ("метод indexOf със символа String."+

"Изминало време:" + (край-старт) + "msec");

System.out.println ("метод indexOf със символа String."+

"Намерен низ в позиция:" + pos);

System.out.println ("метод indexOf със символ (кодова точка на Unicode)."+

"Изминало време:" + (край-старт) + "msec");

System.out.println ("метод indexOf със символ (кодова точка на Unicode)."+

"Намерен низ в позиция:" + pos);

java - Xmx 1024 M SingleSymbolSearch

За да започнете, се нуждаете от достатъчно място в RAM паметта, ако се покаже грешка, свършила паметта, можете да я намалите в реда for (int i = 0; i

Резултати от програмата:

Номер на символите в изходния низ = 130000012

indexOf метод със String символ. Изминало време: 407 msec

indexOf метод със String символ. Намерен низ на позиция: 130000011

indexOf метод с символ (кодова точка на Unicode). Изминало време: 469 msec

indexOf метод с символ (кодова точка на Unicode). Намерен низ на позиция: 130000011

Въз основа на резултатите можем да заключим, че причината за скоростта на метода е да се използва компактен цикъл с по-малко оператори. Следователно, когато търсите единичен знак, се препоръчва да използвате метода indexOf (String s) вместо indexOf (int ch) .

Този изход се отнася за използваните в момента версии на JDK (проверката е извършена за JDK 1.5, 1.6), а за други версии изисква внимателна проверка.