|
Java форум JavaTalks
форум программистов
|
|
|
|
| Предыдущая тема :: Следующая тема |
| Автор |
Сообщение |
Vurn : 1122
Java Developer
|
 Мар 25, 2007 0:02 |
 |
|
Цикл заметок будет рассматривать разные аспекты работы с типом String.
1. Вырезание подстроки из String правильно делать через String.substring(), а не через генерацию StringBuffer/StringBuilder.
Пример:
| Код: |
public class StringSubString {
static String init(){
char ca[] = new char[25000];
for (int i = 0; i < ca.length; i += 2) {
ca[i] = (char) ('A' + i%26);
ca[i+1] = ' ';
}
return new String(ca);
}
public static void main(String[] args) {
final int RUNS = 25;
final String str = init();
final int parts = str.length() - 1000;
final String sa[] = new String[str.length()];
long st, en;
st = System.currentTimeMillis();
for (int runs = 0; runs < RUNS; runs++) {
for (int i = 0; i < parts; i++) {
sa[i] = str.substring(i , i + 1000);
}
}
en = System.currentTimeMillis();
long stElapsed = en - st;
System.out.println("String.substring() took " + (stElapsed) + " milliseconds");
for (int i = 0; i < parts; i++) {
sa[i] = null;
}
System.gc();
st = System.currentTimeMillis();
StringBuilder sb = new StringBuilder(str);
for (int runs = 0; runs < RUNS; runs++) {
for (int i = 0; i < parts; i++) {
sa[i] = sb.substring(i , i + 1000);
}
}
en = System.currentTimeMillis();
System.out.println("StringBuilder.substring() took " + (en - st) + " milliseconds");
System.out.println("String.substring() faster than StringBuilder.substring() " +
(double)(en - st)/stElapsed + " times" );
}
}
|
у меня на экран выводит
| Код: |
String.substring() took 109 milliseconds
StringBuilder.substring() took 12000 milliseconds
String.substring() faster than StringBuilder.substring() 110.09174311926606 times
|
то есть String.substring() быстрей в 110 раз. Причем, попытка увеличить размер массива ca в init() в 10 раз приводит к падению в OutOfMemory в цикле в StringBuilder. |
|
|
|
 |
