Комментарии 32
StringBuilder?
StringBuilder решает этот вопрос немного по другому — он внутри использует unsafe код, а преимущество этого алгоритма в том, что его можно использовать там, где это недопустимо.
Он использует unsafe код потому что можно. Сделать эффективную реализацию StringBuilder можно было и без этого. Кроме того есть string.Join, string.Concat. В целом, в любом нормальном языке (нормальной платформе) есть средства для эффективной склейки строк. Луа тут исключение а не правило.
В Си++ вообще можно извратиться на шаблонах, вычислять результат лениво при приведении типа и вообще много интересных и никому не нужных вещей сделать :-)
В Си++ вообще можно извратиться на шаблонах, вычислять результат лениво при приведении типа и вообще много интересных и никому не нужных вещей сделать :-)
В новых версиях Lua можно делать так:
Этот текст достаточно древен (2002 год), я его перевёл, потому что алгоритм интересен.
local t = {}
for l in ... do
table.insert(t, l)
end
s = table.concat(t)
Этот текст достаточно древен (2002 год), я его перевёл, потому что алгоритм интересен.
Научите: чем вы раскрашиваете синтаксис для постов?
Откройте исходные коды в src.zip в JDK. Нет там ни одного native метода, pure Java.
Спорю на бутылку пива что напишу аналог StringBuffer-а на базе ArrayList за час (знаю медленно, но жарко тут).
НЛО прилетело и опубликовало эту надпись здесь
Как забыть?
Скомпилируется в
Никакой оптимизации, новый StringBuilder объект создается на каждой итерации, причем памяти потребляется O(N2). Память конечно же вычищается, но время на это затрачивается. Или, может быть, вы что-то «такое» знаете про оптимизатор Java 1.5+?
String s = "foo";
for (int i = 0; i < 100500; i++) {
s += "bar";
}
Скомпилируется в
String s = "foo";
for (int i = 0; i < 100500; i++) {
s = new StringBuilder().append(s).append("bar").toString();
}
Никакой оптимизации, новый StringBuilder объект создается на каждой итерации, причем памяти потребляется O(N2). Память конечно же вычищается, но время на это затрачивается. Или, может быть, вы что-то «такое» знаете про оптимизатор Java 1.5+?
Забыть о проблеме, но не о StringBuilder.
String s = «foo»;
StringBuilder sb=new StringBuilder(s);
for (int i = 0; i < 100500; i++) {
sb.append(«bar»);
}
s=sb..toString();
При этом надо понимать, что каждый append увеличивает длину буфера, что в нашем случае приведет к большому числу перевыделений памяти под буффер. Если решается задача, например, рендеринга html страницы, как в jsp, то в качестве представления последовательности символов эффективнее использовать структуры типа ropes, на которые я ниже в комментариях давал ссылку.
Спасибо, принцип понятен, однако, имхо, проблема должна решаться более красивыми функциями в стандартной библиотеке. Вот пример аналогичного кода для питона, который не вызывает таких гигантских накладных расходов:
Этот код:
1) Создаёт объект file (открывает файл на чтение)
2) Создаёт итератор для чтения файла (это происходит потому, что класс file имеет методы для работы в качестве итератора (next,iter)
3) Указанный итератор передаётся в функцию, которая соединяет элементы списка (или итератора, как можно догадаться). Заметим, поскольку функция join морально готова к приёму нескольких строк по-очереди, она не создаёт снова и снова immutable объекты строк, а всего лишь создаёт строку из множества фрагментов, которые ей приходят по-очереди.
Типа так.
''.join(file("myfile",'r'))
Этот код:
1) Создаёт объект file (открывает файл на чтение)
2) Создаёт итератор для чтения файла (это происходит потому, что класс file имеет методы для работы в качестве итератора (next,iter)
3) Указанный итератор передаётся в функцию, которая соединяет элементы списка (или итератора, как можно догадаться). Заметим, поскольку функция join морально готова к приёму нескольких строк по-очереди, она не создаёт снова и снова immutable объекты строк, а всего лишь создаёт строку из множества фрагментов, которые ей приходят по-очереди.
Типа так.
НЛО прилетело и опубликовало эту надпись здесь
Из этого примера не ясно, что надо дальше делать с полученной строкой. Если в дальнейшем нам нужно лишь итерироваться по этой строке, то стек можно и не разворачивать. Или вообще можно использовать Ropes. Кроме того, дополнительный расход памяти на стек O(числа строк в файле), или, по ощущениям, что-то вроде логарифма от числа символов в файле.
НЛО прилетело и опубликовало эту надпись здесь
В начале статьи нужно написать, что алгоритм связан с особенностями lua и ее сборщика мусора
А нельзя-ли просто сложить все прочитанные строки в список или массив, а потом выделить большую строку и все туда скопировать? Потребление памяти х2, зато копирование одно.
Мда, казалось бы, конкатенация строк — древняя задча, за жти годы должна быть изучена досконально, а во многих языках, судя по комментам — не решена (вызывать realloc() на каждое склеивание — никак не тянет на решение). Гораздо правильнее при объдинении просто добавлять кусочки в список, а при попытке прочитать значение строки — склеивать все, что накопилось.
называть это словом «алгоритм» — перебор. скорее это кривохак для обхода особенностей языка программирования
> например, для чтения 350Кб файла требуется почти минута
это невероятно!
1 минута * 1 GHz = 60 секунд * 1 000 000 000 = 60 миллионов тактов процессора.
Делим на 350 Килобайт и получаем результирующее КПД… примерно 171 тысяч тактов процессора на чтение одного байта.
Окей, возьмём «идеальный» алгоритм.
350 Кб за 0.02 сек = 17 500 Кб/с.
Да у меня интернет быстрее, чем чтение с диска в Lua в самой оптимальной реализации.
О чём вообще можно говорить про такую среду исполнения?
Мир сошёл с ума.
это невероятно!
1 минута * 1 GHz = 60 секунд * 1 000 000 000 = 60 миллионов тактов процессора.
Делим на 350 Килобайт и получаем результирующее КПД… примерно 171 тысяч тактов процессора на чтение одного байта.
Окей, возьмём «идеальный» алгоритм.
350 Кб за 0.02 сек = 17 500 Кб/с.
Да у меня интернет быстрее, чем чтение с диска в Lua в самой оптимальной реализации.
О чём вообще можно говорить про такую среду исполнения?
Мир сошёл с ума.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Составление строк из множества частей