Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Java: Общие вопросы > Быстрый способ сравнить строки


Автор: DenWPF 21.9.2010, 14:27
Вот как быстрее всего сравнить две строки?

equals - он как сравнивает по символьно?

Автор: Joil 21.9.2010, 15:03
Цитата(DenWPF @  21.9.2010,  14:27 Найти цитируемый пост)
equals - он как сравнивает по символьно?

Код

    public boolean equals(Object anObject) {
    if (this == anObject) {
        return true;
    }
    if (anObject instanceof String) {
        String anotherString = (String)anObject;
        int n = count;
        if (n == anotherString.count) {
        char v1[] = value;
        char v2[] = anotherString.value;
        int i = offset;
        int j = anotherString.offset;
        while (n-- != 0) {
            if (v1[i++] != v2[j++])
            return false;
        }
        return true;
        }
    }
    return false;
    }

Автор: DenWPF 21.9.2010, 15:15
по символьный, значит быстрей уже не как. ну гуд. спасибо.

Автор: Joil 21.9.2010, 18:27
Цитата(DenWPF @  21.9.2010,  15:15 Найти цитируемый пост)
по символьный, значит быстрей уже не как. ну гуд. спасибо. 

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

Автор: DenWPF 21.9.2010, 18:42
а как хэш генерируется?

Автор: jk1 21.9.2010, 19:39
Код

myString.hashCode();

Автор: DenWPF 21.9.2010, 20:14
ну я в плане механизме.

Автор: jk1 21.9.2010, 21:37
Цитата

ну я в плане механизме. 

Код

 public int hashCode() {
    int h = hash;
    if (h == 0) {
        int off = offset;
        char val[] = value;
        int len = count;

            for (int i = 0; i < len; i++) {
                h = 31*h + val[off++];
            }
            hash = h;
        }
        return h;
    }


Есть кстати еще хороший способ быстрого сравнения, заключается он в вызове метода intern() у всего, что хотите в будущем сравнивать и пользоваться тем, что он вернет. После этого строки можно сравнивать по ссылкам через оператор ==, а это куда быстрее посимвольного сравнения. http://habrahabr.ru/blogs/java/79913/.

Автор: Skipy 22.9.2010, 09:50
Цитата(Joil @ 21.9.2010,  18:27)
Ну почему, если строки очень большие то я думаю быстрее будет взять хэш от каждой строки и сравнить хэши.

У неравных строк могут быть равные хеши, это не противоречит контракту. Обратное неверно. Так что НЕравенство выяснить можно по хеш-коду. Но если они равны - это ни о чем не говорит. То же верно и про хеш-функции (хотя попасть в 128 бит того же MD5 намного сложнее, чем в 32 бита hashCode). Кстати, подсчет хеша займет порядочно времени, имхо, сравнить быстрее.

Можно, конечно, попользоваться методом intern. Но во-первых, это надо делать аккуратно, во-вторых, одно сравнение все-таки будет (когда в буфере строку будут искать), в-третьих - при интенсивном использовании рискуете получить OutOfMemory:PermGen - буфер сильно разрастется.

Автор: danilka 22.9.2010, 10:17
Цитата(Skipy @  22.9.2010,  09:50 Найти цитируемый пост)
Можно, конечно, попользоваться методом intern. Но во-первых, это надо делать аккуратно, во-вторых, одно сравнение все-таки будет (когда в буфере строку будут искать), в-третьих - при интенсивном использовании рискуете получить OutOfMemory:PermGen - буфер сильно разрастется. 


А вот об этом можно поподробнее?
Почему это надо делать аккуратно?
Разве строка будет искаться в буфере когда для нее нужен intern(). Там нет прямой ссылки?
Если не пользоваться intern() разве буфер не разрастется?

Автор: Skipy 22.9.2010, 12:52
Цитата
Почему это надо делать аккуратно?


