std :: vector push_back является узким местом

Question

Вот что делает мой алгоритм: Он берет длинный std :: string и делит его на слова и подслову, если он больше ширины:

inline void extractWords(std::vector<std::string> &words, std::string &text,const AguiFont &font, int maxWidth)
{


    words.clear();

    int searchStart = 0;
    int curSearchPos = 0;
    char right;
    for(size_t i = 0; i < text.length(); ++i)
    {
        curSearchPos = i;

        //check if a space is to the right
        if( i == text.length() - 1)
            right = 'a';
        else
            right = text[i + 1];

        //sub divide the string if it;s too big
        int subStrWidth = 0;
        int subStrLen = 0;
        for(int x = searchStart; x < (curSearchPos - searchStart) + 1; ++x)
        {
            subStrWidth += font.getTextWidth(&text[x]);
            subStrLen ++;
        }
        if(subStrLen > maxWidth && subStrLen > 1)
        {
            for(int k = 2; k <= subStrLen; ++k)
            {
                subStrWidth = 0;
                for(int p = 0; p < k; ++p)
                {
                    subStrWidth += font.getTextWidth(&text[searchStart + p]);
                }
                if(subStrWidth > maxWidth)
                {
                    searchStart += k - 1;

                    words.push_back(text.substr(searchStart,k - 1));
                    break;

                }
            }
        }

        //add the word
        if((text[i] == ' ' && right != ' ' ) || i == text.length() - 1)
        {

                if(searchStart > 0)
                {
                    words.push_back(text.substr(searchStart ,(curSearchPos - searchStart) + 1));

                }
                else
                {
                    words.push_back(text.substr(0 ,(curSearchPos - searchStart) ));
                    words.back() += text[curSearchPos];

                }

            searchStart = i + 1 ;
        }
    }


}

Как вы видите, я использую std :: vectors для добавления своих слов. Вектор дается ссылкой. Этот std :: vector является статическим и находится в процедуре, которая вызывает extractWord. Как ни странно, статичность привела к гораздо большему потреблению процессора. После профилирования я увидел, что я делаю много выделений кучи, но я не знаю почему, поскольку std :: vector должен сохранять свои элементы даже после очистки вектора. Есть ли менее интенсивный способ сделать это? Длина строки неизвестна, равно как и число результирующих строк, поэтому я выбрал std :: vector, но есть ли лучший способ?

Спасибо

* на самом деле я думаю, что моя генерация подстроки - это то, что медленно

Answer 1

Как правило, если добавление элементов в вектор является узким местом, вы должны использовать std::vector<T>::reserve, чтобы заранее зарезервировать некоторое пространство. Это должно снизить вероятность того, что вызов push_back вызовет перераспределение памяти.

Тем не менее, обработка строк в целом может потребовать значительных ресурсов процессора, а перераспределение вектора строковых объектов требует много копирования. Каждый раз, когда вектор перераспределяет память, каждый строковый объект должен быть скопирован в другое место в памяти. (К счастью, это будет существенно уменьшено, как только будут созданы конструкторы перемещения C ++ 0x.)

Кроме того, тот факт, что вы очищаете вектор каждый раз, не меняет того факта, что каждый вызов push_back приводит к копированию строкового объекта в вектор, что, вероятно, является причиной всех выделений кучи, которые вы '' видишь. Не забывайте, что каждый экземпляр std::string должен выделять память в куче для хранения строки.

Answer 2

Код выглядит так, как будто он работает хорошо, но дьявол всегда в деталях, когда дело доходит до производительности.Вот несколько соображений:

1. Попробуйте изменить объявление вектора с:

   с: std :: vector & words
   на: std:: vector & words

   Это создаст указатель и назначит ему адрес строки, а не копирует содержимое каждой строки в вектор.

2. Попробуйте использовать вектор :: резерв для предварительного выделения памяти, необходимой для обработки строки.Грубая оценка может быть text.length () / maxWidth.

3. Обратите особое внимание на используемые строковые операции.Вполне возможно, что существует много временных строк, которые генерируются и сразу выбрасываются.Лучший способ выяснить, происходит ли это, состоит в том, чтобы пройтись по строкам манипуляции со строками и посмотреть, не возникли ли дополнительные строковые конструкторы и конструкторы копирования.

Answer 3

Во-первых, вы должны рассмотреть возможность передачи выходного итератора вместо vector&. Это привело бы к более чистой и более гибкой конструкции.

Определение clear() не дает никаких гарантий об использовании памяти. Реализация имеет полное право освободить всю использованную память, когда вы вызываете clear. Это вполне может быть реализовано так:

void clear() { vector tmp; swap(tmp); }

Возможно, вам повезет, позвонив resize(0) вместо clear(), но даже это не требуется для сохранения емкости вектора.

Если вы действительно хотите уничтожить все эти выделения памяти:

1. Определите функцию как шаблонную функцию с выходным итератором, как я предлагал выше, также передавая предел количества.
2. Передайте обычный старый C-массив, достаточно большой, чтобы вместить максимальное количество слов, которое вы ожидаете увидеть.
3. Используйте std::pair<const char*, const char*> вместо std::string для хранения найденных слов.

Answer 4

Вы можете переключиться на вектор, который косвенно содержит строки. Тогда строки не копируются при каждом изменении размера хранилища, копируются только «дескрипторы». Так что вместо std::vector<std::string> &words что-то более похожее на std::vector< counted_ptr<std::string> > &words. Затем посмотрите эту статью доктора Добба, чтобы узнать больше о countted_ptr <>.

Кроме того, чтобы избежать потенциальной погони за Гейзенбагом, auto_ptr <> - это , а не , что вы хотите использовать для такого рода вещей в контейнере STL.

Answer 5

вектор был бы лучшим, если вы знаете количество результирующих строк, а не если вы его не знаете.deque или list сделают лучше.но, возможно, вы можете проверить, какова емкость вектора в начале и каков размер в конце.