Оптимизация Алгоритма Перенос Слов


У меня есть слово-обернуть алгоритм, который в основном формирует строк текста по ширине текста. К сожалению, это становится медленным, когда я добавляю слишком много текста.

Мне было интересно, если я наблюдал каких-либо серьезных оптимизаций, которые могут быть сделаны. Также, если у кого есть такой дизайн, который будет по-прежнему позволяют строки строки или строки указатели линий, что лучше я буду открыт для переписывания алгоритма.

Спасибо

void AguiTextBox::makeLinesFromWordWrap()
{
    textRows.clear();
    textRows.push_back("");
    std::string curStr;
    std::string curWord;

    int curWordWidth = 0;
    int curLetterWidth = 0;
    int curLineWidth = 0;

    bool isVscroll = isVScrollNeeded();
    int voffset = 0;
    if(isVscroll)
    {
        voffset = pChildVScroll->getWidth();
    }
    int AdjWidthMinusVoffset = getAdjustedWidth() - voffset;
    int len = getTextLength();
    int bytesSkipped = 0;
    int letterLength = 0;
    size_t ind = 0;

    for(int i = 0; i < len; ++i)
    {

        //get the unicode character
        letterLength = _unicodeFunctions.bringToNextUnichar(ind,getText());
        curStr = getText().substr(bytesSkipped,letterLength);


        bytesSkipped += letterLength;

        curLetterWidth = getFont().getTextWidth(curStr);

        //push a new line
        if(curStr[0] == '\n')
        {
            textRows.back() += curWord;
            curWord = "";
            curLetterWidth = 0;
            curWordWidth = 0;
            curLineWidth = 0;
            textRows.push_back("");
            continue;
        }



            //ensure word is not longer than the width
            if(curWordWidth + curLetterWidth >= AdjWidthMinusVoffset && 
                curWord.length() >= 1)
            {
                textRows.back() += curWord;

                textRows.push_back("");
                curWord = "";
                curWordWidth = 0;
                curLineWidth = 0;
            }

            //add letter to word
            curWord += curStr;
            curWordWidth += curLetterWidth;


        //if we need a Vscroll bar start over
        if(!isVscroll && isVScrollNeeded())
        {
            isVscroll = true;
            voffset = pChildVScroll->getWidth();
            AdjWidthMinusVoffset = getAdjustedWidth() - voffset;
            i = -1;
            curWord = "";
            curStr = "";
            textRows.clear();
            textRows.push_back("");
            ind = 0;

            curWordWidth = 0;
            curLetterWidth = 0;
            curLineWidth = 0;

            bytesSkipped = 0;
            continue;
        }

        if(curLineWidth + curWordWidth >= 
            AdjWidthMinusVoffset && textRows.back().length() >= 1)
        {
            textRows.push_back("");
            curLineWidth = 0;
        }

        if(curStr[0] == ' ' || curStr[0] == '-')
        {
            textRows.back() += curWord;
            curLineWidth += curWordWidth;
            curWord = "";
            curWordWidth = 0;
        }
    }

    if(curWord != "")
    {
        textRows.back() += curWord;
    }

    updateWidestLine();
}


1976
6
задан 16 марта 2011 в 11:03 Источник Поделиться
Комментарии
2 ответа

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

Профиль ваш код

Вы не можете надеяться, чтобы сделать вещи быстрее упорядоченно, не узнав, какие части занимают больше всего времени. Да, вы можете разработать более быстрый алгоритм, но вы могли бы в конечном итоге тратить несколько дней на оптимизацию алгоритма о(N^2) до o(зарегистрируйте n), только чтобы узнать, что часть все равно взял 1мс.

Сначала каждое слово

Если вы разделяете только на границах слов, вы можете также искать вперед за рубежа и извлечь подстроку в один звонок.

Рассчитать словом ширины вместо буквы Ширин

Во-первых, когда я писал подобную функцию в Java много лет назад, стоимость вызова расчета ширины строки имел достаточно высокие накладные расходы, которые не меняются с длиной строки. Получение ширины персонаж в то время был значительно более дорогостоящим, чем вычисление длины слова. Кроме того, поскольку там может быть вовлечен Кернинг, который регулирует расстояние между буквами, основанные на пары букв, вы не сможете добавить до ширины символов, чтобы прибыть в машинном слове.

Если вы в конечном итоге нужно разделить слова на полпути, использовать бинарный поиск, чтобы найти точку отсечки

Это идет с двумя выше, но вы не знаете оптимальный путь до профиля.

Убедитесь, что вы не используя связанный список

Добавить строку в список (вектор?) и изменять его для каждого персонажа. Если это связанный список вместо массива, то это будет очень дорого. Я не очень хорошо знаком с STL, если это то, что вы используете (эти декларации поможет), так что, возможно, он сохраняет указатель хвоста. В любом случае, я хотел бы построить в каждой строке и добавить его в список только после его завершения, даже если вы используете массив на основе вектора. Это только кажется чище.

Показать полосу прокрутки отключен, а не перезапуск, как только вы определить, что перечислять надо

Действительно, полоса прокрутки отключена, разве это не ужасно. ;)

Рассчитать самую широкую линию, как вы обернуть

Я уверен, что работа, проделанная в updateWidestLine() очень похож на то, что вы уже делаете в makeLinesFromWordWrap(). Воспользоваться этим и поддерживать maxlength значение локальной переменной, как вы делаете обертывание.

4
ответ дан 17 марта 2011 в 01:03 Источник Поделиться

Одно очевидное улучшение будет хранить массив точек разделения вместо текстовых строк. Скажем, у нас есть эта строка:

This is some text

Мы находим точку разрыва между "некоторые" и "текст". В этом алгоритме, у вас есть следующая хранимая:

Original string = "This is some text"
textRows[0] = "This is some"
textRows[1] = "text"

Повторение не нужно и создании textRows вектор включает в себя много бессмысленного копирования строк. Было бы лучше вместо магазина это:

Original string = "This is some text"
textSplit[0] = 12
textSplit[1] = 16

Для печати текста:

lastSplit = 0
for i = 0 to len(textSplit)
print original text from lastSplit to textSplit[i]
print linebreak
lastSplit = textSplit[i]

4
ответ дан 17 марта 2011 в 10:03 Источник Поделиться