Потому что как только Вы начнете сравнивать строки через == - Вам ВЕЗДЕ надо будет использовать intern. Очень легко это забыть. Плюс есть строки, которые создаются не Вами, их тоже придется обрабатывать.

Цитата
Разве строка будет искаться в буфере когда для нее нужен intern(). Там нет прямой ссылки?


Какой ссылки? Вы себе представляете, как работает intern? Почитайте документацию: http://download.oracle.com/javase/6/docs/api/java/lang/String.html#intern()

Цитата
When the intern method is invoked, if the pool already contains a string equal to this String object as determined by the equals(Object) method, then the string from the pool is returned.


as determined by the equals(Object) method означает, что для определения наличия в пуле вызывается equals. Более того, происходит ПОИСК, что означает как минимум несколько сравнений, даже при оптимизациях. Таким образом, на каждый вызов intern как минимум один раз equals вызовется. А скорее всего - больше одного раза. И с ростом размера пула возможен рост времени поиска.

Цитата
Если не пользоваться intern() разве буфер не разрастется?


А с чего бы ему разрастаться? В буфер попадают строковые литералы и результаты вызова intern. Если не пользоваться intern - там будут только строковые литералы. Ну и если кто-то другой кладет строки через intern - они тоже, но на это Вы никак не влияете.

Автор: danilka 22.9.2010, 13:55
Цитата(Skipy @  22.9.2010,  12:52 Найти цитируемый пост)
Потому что как только Вы начнете сравнивать строки через == - Вам ВЕЗДЕ надо будет использовать intern. Очень легко это забыть. Плюс есть строки, которые создаются не Вами, их тоже придется обрабатывать.


Нет ну понятно что я везде не буду использовать такое сравнение...

Цитата(Skipy @  22.9.2010,  12:52 Найти цитируемый пост)
Какой ссылки? Вы себе представляете, как работает intern? Почитайте документацию: http://download.oracle.com/javase/6/docs/a...g.html#intern()


Просто у меня был мысль что после того как у строки вызван метод intern() и соответствующий инстанс в пуле найден, почему бы в строке не сохранить ссылку на него...


Цитата(Skipy @  22.9.2010,  12:52 Найти цитируемый пост)
А с чего бы ему разрастаться? В буфер попадают строковые литералы и результаты вызова intern. Если не пользоваться intern - там будут только строковые литералы. Ну и если кто-то другой кладет строки через intern - они тоже, но на это Вы никак не влияете.


Мне почему-то казалось что строковые литералы и результаты вызова intern() это одно и тоже.

Автор: Skipy 22.9.2010, 16:43
Цитата
Нет ну понятно что я везде не буду использовать такое сравнение...


Вот именно. Тогда в каждом месте, где Вы будете использовать ==, необходимо будет обеспечить наличие intern-ированной строки. Т.е. ОЧЕНЬ аккуратно отслеживать, где у Вас строки из пула, а где нет. Это сложно.

Цитата
Просто у меня был мысль что после того как у строки вызван метод intern() и соответствующий инстанс в пуле найден, почему бы в строке не сохранить ссылку на него...


В какой строке? У Вас есть объект - String. Он содержит массив char-ов, длину строки и смещение в массиве. Всё. Никаких ссылок на intern-строки он не содержит и содержать не может. Потому как в общем случае в пуле аналогичной строки нет. 

Цитата
Мне почему-то казалось что строковые литералы и результаты вызова intern() это одно и тоже.


Вам казалось. Строковые литералы - это те строки, которые Вы в коде описываете как "строка". Каждый такой объект преобразуется в String и помещается в пул.

Код

package test;

public class Class1 {

    public static String getString(){
        return "test string";
    }

}


Код

package test;

public class Class2 {

    public static String getString(){
        return "test string";
    }

}


Код

package test;

public class Test {

    public static void main(String[] args) {
        System.out.println(Class1.getString() == Class2.getString());
    }

}