Vurn : 1122
Java Developer
|
| Мар 25, 2007 0:03 |
| |
|
Почему так происходит? Дело в том, что String - составной объект. Он включает в себя сам объект и ссылку на char[], который и содержит символы. При этом внутри есть две переменные int offset, count; Первая - индекс начала строки в char[], вторая - длина строки. Таким образом, при создании нового объекта String через substring, массив char[] не создается и не копируется. Два объекта String будут ссылаться на один и тот же char[]. Просто во втором offset & count будут иметь другие значения головы и длины строки. Это допустимо, ибо String - immutable, то есть неизменяемый объект. В выше приведенном примере, все 24900 строк из массива String sa[] разделяют один и тот же char[].
StringBuilder позволить себе такой sharing не может и поэтому вынужден, создавая String, создавать и отдельный char[] для каждой строки, копируя туда символы из себя. Поэтому и медленней и падает в OutOfMemory, ибо массивы отъедают оперативную память. |
|
|
|
|
Vurn : 1122
Java Developer
|
| Апр 21, 2007 19:06 |
| |
|
Для экономии памяти иногда бывает необходимо строку, от которой вырезали подстроку, сбросить через сборщик мусора. Например, из веб-страницы в 250 кб мы "выдрали" байтов 10. Если воспользоваться .substring(), то, как я писал выше, исходная строка останется в памяти. 1000 страниц парсинга и мы упадем в OutOfMemory.
Соотвественно решение - это создать новый объект String() через конструктор.
| Код: |
String addr = new String(webPage.substring(startIndex, endIndex));
|
Соответственно, программируя, надо постоянно держать в памяти (личной), допустимо или нет удерживать в памяти (компьютера) исходную строку.
И соответственно, в разных ситуациях решение будет разным. |
|
|
|
|
Vurn : 1122
Java Developer
|
| Июн 01, 2007 14:30 |
| |
|
Накопление строки
Думаю, не ошибусь, если скажу, что ошибочная работа с накоплением строки является 99% проценной причиной мнения, что Java программы медленные.
Итак, очередной пример:
| Код: |
import java.io.*;
public class Test04 {
static final String FILE_NAME = "test.txt";
static final int STRINGS = 10000;
static void prepareFile(String fileName) throws IOException {
final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(new FileOutputStream(fileName, false)));
for (int i = 0; i < STRINGS ; i++) {
bw.append("Some short string....");
bw.newLine();
}
bw.close();
}
static String readFileViaString (String fileName) throws IOException {
String strBuf = "";
final BufferedReader bf = new BufferedReader(new InputStreamReader(new FileInputStream(fileName)));
while (bf.ready()) {
strBuf = strBuf + bf.readLine();
}
bf.close();
return strBuf;
}
static String readFileViaStringBuilder(String fileName) throws IOException {
final StringBuilder sb = new StringBuilder();
final BufferedReader bf = new BufferedReader(new InputStreamReader(new FileInputStream(fileName)));
while (bf.ready()) {
sb.append(bf.readLine());
}
bf.close();
return sb.toString();
}
static String readFileViaPreparedStringBuilder(String fileName) throws IOException {
final FileInputStream stream = new FileInputStream(fileName);
final StringBuilder sb = new StringBuilder(stream.available());
final BufferedReader bf = new BufferedReader(new InputStreamReader(stream));
while (bf.ready()) {
sb.append(bf.readLine());
}
bf.close();
return sb.toString();
}
public static void main(String[] args) throws IOException {
long st,en;
prepareFile(FILE_NAME);
st = System.currentTimeMillis();
String str1 = readFileViaString(FILE_NAME);
en = System.currentTimeMillis();
System.out.println("String read elapsed " + (en - st) + "ms");
st = System.currentTimeMillis();
String str2 = readFileViaStringBuilder(FILE_NAME);
en = System.currentTimeMillis();
System.out.println("StringBuilder read elapsed " + (en - st) + "ms");
st = System.currentTimeMillis();
String str3 = readFileViaPreparedStringBuilder(FILE_NAME);
en = System.currentTimeMillis();
System.out.println("Prepared StringBuilder read elapsed " + (en - st) + "ms");
if ( str1.equals(str2) & str2.equals(str3)) {
System.out.println("All three strings are equal");
}
}
}
|
Результат работы:
| Код: |
String read elapsed 31941ms
StringBuilder read elapsed 20ms
Prepared StringBuilder read elapsed 10ms
All three strings are equal
|
|
|
|
|
|
Vurn : 1122
Java Developer
|
| Июн 01, 2007 14:55 |
| |
|
То бишь, чтение файла размером в 230 килобайт потребовало почти 32 секунды, когда читали в строку и всего 10 миллисекунд - при чтении в StringBuider с последующей конвертацией в строку.
Разница - колоссальная. Но еще больше она становится, если увеличить количество строк.
Для примера, если STRINGS = 20000, то результаты становятся вообще убийственные:
| Код: |
String read elapsed 164395ms
StringBuilder read elapsed 38ms
Prepared StringBuilder read elapsed 17 ms
All three strings are equal
|
То бишь, через String накопление шло 3 минуты, а через StringBuilder - 1 миллисекунд.
Почему так происходит? String - immutable. Он не может изменятся, он может быть только заменен новым. То есть, читается первая строка в первый раз. Создается объект String, создается char[] внутри объекта, копируется строка. Когда дописываем вторую, создается новый объект, новый массив, в который копируется строка из первого, затем дописывается вторая строка. Когда создаем третий - копируется первая+вторая и дописывается третья.
Таким образом, первая строка будет откопирована n-1 раз, вторая - n-2 (если n - это количество строк ), а формула для всех строк - (n - 1) + (n - 2) +.. + (n - n +1). Или же - n^2 - n. То бишь, с ростом файла в два раза - программа будет замедлятся в 4 раза.
В отличие от String, в StringBuffer/StringBuilder - строки дописываются в один и тот же массив, который растет при необходимости. Резерв для дописывании достаточно мал - 16 байт, соответственно, если есть возможность "предсказать" размер строки - надо стараться создавать с предустановленным размером. В функции readFileViaPreparedStringBuilder() это делается строкой -
| Код: |
new StringBuilder(stream.available())
|
То есть, массив char[] в этом StringBuilder не пересоздается по мере чтения и это ускоряет его в два раза по сравнению с конструктором new StringBuilder();
То есть, любое накопление строки, если строк больше, чем 2-3 - надо делать через StringBuilder/StringBuffer. |
|
|
|
|
Vurn : 1122
Java Developer
|
| Июн 01, 2007 15:33 |
| |
|
Теперь о тонкой разнице между StringBuffer & StringBuilder. Если посмотреть в описании - то вся разница между ними - StringBuffer - thread-safe. A StringBuilder - нет.
| Код: |
public class Test05 implements Runnable {
static final String STRING_EXAMPLE = "Simple string example\n";
StringBuilder stringBuilder;
StringBuffer stringBuffer;
String threadId;
int run;
StringBuilder tempSb;
Test05(String th, StringBuilder sbl, StringBuffer sbf){
threadId = th;
stringBuilder = sbl;
stringBuffer = sbf;
tempSb = new StringBuilder(32);
}
public static void main(String[] args) throws InterruptedException {
StringBuilder sbl = new StringBuilder();
StringBuffer sbf = new StringBuffer();
Thread th1 = new Thread(new Test05("Thread 1", sbl, sbf));
th1.start();
Thread th2 = new Thread(new Test05("Thread 2", sbl, sbf));
th2.start();
th1.join();
th2.join();
System.out.println("StringBuilder length \n" + sbl.length());
System.out.println("StringBuffer length \n" + sbf.length());
}
public void run() {
for(int i = 0; i < 2000; i++){
stringBuilder.append(STRING_EXAMPLE);
for(int j = 0; j < 100; j++);
stringBuffer.append(STRING_EXAMPLE);
}
}
}
|
Как видим, создаются два буфера, в которые по циклу добавляется одинаковое количество одинаковых строк.
Итак, результат вывода:
| Код: |
StringBuilder length
84546
StringBuffer length
88000
|
О чем это говорит? В оба буфера добавилось одинаковое количество одинаковых строк, но их размер разный и StringBuilder - меньше. Это означает, что часть информации в StringBuilder не добавилось и было потеряно.
Как это произошло? В функции main были созданы объекты. В два созданных объекта th1 & th2 были переданны ссылки на них. при этом сами буферы были откопированы в глобальное хранилище, а их копии откопированы в локальные хранилища переменных нитей th1 & th2. Нити начали добавлять информацию в буфера, но StringBuffer при каждом обновлении копирался снова в глобальное хранилище, а потом перекопировался в другую нить, а StringBuilder - совсем даже не всегда, а от случая к случаю. Естественно, бывали моменты, когда обе нити добавляли информацию к StringBuilder'у одновременно, потом копировали информацию в глобальное хранилище, "перезатирая" друг друга.
То бишь, если мы оперируем буфером в заведомо одной нити (обычно - в пределах одной функции) - используем StringBuilder(). Он быстрей.
В противном случае, если даже подозреваем возможность, что накопление может идти с нескольких нитей - используем StringBuffer() |
|
|
|
|
ur6lad : 694
шкипер
Откуда: KN89DX
|
| Июл 30, 2009 12:51 |
| |
|
Сортировка строк с учётом алфавитного порядка букв
По следам темы о сортировке строк. Несмотря на заявленный в методе String.compareTo лексикографический порядок сравнения строк на самом деле при сравнении испольузется индекс символа в таблице Unicode. Что не всегда соответствует реальному положению символа в алфавите. Как пример: русская буква Ё имеет код 0x0401, украинская Ґ - 0x0490. Соответственно при сравнении с помощью compareTo буква Ё окажется перед буквой А (код 0x0410), а буква Ґ - даже после буквы Я (код 0x042f).
Как быть?
Для сортировки с учётом расположения букв в алфавите необходимо использовать класс java.text.Collator. Для получения экземпляра обычно используется метод Collator.getInstance. Есть переопределенная версия этого метода, которая позволяет задать отличную от используемой по умолчанию локаль.
| Код: |
import java.text.Collator;
import java.util.Locale;
public class CompareString {
public static String compareRussianStrings(String first, String second) {
StringBuilder result = new StringBuilder();
Collator russianCollator = Collator.getInstance(new Locale("ru", "RU"));
int order;
result.append(first).append(vs).append(second).append(detail);
result.append(compare).append(
(first.compareTo(second) < 0) ? asc : desc
).append(comma);
result.append(collator).append(
(russianCollator.compare(first, second) < 0) ? asc : desc
).append(nl);
return result.toString();
}
public static void main(String args[]) {
StringBuilder message = new StringBuilder();
String буква_Ё = "Ё", буква_А = "А", буква_Б = "Б", буква_В = "В";
message.append(compareRussianStrings(буква_Ё, буква_А));
message.append(compareRussianStrings(буква_Б, буква_А));
message.append(compareRussianStrings(буква_А, буква_В));
if (args.length >= 2)
message.append(compareRussianStrings(args[0], args[1]));
javax.swing.JOptionPane.showMessageDialog(null, message, "Результат сравнения строк", javax.swing.JOptionPane.PLAIN_MESSAGE);
}
// Различные вспомогательные переменные
private static final String vs = " vs. ", detail = "\n\t", comma = ", ", nl = "\n",
compare = "compareTo: ", collator = "collator: ",
asc = "в порядке возрастания", desc = "в порядке убывания";
} |
В результате вы должны увидеть что-то вроде
Важно
Кириллические имена переменных используются только ради демонстрационных целей. Крайне не рекомендую в коде реальных приложений использовать не латинские имена для переменных и методов. Результат сравнения с целью упрощения используется немного не верно так как у обеих методов результат может принимать следующие значения: отрицательный (строки идут в лексикографическом порядке), ноль (строки идентичны), положительный (строки идут в порядке, обратном лексикографическому).
_________________
Java is to Javascript as ham is to hamster |
|
|
|
|
|
|
Страница 1 из 1
|
Список форумов
-> Примеры |
|
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
|
|
