c++ - 优化 WordWrap 算法

Question

我有一个自动换行算法，基本上可以生成适合文本宽度的文本行。不幸的是，当我添加太多文本时它会变慢。

我想知道我是否监督了可以进行的任何重大优化。此外，如果任何人的设计仍然允许更好的行字符串或行字符串指针，我愿意重写算法。

谢谢

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();
}

Answer 1

我认为有两个主要因素使它比它可能的慢。

第一个，可能不太重要:在构建每一行时，您是在向该行添加单词。每个这样的操作都可能需要重新分配该行并复制其旧内容。对于长线，这是低效的。但是，我猜测在实际使用中你的行很短(比如 60-100 个字符)，在这种情况下成本不太可能很大。尽管如此，还是有可能提高效率。

第二个，可能更重要:您显然将其用于某种 GUI 中的文本区域，我猜它正在被输入。如果您要为输入的每个字符重新计算，那么一旦文本变长，那真的会很痛苦。

只要用户只在末尾添加字符——这肯定是最常见的情况——你就可以有效地利用这样一个事实，即通过你的“贪心”换行算法，更改永远不会影响前面的任何内容行:所以只需从最后一行的开头重新计算。

如果您希望即使用户在文本中间某处键入(或删除或其他)时也能快速完成，您的代码将需要做更多工作并存储更多信息。例如:每当你构建一行时，记住“如果你以这个单词开始一行，它以那个单词结束并且这个是整个结果线”。当该行内发生任何更改时，使此信息无效。现在，经过一些编辑后，大多数更改都不需要重新计算。您应该自己弄清楚这方面的细节，因为 (1) 这是一项很好的锻炼，并且 (2) 我现在需要去 sleep 了。

(为了节省内存，您可能更愿意根本不存储整行——无论您是否实现我刚才描述的那种技巧。相反，只需存储这里的下一个换行符信息并构建根据您的 UI 需要渲染它们来设置行。)

它可能比您现在想接受的要复杂得多，但您还应该查看 Donald Knuth 的基于动态规划的换行算法。它比你的要复杂得多，但仍然可以非常快地完成，而且它会产生明显更好的结果。参见，例如 http://defoe.sourceforge.net/folio/knuth-plass.html .