Вот этот тест вернет true. Но к intern это не имеет никакого отношения, этот метод тут, как видите, не вызывается. Всё делается на стадии компиляции и загрузки классов.

Автор: danilka 22.9.2010, 17:46
Цитата(Skipy @  22.9.2010,  16:43 Найти цитируемый пост)
В какой строке? У Вас есть объект - String. Он содержит массив char-ов, длину строки и смещение в массиве. Всё. Никаких ссылок на intern-строки он не содержит и содержать не может. Потому как в общем случае в пуле аналогичной строки нет. 


Под строкой я и имел ввиду объект класса String. То есть Вы хотите сказать что можно создать строку так чтобы в пуле не было соответствующего ей объекта intern()?

Поделитесь первоисточником плиз где описано как хранятся строковые литералы, и пул для intern-строк и в какой момент они заполняются.

Автор: Evgeni68 24.9.2010, 19:45
Цитата(danilka @ 22.9.2010,  17:46)
То есть Вы хотите сказать что можно создать строку так чтобы в пуле не было соответствующего ей объекта intern()?

Код

String test = new String("Hello world");


Данный код создаст объект типа String не помещая строку в пул.

Автор: Skipy 24.9.2010, 20:05
Цитата(Evgeni68 @ 24.9.2010,  19:45)
Цитата(danilka @ 22.9.2010,  17:46)
То есть Вы хотите сказать что можно создать строку так чтобы в пуле не было соответствующего ей объекта intern()?

Код

String test = new String("Hello world");


Данный код создаст объект типа String не помещая строку в пул.

Ну, сам строковый литерал "Hello world!" в пуле таки будет. Так что при сравнении по equals с вновь созданной строкой вернется именно он. Не совсем удачный пример.

А вот так - строки точно не будет в пуле (разве что случайно такая окажется smile):

Код

byte[] bytes = ...;
String str = new String(bytes, encoding);

Автор: Evgeni68 24.9.2010, 22:10
Цитата(Skipy @ 24.9.2010,  20:05)
Ну, сам строковый литерал "Hello world!" в пуле таки будет. Так что при сравнении по equals с вновь созданной строкой вернется именно он. Не совсем удачный пример.

Да, действительно, пример не совсем удачный.
Но смысл от того что литерал будет в пуле?

Код

String test1 = "test";
String test2 = new String("test");
        
System.out.println(test1 == test2);


Выводом будет FALSE. Метод equals в классе String сначала проверяет равенство ссылок, а затем обычное сравнение строк по символам. В итоге никакого преимущества в скорости от того, что литерал в пуле - нет.

Или я чего-то не допонимаю? Поправьте.

Автор: Skipy 27.9.2010, 12:02
Цитата(Evgeni68 @ 24.9.2010,  22:10)
Но смысл от того что литерал будет в пуле?

Код

String test1 = "test";
String test2 = new String("test");
        
System.out.println(test1 == test2);


Выводом будет FALSE. 

Код

String test1 = "test";
String test2 = new String("test").intern();
        
System.out.println(test1 == test2);


Так лучше? А то Вы как-то упустили, что test2 указывает не на тот экземпляр, который в пуле.

Автор: danilka 28.9.2010, 09:43
Цитата(Skipy @  24.9.2010,  20:05 Найти цитируемый пост)
А вот так - строки точно не будет в пуле (разве что случайно такая окажется smile):

byte[] bytes = ...;
String str = new String(bytes, encoding);


Тут Вы имеете ввиду пул строковых литералов или пул intern()?

Автор: Skipy 28.9.2010, 11:54
Цитата(danilka @ 28.9.2010,  09:43)
Тут Вы имеете ввиду пул строковых литералов или пул intern()?

Пул - он один. Еще раз объясняю - строковые литералы существуют только в исходном коде. При компиляции они помещаются в пул строк. И в него же во время исполнения помещаются отсутствующие в нем строки при вызове на них метода intern().

