Comments 81
условное сравнение — плохо.
лучше использовать таблицу.
что-то типа:
Таким образом значение в oldChars[i] будет перезатираться до тех пор, пока не увеличим счетчик, то есть не найдем корректный символ для этой позиции.
Ну и разворот цикла, я думаю, тоже бы помог.
лучше использовать таблицу.
что-то типа:
unsigned char allowedChars[256] = {
/* 0x00 */ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
/* 0x10 */ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
/* 0x20 */ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
...
};
...
oldChars[newLen] = ch;
newLen += allowedChars[ch];
Таким образом значение в oldChars[i] будет перезатираться до тех пор, пока не увеличим счетчик, то есть не найдем корректный символ для этой позиции.
Ну и разворот цикла, я думаю, тоже бы помог.
Ой не факт, что таблица будет лучше, учитывая тот момент, что сравнение (это все же сравнение регистра и константы), а обращение к таблице, это дополнительное обращение к памяти. Конечно в данном случае все зависит от реализации виртуальной машины, но все же использование константы и обращение к памяти. При сравнении есть усугубление в виде последующего условного перехода, так что данный вариант стоило бы просто проверить на практике.
Очень спорно. Обычно любые манипуляции с памятью работают медленнее чем арифметические операции.
Вообще статья напомнила «сначала напишем криво, а потом напишем нормально и обнаружим 10x прирост скорости». А ведь заголовок был интересный: «чуть ниже я покажу, как можно заменить одну строчку на пару десятков, увеличив производительность алгоритма в несколько десятков раз» — я сразу представил, как одну строчку скопировали десять раз, как то хитро удалили символы из них, учитывая особенности кеша процессора, потом соединили строчки вместе и получили то что надо, но быстрее в 10 раз. Оказалось, что в «заменить одну строчку на пару десятков» под строчкой имелась ввиду строчка кода, а не та строчка в которой надо символы удалять :)
Вообще статья напомнила «сначала напишем криво, а потом напишем нормально и обнаружим 10x прирост скорости». А ведь заголовок был интересный: «чуть ниже я покажу, как можно заменить одну строчку на пару десятков, увеличив производительность алгоритма в несколько десятков раз» — я сразу представил, как одну строчку скопировали десять раз, как то хитро удалили символы из них, учитывая особенности кеша процессора, потом соединили строчки вместе и получили то что надо, но быстрее в 10 раз. Оказалось, что в «заменить одну строчку на пару десятков» под строчкой имелась ввиду строчка кода, а не та строчка в которой надо символы удалять :)
Вообще-то речь идет о Java. Там newLen += allowedChars[ch] выльется как минимум в два сравнения (range check). Да даже для C эта оптимизация не имеет смысла: newLen += (ch >= ' ') будет быстрее. Условных переходов в сгенерированном коде нет.
А если символ будет больше, чем 256? OutOfBoundsException
То ли народ перестает задумываться о оптимизации, то ли что, что на оптимизацию подобного тратится столько времени, да и по этому еще пишется статья.
TDD возможно и хорош, но хорош, когда недостаточно опыта сделать правильную оценку ситуации.
В данном случае, сразу понятно, что необходимо минимизировать работу с памятью, исходя из этого регулярки, StringBuilder можно было отсеять на этапе постановки задачи.
TDD возможно и хорош, но хорош, когда недостаточно опыта сделать правильную оценку ситуации.
В данном случае, сразу понятно, что необходимо минимизировать работу с памятью, исходя из этого регулярки, StringBuilder можно было отсеять на этапе постановки задачи.
Все бы так оптимизировали…
Если надо модифицировать всего 0.1% строк, то можно попробовать написать отдельный быстрый поиск управляющего символа. А если вдруг нашли, то уже работать…
Правда, в последнем варианте и так уже лишний действий нет.
Правда, в последнем варианте и так уже лишний действий нет.
В порядке бреда, C-style:
int okCnt = 0;
for (int j = 0; j < length; j++) {
char ch = oldChars[j];
okCnt += ch&128 | ch&64 | ch&32;
}
if (okCnt != length) do_wrk();
Будет ли это работать быстрее так? Будет ли это работать быстрее, если развернуть цикл 4 раза и использовать 4 независимых okCnt? Нет мне ответа, потому что теста в руках нету :)
int okCnt = 0;
for (int j = 0; j < length; j++) {
char ch = oldChars[j];
okCnt += ch&128 | ch&64 | ch&32;
}
if (okCnt != length) do_wrk();
Будет ли это работать быстрее так? Будет ли это работать быстрее, если развернуть цикл 4 раза и использовать 4 независимых okCnt? Нет мне ответа, потому что теста в руках нету :)
Ради эксперимента было бы интересно посмотреть на результат кода на C/C++
осталось i++ заменить на ++i
:)
:)
Уточните, тестировали на синтетике? Или реальные данные? Если синтетика — как формировалась. Дайте больше входных параметров, чем мы хуже stackoverflow :)
Очень хорошие вопросы :) Прошу прощения, что пропустил комментарий и отвечаю с опозданием.
Изолированный алгоритм тестировал на синтетике. Изначально вообще брал одну константную строчку в ~130 символов и 140 UTF-8 байт, прошитую в коде и стирпал ее. В строчке было порядка 5-6 управляющих символов, для измерений прогонял по ~10 миллионов итераций «для разогрева» JIT, затем по ~100 миллионов итераций. Для того, чтобы убедиться, что JIT хотя бы по первому разу отработал — рядом еще был цикл, который не делал ничего. После JIT он, разумеется, превращался в ничто и отрабатывал за 0 мс.
Затем понял, что одинаковая синтетика — тоже плохо и стал поступать так: генерировал N строчек длиной от 20 до 220 символов, заполняя их случайными символами из диапазона 0..127. Пытался читать из с диска и писать на диск, но понял, что это только мешает измерениям и ничего хорошего не приносит. Оно, разумеется, лучше эмулирует поведение на практике, но в тот момент меня уже интересовал больше теоретически достижимый результат и, как следствие, наиболее «чистый» учет времени.
В конечном варианте, когда понял, что нужно сыграть на том, что строчка не изменяется — стал генерировать строчки с символами из диапазона 32..127, и только если Random#nextInt(100) == 0 — с символами из диапазона 0..127.
Все измерения проводил на
Изолированный алгоритм тестировал на синтетике. Изначально вообще брал одну константную строчку в ~130 символов и 140 UTF-8 байт, прошитую в коде и стирпал ее. В строчке было порядка 5-6 управляющих символов, для измерений прогонял по ~10 миллионов итераций «для разогрева» JIT, затем по ~100 миллионов итераций. Для того, чтобы убедиться, что JIT хотя бы по первому разу отработал — рядом еще был цикл, который не делал ничего. После JIT он, разумеется, превращался в ничто и отрабатывал за 0 мс.
Затем понял, что одинаковая синтетика — тоже плохо и стал поступать так: генерировал N строчек длиной от 20 до 220 символов, заполняя их случайными символами из диапазона 0..127. Пытался читать из с диска и писать на диск, но понял, что это только мешает измерениям и ничего хорошего не приносит. Оно, разумеется, лучше эмулирует поведение на практике, но в тот момент меня уже интересовал больше теоретически достижимый результат и, как следствие, наиболее «чистый» учет времени.
В конечном варианте, когда понял, что нужно сыграть на том, что строчка не изменяется — стал генерировать строчки с символами из диапазона 32..127, и только если Random#nextInt(100) == 0 — с символами из диапазона 0..127.
Все измерения проводил на
java version «1.6.0_24»
Java(TM) SE Runtime Environment (build 1.6.0_24-b07)
Java HotSpot(TM) 64-Bit Server VM (build 19.1-b02, mixed mode)
Linux 2.6.39-2-amd64 #1 SMP Wed Jun 8 11:01:04 UTC 2011 x86_64 GNU/Linux
Еще немного древних методик: префиксный декремент (может тоже не оптимизируется) и обход цикла в обратном порядке.
// здесь проверка что length > 0
int pos = length - 1;
for (int j = pos; j >= 0; --j) {
char ch = oldChars[j];
if (ch >= ' ') {
oldChars[pos] = ch;
--pos;
}
}
if (pos >= 0) {
++pos;
s = new String(oldChars, pos, length - pos);
}Еще один вариант: проверяем на равенство нулю и упрощаем сравнение символов.
// здесь проверка что length > 0
int pos = length — 1;
for (int j = pos; j != 0; --j) {
char ch = oldChars[j];
if (ch > '\x1F') { // или как там пишется ascii код
oldChars[pos] = ch;
--pos;
}
}
char ch = oldChars[0];
if (ch > '\x1F') {
oldChars[pos] = ch;
}
else {
++pos;
}
if (pos != 0) {
s = new String(oldChars, pos, length — pos);
}
P.S. кстати момент «что этот элемент по сути равнозначен выбору символов с кодами от 0 до 31 включительно, плюс 127» в итоговом алгоритме упущен.
// здесь проверка что length > 0
int pos = length — 1;
for (int j = pos; j != 0; --j) {
char ch = oldChars[j];
if (ch > '\x1F') { // или как там пишется ascii код
oldChars[pos] = ch;
--pos;
}
}
char ch = oldChars[0];
if (ch > '\x1F') {
oldChars[pos] = ch;
}
else {
++pos;
}
if (pos != 0) {
s = new String(oldChars, pos, length — pos);
}
P.S. кстати момент «что этот элемент по сути равнозначен выбору символов с кодами от 0 до 31 включительно, плюс 127» в итоговом алгоритме упущен.
Извинияюсь, я не в теме, поэтому такой вопрос — а почему цикл в обратном порядке быстрей?
Городская легенда гласит, что если цикл пустить в обратную сторону, то он компилируется в чуть-более эффективный байт-код (а одну операцию вычитаня меньше, в обласли сравнения условий).
Альтернативно, можно ничего не делать по-умолчанию:
если newLen == j, то писать не нужно вообще ничего! Там и так то же самое.
Альтернативно, можно ничего не делать по-умолчанию:
oldChars[newLen] = ch; очень отжирает время на запись в память.если newLen == j, то писать не нужно вообще ничего! Там и так то же самое.
Тоже подумал о лишнем копировании, вот еще один вариант (за точность не ручаюсь негде проверить):
// здесь проверка что length > 0
int pos = length — 1;
char ch = oldChars[pos];
while (pos != 0 && ch > '\x1F') {
--pos;
ch = oldChars[pos];
}
if (pos == 0) {
if (ch > '\x1F') {
// возвращаем исходную строку
}
}
else {
for (int j = pos — 1; j != 0; --j) {
char ch = oldChars[j];
if (ch > '\x1F') { // или как там пишется ascii код
oldChars[pos] = ch;
--pos;
}
}
ch = oldChars[0];
}
if (ch > '\x1F') {
oldChars[pos] = ch;
}
else {
++pos;
}
if (pos != 0) {
s = new String(oldChars, pos, length — pos);
}
// здесь проверка что length > 0
int pos = length — 1;
char ch = oldChars[pos];
while (pos != 0 && ch > '\x1F') {
--pos;
ch = oldChars[pos];
}
if (pos == 0) {
if (ch > '\x1F') {
// возвращаем исходную строку
}
}
else {
for (int j = pos — 1; j != 0; --j) {
char ch = oldChars[j];
if (ch > '\x1F') { // или как там пишется ascii код
oldChars[pos] = ch;
--pos;
}
}
ch = oldChars[0];
}
if (ch > '\x1F') {
oldChars[pos] = ch;
}
else {
++pos;
}
if (pos != 0) {
s = new String(oldChars, pos, length — pos);
}
Еще один вариант:
int pos = length — 1;
if (pos < 1) {
if (pos == 0 && chars[0] > '\x1F') {
return s;
}
else {
return string.Empty;
}
}
char ch = chars[pos];
while(ch > '\x1F') {
if (--pos == 0) {
if (chars[pos] > '\x1F') {
return s;
}
else {
return new String(chars, 1, length — 2);
}
}
ch = chars[pos];
}
for (int j = pos; --j != 0;) {
ch = chars[j];
if (ch > '\x1F') { // или как там пишется ascii код
chars[pos--] = ch;
}
}
ch = chars[0];
if (ch > '\x1F') {
chars[pos] = ch;
}
else {
++pos;
}
return new String(chars, pos, length — pos);
int pos = length — 1;
if (pos < 1) {
if (pos == 0 && chars[0] > '\x1F') {
return s;
}
else {
return string.Empty;
}
}
char ch = chars[pos];
while(ch > '\x1F') {
if (--pos == 0) {
if (chars[pos] > '\x1F') {
return s;
}
else {
return new String(chars, 1, length — 2);
}
}
ch = chars[pos];
}
for (int j = pos; --j != 0;) {
ch = chars[j];
if (ch > '\x1F') { // или как там пишется ascii код
chars[pos--] = ch;
}
}
ch = chars[0];
if (ch > '\x1F') {
chars[pos] = ch;
}
else {
++pos;
}
return new String(chars, pos, length — pos);
Отрадно было прочитать вот это в начале статьи:
>С моей точки зрения логично было бы, чтобы такая задача упиралась в диск или сеть — нагрузка на процессор здесь должна быть минимальная. Однако, простейший профайлинг показал совсем другое. Исходный вариант содержал строчку, на которую тратилось 80-90% рабочего времени алгоритма — это была ровно одна строчка, которая и делала операцию 3, вот она:
Главное, чтобы потом эту функцию не начали использовать для обработки UTF-8, там много многобайтовых управляющих символов.
Если строка превратилась в Java String, то там в любом случае UTF-16. В другом виде char не хранится.
Тут стоит на самом деле уточнить задачу: мне на самом деле не нужно было вырезать все возможные управляющие символы (тем более то, что называется в Unicode с general category равной Cc, Cf и Cs), мне даже не нужно было вырезать все управляющие символы ASCII. После этой обработки данные записываются в текстовые tab-separated файлы — в минимальном варианте мне нужно было просто обеспечить удаление \t, \n, \r (9, 10, 13), чтобы они не порушили парсинг такого текстового файла дальше у пользователя — т.е. строчки оставались бы строчками, столбцы бы не съезжали.
В качестве бонуса — приятно было бы, чтобы экран при просмотре файла не перекашивало от случайного наличия Esc-последовательностей (т.е. нужно резать 27) и чтобы консоль не пищала (т.е. резать 7)
В итоге оказалось, что проще и эффективнее просто отрезать все, что в диапазоне 0-31.
В качестве бонуса — приятно было бы, чтобы экран при просмотре файла не перекашивало от случайного наличия Esc-последовательностей (т.е. нужно резать 27) и чтобы консоль не пищала (т.е. резать 7)
В итоге оказалось, что проще и эффективнее просто отрезать все, что в диапазоне 0-31.
А чем не угодил символ #127?
В смысле — «не угодил» и кому он не угодил?
Цитирую:
Вспоминаем, что же именно у нас за строчки и что нам нужно фильтровать и что такое \p{Cntrl}. Понимаем, что этот элемент по сути равнозначен выбору символов с кодами от 0 до 31 включительно, плюс 127.C [0..31] всё ясно, а чем опасен «плюс 127»?
Видимо, тем же, чем и [0..31] — в некоторых системах он является управляющим символом, с определенной семантикой и всем полагающимся. Тут уж тогда надо или более философский вопрос «что является управляющим символом» ставить, или — в данном конкретном случае — просто не париться, потому что авторы движка регэкспов в Sun уже давно решили для себя эту проблему вот таким вот образом.
Если вдаваться в философствования — то имеет смысл либо отвечать на вопрос «для кого является» (и понимать, что в описываемом кластерном комплексе на самом деле более, чем достаточно было фильтровать всего 3 символа — \t, \r и \n), либо пытаться составить «список управляющих символов на все случаи жизни по всем возможным стандартам». Это, кстати, весьма нетривиально с учетом Unicode.
Если вдаваться в философствования — то имеет смысл либо отвечать на вопрос «для кого является» (и понимать, что в описываемом кластерном комплексе на самом деле более, чем достаточно было фильтровать всего 3 символа — \t, \r и \n), либо пытаться составить «список управляющих символов на все случаи жизни по всем возможным стандартам». Это, кстати, весьма нетривиально с учетом Unicode.
Расскажу и я байку про оптимизацию. На одном заводе из листа цветного металла раскраивали круглые заготовки для последующей вытяжки и обрезки (делали стаканы). На завод пришли два молодца, которые на коленке и существовавшей в то время на заводе ЭВМ набросали алгоритм, который рассчитал оптимальный раскрой позволяющий экономить до 40% металла при раскрое. Внедрили в производство. А рабочие в итоге стали на них как волки смотреть, а все потому что обрезки которые раньше выкидывались шли к ним в карманы, а теперь нет :)
Хм… мне всегда казалось что все обрезки металла отправляются на переработку. Ну а по бумагам должно быть видно сколько металла потрачено на детали, сколько осталось и сколько отправлено на переработку.
У меня дед в свое время работал на заводе, где помимо всего прочего в одном из производственных циклов участвовал титан (какие-то корпуса из него делали, если не ошибаюсь для навигационного оборудования).
Так у всего цеха дома лежали ТИТАНОВЫЕ!!! ведра, лопаты, тазы и прочая утварь. Вечная (до сих пор как новые), легкая, и безобразно дорогая.
Так у всего цеха дома лежали ТИТАНОВЫЕ!!! ведра, лопаты, тазы и прочая утварь. Вечная (до сих пор как новые), легкая, и безобразно дорогая.
Это пересказ вполне реальной истории, имевшей место:
Много лет назад произошла, пожалуй, наиболее типичная — по непониманию — ситуация, которую сегодня часто вспоминают как анекдот. Но это — не анекдот. На вагоностроительном заводе имени Егорова в Ленинграде с помощью линейного программирования сделали раскрой металла. Это была пионерная работа и в мире, и у нас в стране. Делалось все в эпоху арифмометров, а не ЭВМ, вообще, вероятно, это было первое в мировой практике реальное применение методов линейного программирования.
После того как были применены оптимальные методы и несколько сократился расход металла, оказалось, что резко уменьшилась возможность сдачи металлолома. В итоге был сорван план сдачи отходов металла, а раз один из показателей плана не выполнен, то предприятие не может быть премировано в полном размере. Тогда райком помог преодолеть эту трудность, и в виде исключения премия заводу была сохранена, несмотря на срыв одного из показателей. Второй казус этой ситуации: отраслевое начальство, получив рапорт о том, что завод на 4 процента увеличил использование металла при раскрое, предложило им не терять темпа и в следующем году опять подняло план использования металла на те же 4 процента. Выходило, что металл должен использоваться на 101 процент, и пришлось даже писать бумагу от академии, что больше 100 процентов не бывает.
exsolver.narod.ru/Intresting/Kantor/Kantor_seetruth.html
Как водится, передовые технологии (Канторович и его линейное программирование) уперлись в твердолобость бюрократов.
Много лет назад произошла, пожалуй, наиболее типичная — по непониманию — ситуация, которую сегодня часто вспоминают как анекдот. Но это — не анекдот. На вагоностроительном заводе имени Егорова в Ленинграде с помощью линейного программирования сделали раскрой металла. Это была пионерная работа и в мире, и у нас в стране. Делалось все в эпоху арифмометров, а не ЭВМ, вообще, вероятно, это было первое в мировой практике реальное применение методов линейного программирования.
После того как были применены оптимальные методы и несколько сократился расход металла, оказалось, что резко уменьшилась возможность сдачи металлолома. В итоге был сорван план сдачи отходов металла, а раз один из показателей плана не выполнен, то предприятие не может быть премировано в полном размере. Тогда райком помог преодолеть эту трудность, и в виде исключения премия заводу была сохранена, несмотря на срыв одного из показателей. Второй казус этой ситуации: отраслевое начальство, получив рапорт о том, что завод на 4 процента увеличил использование металла при раскрое, предложило им не терять темпа и в следующем году опять подняло план использования металла на те же 4 процента. Выходило, что металл должен использоваться на 101 процент, и пришлось даже писать бумагу от академии, что больше 100 процентов не бывает.
exsolver.narod.ru/Intresting/Kantor/Kantor_seetruth.html
Как водится, передовые технологии (Канторович и его линейное программирование) уперлись в твердолобость бюрократов.
> Добавление final везде, где можно, вопреки традиционно сложившемуся мнению, не дает никакого прироста
«final» — это по сути дела памятка программисту самому себе и директива компилятору напомнить об этом в случае описки. байт-код будет отличаться только атрибутами, но не собственно операциями. поэтому прироста от файнала ждать не следует.
да, кстати, вместо вышеуказаного кода
int pos = length — 1;
for (int j = pos; j >= 0; --j) {
предлагаю
for ( int j = length; --j >= 0; ) {
Существенного прироста это не даст, но выглядит не хуже
«final» — это по сути дела памятка программисту самому себе и директива компилятору напомнить об этом в случае описки. байт-код будет отличаться только атрибутами, но не собственно операциями. поэтому прироста от файнала ждать не следует.
да, кстати, вместо вышеуказаного кода
int pos = length — 1;
for (int j = pos; j >= 0; --j) {
предлагаю
for ( int j = length; --j >= 0; ) {
Существенного прироста это не даст, но выглядит не хуже
это не везде применимо, т.к. pos используется дальше, а вообще прирост может быть, при сравнении j уже будет лежать в регистре.
я хотел показвть общий принцип написания цикла задом наперед,
ибо часто цикл «переворачивают» не совсем оптимально на мой взгляд
вариант 1, прямой классический
for ( int i = 0; i < v.size ( ); i++ )
вариант 2, перевернутый неоптимальный
for ( int i = v.size ( ) — 1; i >= 0; --i )
вариант 3
for ( int i = v.size ( ); --i >= 0; )
я уже привык свой код писать по варианту 3, и остальные варианты уже «режут глаз»
ибо часто цикл «переворачивают» не совсем оптимально на мой взгляд
вариант 1, прямой классический
for ( int i = 0; i < v.size ( ); i++ )
вариант 2, перевернутый неоптимальный
for ( int i = v.size ( ) — 1; i >= 0; --i )
вариант 3
for ( int i = v.size ( ); --i >= 0; )
я уже привык свой код писать по варианту 3, и остальные варианты уже «режут глаз»
А вот еще более красивый вариант:
int i = v.size();
while(i --> 0){
…
}
int i = v.size();
while(i --> 0){
…
}
я не считаю это «более красивым» потому что
а) с точки зрения байткода скорее всего получится примерно то же самое (задание на дом)
б) запись for ( int i… инкапсулирует переменную «i» внутри цикла
в) мне больше нравится однострочная запись цикла for, чем ваш двустрочный вариант
скажем так — это эквивалентная запись варианта 3. кому как нравится.
а) с точки зрения байткода скорее всего получится примерно то же самое (задание на дом)
б) запись for ( int i… инкапсулирует переменную «i» внутри цикла
в) мне больше нравится однострочная запись цикла for, чем ваш двустрочный вариант
скажем так — это эквивалентная запись варианта 3. кому как нравится.
На самом деле, for тоже можно написать в таком стиле:
for ( int i = v.size ( ); i -->0; )
Да, одна строка лучше двух, и инкапсуляция это хорошо, но когда я вижу эти идиотские точки с запятой — мне резко перестает нравиться for-версия(сейчас я про последний символ, висящий, хотя не нравятся мне они все внутри for).
Относительно байткода — думаю, результат просто обязан быть идентичным.
А вообще, у меня это осознанная необходимость — я в основном пишу на haXe, а в нем for работает только с итераторами. Канонически, это надо писать как for(i in 0...v.size()) (Да-да, тип i инферится), где 0...v.size() — сахарный конструктор итератора. Плюс — такой итератор в цикле развернется. Минус — только от меньшего к большему. Так что если хочется выжать немного больше производительности — приходится спускаться к while в любом случае. Но я начал находить в этом особый кайф — while автоматически отмечает оптимизированные места.
И, да, надо уже добавить возможность прохода от большего к меньшему. На самом деле, если я этим займусь, то итоговая версия будет идеальна, на мой взгляд, for(i in v.size()...0) в идеальную по скорости конструкцию.
for ( int i = v.size ( ); i -->0; )
Да, одна строка лучше двух, и инкапсуляция это хорошо, но когда я вижу эти идиотские точки с запятой — мне резко перестает нравиться for-версия(сейчас я про последний символ, висящий, хотя не нравятся мне они все внутри for).
Относительно байткода — думаю, результат просто обязан быть идентичным.
А вообще, у меня это осознанная необходимость — я в основном пишу на haXe, а в нем for работает только с итераторами. Канонически, это надо писать как for(i in 0...v.size()) (Да-да, тип i инферится), где 0...v.size() — сахарный конструктор итератора. Плюс — такой итератор в цикле развернется. Минус — только от меньшего к большему. Так что если хочется выжать немного больше производительности — приходится спускаться к while в любом случае. Но я начал находить в этом особый кайф — while автоматически отмечает оптимизированные места.
И, да, надо уже добавить возможность прохода от большего к меньшему. На самом деле, если я этим займусь, то итоговая версия будет идеальна, на мой взгляд, for(i in v.size()...0) в идеальную по скорости конструкцию.
Вы правы, но лишь частично :)
Я померял все три варианта, получаются такие средние затраты времени:
вариант 1 — 334655
вариант 2 — 335893
вариант 3 — 334851
Т.е. для Java — скорее, самым адекватным остается простой прямой цикл, хотя разница где-то на полпроцента-процент.
Байткод для первого варианта занимает 23 байта (19 инструкций), для второго — 24 байта (20 инструкций), для третьего — 22 байта (18 инструкций). С точки зрения JVM «if_icmplt» и «ifge», видимо, работают одинаково.
Я померял все три варианта, получаются такие средние затраты времени:
вариант 1 — 334655
вариант 2 — 335893
вариант 3 — 334851
Т.е. для Java — скорее, самым адекватным остается простой прямой цикл, хотя разница где-то на полпроцента-процент.
Байткод для первого варианта занимает 23 байта (19 инструкций), для второго — 24 байта (20 инструкций), для третьего — 22 байта (18 инструкций). С точки зрения JVM «if_icmplt» и «ifge», видимо, работают одинаково.
я анализировал байткод два года назад тут:
blogs.mail.ru/corp/bachin/5D31118461B9C125.html
(по размеру для меня важнее, чем по скорости, но про скорость не забываю)
Кстати, JVM бывают разные… весьма разные…
blogs.mail.ru/corp/bachin/5D31118461B9C125.html
(по размеру для меня важнее, чем по скорости, но про скорость не забываю)
Кстати, JVM бывают разные… весьма разные…
> я покажу, как… в несколько десятков раз.
>…
> Выводы
>…
> быстрее в 10 раз
В чем-то заядлые программисты схожи с заядлыми рыбаками…
Соблазн велик, но надо себя сдерживать. :)
>…
> Выводы
>…
> быстрее в 10 раз
В чем-то заядлые программисты схожи с заядлыми рыбаками…
Соблазн велик, но надо себя сдерживать. :)
Статья отличная.
Речь идёт о алгоритме.
Спасибо, исправил. Осталось от старого варианта топика, где детально рассматривались еще более ужасные с точки зрения производительности способы — в частности, если делать getBytes в windows-1251, производительность падает до ~120000 строчек в секунду. Таким образом разброс между «самым худшим» и «самым лучшим» вариантом действительно начинает быть где-то в ~40 раз, но я посчитал, что приводить тучу вариантов с заведомо худшими результатами не стоит — и так много получилось — ограничился их упоминаниями %)
UFO just landed and posted this here
Такое ощущение, что вы не читали текста.
Эта проблема применима даже к ассемблеру.
Эта проблема применима даже к ассемблеру.
UFO just landed and posted this here
Очень мало есть в жизни по-настоящему критичных вещей.
Топик как раз о том, что «и из пустой бутылки водки можно при желании выжать еще десять-двенадцать капель». Делать это или не делать — решает каждый сам исходя из собственных соображений.
Топик как раз о том, что «и из пустой бутылки водки можно при желании выжать еще десять-двенадцать капель». Делать это или не делать — решает каждый сам исходя из собственных соображений.
Опять-же, лучше надо читать.
Это обычное такое бутылочное горлышка, и обычная такая оптимизация. Если речь идет о скорости — скорее всего таких встретится далеко не одно.
Если же говорить о конкретно этой проблеме:
Изначальный вариант был коряв в том плане, что регэксп не компилировался. Это — большая и очевидная ошибка программиста.
Второй момент, на который стоит обратить внимание — то, что мы делаем не обычную замену, а замену на подстроку, которая по размерам не превосходит заменяемой подстроки. Казалось бы, разница не велика, но это позволяет хорошо экономить на преаллокации(А если можно работать деструктивно, то мы можем вообще не преаллоцировать, а переписывать инплэйс.). На мой взгляд, в библиотеки стоило бы ввести стандартные функции замены на меньшую подстроку и замены на пустую строку. Это хорошая оптимизация, но для каждого конкретного случая писать такую функцию — немного оверкилл. Так что, как я уже сказал, я считаю, что такие должны быть в стандартных библиотеках.
Ну и последнее — это, собственно, использование регэкспов. Тут все зависит от окружениях. На многих виртуальных машинах регэкспы легко переплевывают всякие хитрые махинации с байтами. Если говорить конкретно о C++, то регэксп не получает никаких преимуществ по сравнению с вашим собственном кодом и врядли найдутся случаи, где такие простые обработки строк регэкспами будут быстрее, чем самописный вариант(даже в случае достаточно кривых рук). Но тут, опять-же, стоит подумать о том, что простых обработок строк не так уж и много, так что по-хорошему это пишется один раз, кладется в библиотеку и потом радостно используется.
Это обычное такое бутылочное горлышка, и обычная такая оптимизация. Если речь идет о скорости — скорее всего таких встретится далеко не одно.
Если же говорить о конкретно этой проблеме:
Изначальный вариант был коряв в том плане, что регэксп не компилировался. Это — большая и очевидная ошибка программиста.
Второй момент, на который стоит обратить внимание — то, что мы делаем не обычную замену, а замену на подстроку, которая по размерам не превосходит заменяемой подстроки. Казалось бы, разница не велика, но это позволяет хорошо экономить на преаллокации(А если можно работать деструктивно, то мы можем вообще не преаллоцировать, а переписывать инплэйс.). На мой взгляд, в библиотеки стоило бы ввести стандартные функции замены на меньшую подстроку и замены на пустую строку. Это хорошая оптимизация, но для каждого конкретного случая писать такую функцию — немного оверкилл. Так что, как я уже сказал, я считаю, что такие должны быть в стандартных библиотеках.
Ну и последнее — это, собственно, использование регэкспов. Тут все зависит от окружениях. На многих виртуальных машинах регэкспы легко переплевывают всякие хитрые махинации с байтами. Если говорить конкретно о C++, то регэксп не получает никаких преимуществ по сравнению с вашим собственном кодом и врядли найдутся случаи, где такие простые обработки строк регэкспами будут быстрее, чем самописный вариант(даже в случае достаточно кривых рук). Но тут, опять-же, стоит подумать о том, что простых обработок строк не так уж и много, так что по-хорошему это пишется один раз, кладется в библиотеку и потом радостно используется.
Я сильно не соглашусь в том, что некэширующийся скомпилированный вариант регэкспа — это *ошибка*. У первого варианта — собственно, почему я его показал и показал всякие другие варианты — есть один огромный плюс — он очень читаемый и занимает всего одну строчку. Любому программисту, хоть немножко знакомого с Java, или вообще любому программиста, представляющему в общих чертах регэкспы и знающего 2 английских слова «replace» и «all», можно показать этот код и он поймет, что там происходит. Этот код быстро писать, его быстро читать, он занимает мало места и понятен. Его абсолютно не жалко выкинуть и заменить на что-то совсем другое. Я всеми руками за такой код — до тех пор, пока это не критично с точки зрения производительности.
Рассуждения про строки и регэкспы — я с вами соглашусь, но, к сожалению, эти рассуждения более относятся к C/C++, нежели к managed языкам. В подавляющем большинстве современных фреймворков (Java-based, .NET-based, практически во всех скриптовых языках) строки — immutable объекты. Соответственно, они обычно банально инкапсулируют что-то типа вектора целых чисел и доступ к внутренностям этого вектора для внешних классов сознательно очень сильно ограничен. Весь смысл топика — показать то, как можно используя «мягкие» операции доступа до внутренностей этого вектора пытаться писать эффективные алгоритмы. Для того же .NET, например, результат может быть прямо противоположный (хотя альтернативы по сути очень похожие) — может быть там действительно регэкспы дадут наилучшую производительность.
Рассуждения про строки и регэкспы — я с вами соглашусь, но, к сожалению, эти рассуждения более относятся к C/C++, нежели к managed языкам. В подавляющем большинстве современных фреймворков (Java-based, .NET-based, практически во всех скриптовых языках) строки — immutable объекты. Соответственно, они обычно банально инкапсулируют что-то типа вектора целых чисел и доступ к внутренностям этого вектора для внешних классов сознательно очень сильно ограничен. Весь смысл топика — показать то, как можно используя «мягкие» операции доступа до внутренностей этого вектора пытаться писать эффективные алгоритмы. Для того же .NET, например, результат может быть прямо противоположный (хотя альтернативы по сути очень похожие) — может быть там действительно регэкспы дадут наилучшую производительность.
Разницы между компиляцией регэкспа и использованиеем, и реплэйс олл — 1 строка. В первом случае четко прослеживается логика, во втором нет (Для меня replaceAll неочевидна, я от такой функции ожидаю строковую замену, а не регэксповую.).
Наверное, это в некоторой степени вопрос предпочтений, но если код не для тулзы на 2 раза, использование регэкспов без прекомпиляции в циклах считал и буду считать ошибкой. Конечно, не всегда это сильно влияет на скорость исоплнения, но не вижу никаких причин искусственно замедлять софт, пусть даже и лишь на десяток миллисекунд(которые, кстати, из-за количества запусков могут вылиться в достаточно продолжительные промежутки времени). В этом вопросе я заодно с пользователями — чем быстрее работает софт, тем лучше.
Наверное, это в некоторой степени вопрос предпочтений, но если код не для тулзы на 2 раза, использование регэкспов без прекомпиляции в циклах считал и буду считать ошибкой. Конечно, не всегда это сильно влияет на скорость исоплнения, но не вижу никаких причин искусственно замедлять софт, пусть даже и лишь на десяток миллисекунд(которые, кстати, из-за количества запусков могут вылиться в достаточно продолжительные промежутки времени). В этом вопросе я заодно с пользователями — чем быстрее работает софт, тем лучше.
Ну, на самом деле 1 против 3, плюс одна из этих строчек должна быть вынесена куда-то сильно далеко от кода — как правило, на уровень статических переменных или конструктора. И в туче языков и фреймворков — константный регэксп найдется на этапе компиляции и будет вынесен за скобки автоматически — так что ручная его прекомпиляция не даст фактически ничего.
Вот пример для perl:
Если не знать, что он выдаст — то результаты, скорее всего, будут прямо противоположные тому, что можно было подумать. Так что да — скорее вопрос предпочтений.
А пользователи — это такие странные зверьки. Им зачастую надо не «чем быстрее, тем лучше», а «чем раньше, тем лучше», «подешевле», «попроще» и т.п.
Вот пример для perl:
use Benchmark qw(:all);
$precomp = qr/([0-9]+)/;
cmpthese(1000000, {
'simple' => sub { 'Sample 123 numbers' =~ /([0-9]+)/; },
'precompiled' => sub { 'Sample 123 numbers' =~ $precomp; },
});
Если не знать, что он выдаст — то результаты, скорее всего, будут прямо противоположные тому, что можно было подумать. Так что да — скорее вопрос предпочтений.
А пользователи — это такие странные зверьки. Им зачастую надо не «чем быстрее, тем лучше», а «чем раньше, тем лучше», «подешевле», «попроще» и т.п.
А относительно фреймворков, я написал же, «Тут все зависит от окружениях. На многих виртуальных машинах регэкспы легко переплевывают всякие хитрые махинации с байтами.»
Это *нигде* не является критичным, до тех пор, пока это не жмет. А вот если программа начинает показывать неудовлетворительную производительность и кто-то с профайлером в руках не доказал, что проблема именно в одной этой строчке — то имеет смысл оптимизировать.
Если же это не так — то решение в одну строчку всегда априори лучше, читабельнее, понятнее, не-жалко-выкинуть и т.д., чем весьма долбанутое решение на двадцать строчек.
Если же это не так — то решение в одну строчку всегда априори лучше, читабельнее, понятнее, не-жалко-выкинуть и т.д., чем весьма долбанутое решение на двадцать строчек.
Автор, как заметили выше, прогоните на вашем наборе тестов вариант оптимизации
У меня вроде получается быстрее. На строках не содержащих управляющих символов таким образом убирается бессмысленное копирование oldChars[x] = oldChars[x]
if (ch >= ' ') {
if (newLen != j) {
oldChars[newLen] = ch;
}
newLen++;
}
У меня вроде получается быстрее. На строках не содержащих управляющих символов таким образом убирается бессмысленное копирование oldChars[x] = oldChars[x]
«Потокобезопасный» вариант сделать довольно просто. Весь алгоритм выносится в отдельный объект, и буфер создается внутри объекта.
Если в каждом потоке создавать свой объект алгоритма и передавать строки в него, то они прекрасно распараллелятся.
И ещё небольшое ускорение. Если строка оказалась длиннее массива, то новый массив можно сохранить для следующих вызовов. И если снова попадется более длинная строка, то память выделять уже не придётся.
class Algoritm{
public char[] buf = new char[1024];
String run(String s){
...
Если в каждом потоке создавать свой объект алгоритма и передавать строки в него, то они прекрасно распараллелятся.
И ещё небольшое ускорение. Если строка оказалась длиннее массива, то новый массив можно сохранить для следующих вызовов. И если снова попадется более длинная строка, то память выделять уже не придётся.
...
if(length > 1024)
buf = new char[length];
char[] oldChars = buf;
...
Встроенные Java regexps, во-первых, имеют долбанутый API (подстрекая тем самым излишне часто компилировать одни и те же выражения), во-вторых, достаточно медленны на таких простых операциях; впрочем, о том, что встроенные Java regexps медленныерегэкспы мадленные не в Ява, а сами по себе, будь то РНР или С… например, для усокрения регэкспов придуманы всякие кодогенераторы, типа habrahabr.ru/blogs/regex/117843/ или
Регэкспы медленные не сами по себе (сами по себе регулярные выражения, будучи регулярными, обрабатываются детерминированными конечными автоматами, про оптимизацию и быстрое выполнение которых написаны многие тонны литературы). И для Java, и для C, и, я догадываюсь, для практически всего, что угодно, вполне можно сделать быстрый движок — разумеется, в первую очередь за счет куда большего объема памяти и времени компиляции регулярного выражения.
То, что вы показали «для ускорения» — по сути и есть довольно банальный компилятор регэкспа сразу в C-код. Если уж говорить о сверхскорострельных регэкспах — то рекомендую посмотреть Pire — такая сверхоптимизированная C-библиотека, позволяет добиваться скоростей в сотни мегабайт в секунду.
Если говорить о Java — то, опять же, если верить приведенной выше ссылке — 6556ms на Sun-овской реализации из стандартных библиотек легко сокращаются до 11ms (т.е. становится в ~600 раз быстрее) при использовании библиотек gnu.rex.Rex.
То, что вы показали «для ускорения» — по сути и есть довольно банальный компилятор регэкспа сразу в C-код. Если уж говорить о сверхскорострельных регэкспах — то рекомендую посмотреть Pire — такая сверхоптимизированная C-библиотека, позволяет добиваться скоростей в сотни мегабайт в секунду.
Если говорить о Java — то, опять же, если верить приведенной выше ссылке — 6556ms на Sun-овской реализации из стандартных библиотек легко сокращаются до 11ms (т.е. становится в ~600 раз быстрее) при использовании библиотек gnu.rex.Rex.
на Си задача решилась бы просто и малой кровью,
то что можно распараллелить и на этом выиграть — ежу понятно.
наверняка есть бинд из Java в Си (раньше, когда я изучал Java он был).
так что, если надо — пишем небольшую Сишную программульку и вызываем ее из Java
Прирост производительности будет еще больше :) раза в три по сравнению с последним вариантом
я не Java программист, а РНРник. но если мне нужны производительные вычисления,
или какая-то хитрая функция, то я их всегда реализую на С и вызываю это из языка более высокого уровня.
то что можно распараллелить и на этом выиграть — ежу понятно.
наверняка есть бинд из Java в Си (раньше, когда я изучал Java он был).
так что, если надо — пишем небольшую Сишную программульку и вызываем ее из Java
Прирост производительности будет еще больше :) раза в три по сравнению с последним вариантом
я не Java программист, а РНРник. но если мне нужны производительные вычисления,
или какая-то хитрая функция, то я их всегда реализую на С и вызываю это из языка более высокого уровня.
Прочитайте топик, пожалуйста? И про параллелизацию, и про «давайте сделаем все на JNI» (это и есть упомянутый вами «бинд из Java в Си») — там всё есть. И речь как раз о том, что можно сделать не прибегая к такому ядерному оружию.
Есть, кстати, еще один забавный вариант — почему-то про него никто не сказал, хотя он тоже как бы нелегитимен — можно с помощью reflection лазать во внутренние структуры Java, в том числе получить доступ к полю value объекта String — который и есть искомый char[].
Есть, кстати, еще один забавный вариант — почему-то про него никто не сказал, хотя он тоже как бы нелегитимен — можно с помощью reflection лазать во внутренние структуры Java, в том числе получить доступ к полю value объекта String — который и есть искомый char[].
Кстати не факт что вызов getChars выделение массива чаров и конструирование новой строки будет медленней чем игры с рефлекшн
Более того, этот вариант совсем не подходит. Посмотрите на конструктор копирования строк (public String(String original)) — он по возможности пытается использовать внутренний value строки параметра, т.е. нарушая контракт string-immutable можно очень интересные баги получить.
Разумеется, можно. Разумеется, этим надо пользоваться очень аккуратно — он там не зря сделан immutable и private %) Но ускорение оно дает.
Мой предыдущий ответ почему-то сюда ушел, извиняюсь.
Мой предыдущий ответ почему-то сюда ушел, извиняюсь.
Я уже подумываю на самом деле еще один топик написать с такими «запрещенными» приемами. Игры с reflection дают еще ~+30% производительности. Реализация на JNI дает на самом деле тоже рост от 50 до 100%… И т.д.
Возможно, будет еще немного быстрее, если не копировать массив символов (getChars на самом деле вызвает System.arraycopy), а использовать String.charAt()
Еще быстрее нужно — меняйте архитектуру. Почему у вас передаются строки, а не массивы символов? Или хотя бы Stream-ы.
Еще быстрее нужно — меняйте архитектуру. Почему у вас передаются строки, а не массивы символов? Или хотя бы Stream-ы.
Это был «вариант номер 5», на самом деле. Я тут все-таки взял все предложенные варианты, перемерял еще раз в нескольких режимах и думаю еще одну статью с более детальными исследованиями, цифрами и графиками сделать…
Да, Вы правы про charAt.
И все же, почему String? Почему не char[] или не Reader? Ведь, по сути, вы свели весь функционал String-а к хранению массива символов.
В целом, «правильным» было бы реализовать подкласс FilterReader и фильтровать символы в нем. Оно будет медленнее C-style решения, но универсальней. Понятно, что все зависит от задачи и выбранной архитектуры.
И все же, почему String? Почему не char[] или не Reader? Ведь, по сути, вы свели весь функционал String-а к хранению массива символов.
В целом, «правильным» было бы реализовать подкласс FilterReader и фильтровать символы в нем. Оно будет медленнее C-style решения, но универсальней. Понятно, что все зависит от задачи и выбранной архитектуры.
Потому что эта функциональность — лишь маленькая часть огромного комплекса. В той же парадигме кроме этой задачи работают еще сотня-другая других задач — в том числе с совершенно другими алгоритмами и сложностями. Да даже в этой задаче, кроме собственно фильтрации выходного потока (что, кстати, тоже само по себе не так тривиально — в выходном потоке там набор объектов, среди которых *иногда* встречаются String, которые надо фильтровать, иногда встречаются примитивы типа int / double, которые надо выводить как есть, а иногда — всякие другие сложные объекты типа tuples / maps, которые надо выводить еще сложнее.
Если говорить о «концах» этой задаче — т.е. «читалке» и «писалке» — то, зря в корень, читалка «читает» именно String, а не char[] и не byte[], потому что в исходном потоке приходит именно String. Может прийти и char[], но в этом случае на выходе он будет обработан еще более банально и просто (hex dump'ом). А посередине может быть алгоритм, который захочет этому String сделать какую-то именно строковую операцию, характерную для этого класса…
Если говорить о «концах» этой задаче — т.е. «читалке» и «писалке» — то, зря в корень, читалка «читает» именно String, а не char[] и не byte[], потому что в исходном потоке приходит именно String. Может прийти и char[], но в этом случае на выходе он будет обработан еще более банально и просто (hex dump'ом). А посередине может быть алгоритм, который захочет этому String сделать какую-то именно строковую операцию, характерную для этого класса…
Sign up to leave a comment.
Как убрать все управляющие символы из строки — история одной бурной оптимизации