Эффективная конкатенация строк в C++
Использование Ramda,
npm установка ramda
import R from 'ramda'
var objs = [
{ first_nom: 'Lazslo', last_nom: 'Jamf' },
{ first_nom: 'Pig', last_nom: 'Bodine' },
{ first_nom: 'Pirate', last_nom: 'Prentice' }
];
var ascendingSortedObjs = R.sortBy(R.prop('last_nom'), objs)
var descendingSortedObjs = R.reverse(ascendingSortedObjs)
9 ответов
дополнительная работа, вероятно, не стоит того, если Вам действительно действительно не нужна эффективность. у Вас, вероятно, будет намного лучшая эффективность просто при помощи оператора + = вместо этого.
Теперь после той правовой оговорки, я отвечу на Ваш фактический вопрос...
эффективность строкового класса STL зависит от реализации STL, который Вы используете.
Вы могли , эффективность гарантии и имеет больший контроль сами путем выполнения конкатенации вручную через c встроенные функции.
, Почему оператор + не эффективен:
Смотрят на этот интерфейс:
template <class charT, class traits, class Alloc>
basic_string<charT, traits, Alloc>
operator+(const basic_string<charT, traits, Alloc>& s1,
const basic_string<charT, traits, Alloc>& s2)
Вы видите, что новый объект возвращается после каждого +. Это означает, что новый буфер используется каждый раз. При выполнении тонны дополнительных + операции, это не эффективно.
, Почему можно сделать это более эффективным:
- Вы гарантируете эффективность вместо того, чтобы доверять делегату, чтобы сделать это эффективно для Вас
- станд.:: строковый класс ничего не знает о макс. размере Вашей строки, ни как часто Вы будете конкатенировать к нему. Вы можете иметь это знание и можете сделать вещи на основе наличия этой информации. Это приведет к меньшему количеству перераспределений.
- Вы будете управлять буферами вручную, таким образом, можно будет быть уверены, что Вы не скопируете целую строку в новые буферы, когда Вы не захотите, чтобы это произошло.
- можно использовать стек для буферов вместо "кучи", которая намного более эффективна.
- строка + оператор создаст новый строковый объект и возвратит ее следовательно использование нового буфера.
Соображения для реализации:
- Отслеживают длину строки.
- Сохраняют указатель до конца строки и запуска или просто запуска и используют запуск + длина как смещение для нахождения конца строки.
- Удостоверяются буфер, в котором Вы храните свою строку, является достаточно большим, таким образом, Вы не должны перераспределять данные
- Использование strcpy вместо strcat, таким образом, Вы не должны выполнять итерации по длине строки для нахождения конца строки.
структура данных Веревки:
, Если Вам нужны действительно быстрые конкатенации, рассматривают использование структура данных веревки .
Зарезервируйте свое заключительное пространство прежде, затем используйте добавлять метод с буфером. Например, скажите, что Вы ожидаете, что Ваша заключительная длина строки будет 1 миллионом символов:
std::string s;
s.reserve(1000000);
while (whatever)
{
s.append(buf,len);
}
Я не волновался бы об этом. Если Вы сделаете это в цикле, то строки будут всегда предварительно выделять память для уменьшения перераспределений - просто используют operator+= в этом случае. И если Вы делаете это вручную, что-то вроде этого, или дольше
a + " : " + c
Тогда это создает временные файлы - даже если компилятор мог бы устранить некоторые копии возвращаемого значения. Это вызвано тем, что в последовательно названном operator+ это не знает, ссылается ли параметр ссылки на именованный объект, или временный файл возвратился из вызова sub operator+. Я не волновался бы об этом прежде не представил сначала. Но давайте возьмем пример для показа этого. Мы сначала представляем круглые скобки, чтобы ясно дать понять привязку. Я поместил аргументы непосредственно после объявления функции, это используется для ясности. Ниже этого я показываю, каково получающееся выражение тогда:
((a + " : ") + c)
calls string operator+(string const&, char const*)(a, " : ")
=> (tmp1 + c)
Теперь, в том дополнении, tmp1 то, что было возвращено первым вызовом к оператору + с показанными аргументами. Мы предполагаем, что компилятор действительно умен и оптимизирует копию возвращаемого значения. Таким образом, мы заканчиваем с одной новой строкой, которая содержит конкатенацию a и " : ". Теперь, это происходит:
(tmp1 + c)
calls string operator+(string const&, string const&)(tmp1, c)
=> tmp2 == <end result>
Сравнивают это со следующим:
std::string f = "hello";
(f + c)
calls string operator+(string const&, string const&)(f, c)
=> tmp1 == <end result>
Это использует ту же функцию для временного файла и для именованной строки! Таким образом, компилятор имеет , чтобы скопировать аргумент в новую строку и добавить к этому и возвратить его из тела [1 111]. Это не может взять память временного файла и добавить к этому. Чем больше выражение, тем должно быть сделано больше копий строк.
Следующая Visual Studio и GCC будут поддерживать C++ 1x's семантика перемещения (дополнение семантика копии ) и rvalue ссылки как экспериментальное дополнение. Это позволяет выяснять, ссылается ли параметр на временный файл или нет. Это сделает такие дополнения удивительно быстро, поскольку все вышеупомянутое закончится в одном "добавлять-конвейере" без копий.
, Если это оказывается узким местом, можно все еще сделать
std::string(a).append(" : ").append(c) ...
append, вызовы добавляют аргумент [1 113] и затем возвращают ссылку на себя. Таким образом, никакое копирование временных файлов не сделано там. Или альтернативно, эти operator+= может использоваться, но Вам были бы нужны ужасные круглые скобки для фиксации приоритета.
Для большинства приложений это просто не будет иметь значения. Просто напишите свой код, в блаженном неведении о том, как точно + работы оператора, и только берут дело в свои руки, если это становится очевидным узким местом.
В отличие от Системы.NET. Строки, станд. C++:: строки изменяемы, и поэтому могут быть созданы посредством простой конкатенации настолько же быстро как через другие методы.
В Несовершенный C++ , Matthew Wilson представляет динамичный строка concatenator, который предварительно вычисляет длину заключительной строки, чтобы иметь только одно выделение прежде, чем связать все части. Мы можем также реализовать статический concatenator путем игры с шаблоны выражения .
Такая идея были реализованы в станд. STLport:: строковая реализация - который не соответствует стандарту из-за этого точного взлома.
возможно, станд.:: stringstream вместо этого?
, Но я соглашаюсь с чувством, что необходимо, вероятно, просто сохранить его удобным в сопровождении и понятным и затем представить, чтобы видеть, есть ли у Вас действительно проблемы.
Как с большинством вещей, легче не сделать что-то, чем сделать это.
, Если Вы хотите произвести большие строки к GUI, может случиться так, что независимо от того, что Вы производите к, может обработать строки в частях лучше, чем как большая строка (например, связывая текст в текстовом редакторе - обычно они сохраняют строки как отдельные структуры).
, Если Вы хотите произвести в файл, передайте данные потоком вместо того, чтобы создать большую строку и произвести это.
я никогда не находил потребность сделать конкатенацию быстрее необходимой, если я удалил ненужную конкатенацию из медленного кода.
Для маленьких строк это не имеет значения. Если у Вас есть большие строки, Вы были бы лучше для хранения их, как они находятся в векторе или в некотором другом наборе как части. И addapt Ваш алгоритм для работы с таким набором данных вместо одной большой строки.
я предпочитаю станд.:: ostringstream для сложной конкатенации.