Автор: Evgeni68 28.9.2010, 21:39
Цитата(Skipy @ 27.9.2010,  12:02)
Цитата(Evgeni68 @ 24.9.2010,  22:10)
Но смысл от того что литерал будет в пуле?

Код

String test1 = "test";
String test2 = new String("test");
        
System.out.println(test1 == test2);


Выводом будет FALSE. 

Код

String test1 = "test";
String test2 = new String("test").intern();
        
System.out.println(test1 == test2);


Так лучше? А то Вы как-то упустили, что test2 указывает не на тот экземпляр, который в пуле.

Так гораздо лучше! Просто я хотел сказать, что создавать новый инстанс строки, передавая в конструктор литерал - мягко говоря не рационально.

Автор: danilka 29.9.2010, 09:43
Цитата(Skipy @  28.9.2010,  11:54 Найти цитируемый пост)
Пул - он один. Еще раз объясняю - строковые литералы существуют только в исходном коде. При компиляции они помещаются в пул строк. И в него же во время исполнения помещаются отсутствующие в нем строки при вызове на них метода intern(). 


То есть правильно ли я понял?
Представим что каждая из приведенных ниже строк кода выполняется в новом приложении (пул строк пустой)

Код

String s = "test"; //строка "test" помещяется в пул
String s = ss.intern(); //строка с аналогичным ss контентом помещается в пул (если ее там еще не было)
String s = new String("test"); //строка "test" НЕ помещяется в пул

Автор: Skipy 29.9.2010, 13:31
Цитата(Evgeni68 @ 28.9.2010,  21:39)
Просто я хотел сказать, что создавать новый инстанс строки, передавая в конструктор литерал - мягко говоря не рационально.


Ага. И Вы на эти грабли наступили...

Рассказываю.

Допустим, у Вас есть строка. Большая, в несколько тысяч символов. Вы выбираете подстроку, символов 10. Исходная строка выбрасывается. Вопрос. Освобождается ли память, которую занимала эта подстрока?

А вот не освобождается! В качестве базы строки берется текущий массив char-ов. И просто выставляется смещение и длина. Но при этом ВСЯ исходная строка, фактически, остается в памяти. Это оптимизация, чтобы избежать копирования (и память дополнительная нужна, и время).

А вот конструктор String(String) - он КОПИРУЕТ строку. Т.е. если Вы результаты Вашего substring передадите в копирующий конструктор, несмотря на внешнюю бессмысленность этого действия, - у Вас останется массив из нужных 10 символов. А исходный массив соберется как мусор, если Вы убъете на него ссылки.

Так что да, создавать строку на основе литерала прямо в коде - нерационально, если только Вы не хотите, чтобы ссылка была не на объект, находящийся в пуле. Но копирующий конструктор сам по себе - бывает весьма полезен.

Добавлено @ 13:35
Цитата(danilka @ 29.9.2010,  09:43)
Код

String s = "test"; //строка "test" помещяется в пул
String s = ss.intern(); //строка с аналогичным ss контентом помещается в пул (если ее там еще не было)
String s = new String("test"); //строка "test" НЕ помещяется в пул

Да.

Да.

Нет. "test" помещается в пул - ибо есть строковый литерал. s - по значению в пуле будет, ибо создана на основе литерала. Т.е. вызов s.intern() не приведет к помещению новых данных в пул, а вернет ссылку на "test". А вот ссылка на s - не будет совпадать со сcылкой на "test", т.е.  результатом (s =="test") будет false.

Автор: Evgeni68 29.9.2010, 20:23
Цитата(Skipy @  29.9.2010,  13:31 Найти цитируемый пост)
Так что да, создавать строку на основе литерала прямо в коде - нерационально, если только Вы не хотите, чтобы ссылка была не на объект, находящийся в пуле. Но копирующий конструктор сам по себе - бывает весьма полезен.


Спасибо, очень полезно. О копирующем конструкторе не задумывался smile .

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)