优化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个字符），在这种情况下，成本不太可能很高。不过，这里可能会有一些效率。

第二个，也许更重要的是：你显然是在某种图形用户界面中将它用于文本区域，并且我猜测它正在被输入。如果你为每个输入的字符重新计算，那么一旦文本变长，这真的会受到伤害。

只要用户只在最后添加字符 - 这当然是最常见的情况 - 您可以有效地使用这样的事实：使用“贪婪”换行算法更改不会影响任何内容较早的行：只需从最后一行开始重新计算。

如果您希望即使用户在文本中间的某处输入（或删除或任何其他地方）时仍快速运行，您的代码需要做更多工作并存储更多信息。例如：每当你建立一条线时，记住“如果你用这个字开始一行，那么即字，而这个是整个结果行”。当该行内发生任何更改时，使该信息无效。现在，经过一些编辑，大部分更改都不需要重新计算。你应该为自己弄清这个细节，因为（1）这是一个很好的练习，（2）我现在需要去睡觉。 （为了节省内存，你可能不希望存储整行代码 - 不管你是否实现了我刚才描述的那种技巧，而只是存储这里的下一行代码信息和当你的用户界面需要渲染它们时建立线条。）

这可能比你现在想要采用的更复杂，但你也应该查阅Donald Knuth基于动态编程的换行算法。它比你的要复杂得多，但仍然可以很快完成，并且产生明显更好的结果。参见例如，http://defoe.sourceforge.net/folio/knuth-plass.html。

Answer 2

的算法一般变化 -

1. 工作，如果你需要滚动条一样便宜就可以了，即。计算文本中的\ n数量，如果它大于，则vheight打开滚动，检查长度等。
2. 现在您已经知道您需要滚动条或不滚动条，将文本准备到控件的相应行中。

这允许你删除/如运行在几乎每一个字符减少测试if(!isVscroll && isVScrollNeeded()) - isVScroll可能是不吱，示例代码似乎并没有传递线功能的知识，不能看它如何告诉它是否需要。

假设textRows是vector<string> - textrows.back() +=是一种昂贵的，查找后面不是很多+ =字符串不是有效的字符串。我会更改为使用ostrstream收集该行并在完成时将其推入。

getFont（）。getWidth（）可能是昂贵的 - 字体是否改变？固定宽度字体的最小和最大快捷键的宽度差异有多大。

使用本地方法，其中可能的，因为你不希望打破他们得到一个字的大小 - GetTextExtentPoint32

通常情况下，将有足够的空间以允许VSCROLL当你之间切换。从测量开始重新开始可能花费你两倍的时间。用每行存储行的宽度，以便跳过仍然适合的行。 或者不要直接建立行字符串，保持单词与大小分开。

它究竟需要多准确？涂一些务实...
只是假设VSCROLL将是必要的，大多是如果不是（一行在结束1个字母词/启动）

尝试包装甚至不会发生大的变化和用字比用字母更多地工作 - 检查每个字母的剩余空间会浪费时间。假定字符串中的每个字母是最长的字母，字母x最长的空间<然后将其放入。

Answer 3

算法问题通常伴随着数据结构问题。

让我们提出一些意见，第一：

• 段落可以在给定指标
• 编辑在独立处理仅无效当前单词和那些跟随
• 没有必要对整个复制当他们的索引足以用于检索它们并且只有它们的长度对于计算而言是重要的时

段落

我首先介绍段落的概念，这是由用户引入的换行符决定的。当一个版本发生时，你需要找到哪个是有关的段落，这需要查找结构。

这里的“理想”结构应该是一个Fenwick树，但对于一个小文本框来说，这看起来有点矫枉过正。我们只需让每个段落存储组成其表示的显示行数，并从头开始计算。请注意，对最后显示行的访问权限是对最后一段的访问。

段落因此以C++术语作为连续序列存储，很可能采用间接命中（即存储指针）来保存在中间段落被删除时移动它们。

每个段落将存储：

• 它的内容，其中最简单的一个std::string来代表它。
• 其显示，在可编辑的形式（我们需要确定仍然）

每个段落将缓存它的显示，每当编辑由该段高速缓存将失效。

实际渲染将一次只有几个段落（更好，几条显示的行）：可见的。

显示线

甲段是可以显示与至少一条线，但没有最大值。我们需要以可编辑的形式存储“显示”，这是一种适合版本的形式。

投入的单个大块字符\n并不适合。变化意味着移动大量字符，用户假设要改变文字，所以我们需要更好。

使用长度而不是字符，我们可能实际上只存储了4个字节（如果字符串需要超过3GB ...我不能保证太多这个算法）。

我的第一个想法是使用字符索引，但是在编辑的情况下，所有后续索引都会更改，并且传播很容易出错。长度是偏移量，所以我们有一个相对于前一个词的位置的索引。它确实提出了一个词（或标记）是什么的问题。值得注意的是，你是否折叠了多个空格？你如何处理它们？在这里，我假设单词由一个空格分开。

对于“快速”检索，我还将存储整个显示行的长度。这允许在段落的字符503处进行编辑时快速跳过第一显示的行。

甲显示线将由此组成的：

• 的总长度（劣于箱的最大显示长度，一旦计算结束）
• 字序列（令牌）长度

这个序列应该可以在两端有效地进行编辑（因为对于包装，我们会根据编辑添加或删除的文字来推送/弹出文字两端）。如果在中间我们效率不高，这并不重要，因为一次只能编辑一行。

在C++中，vector或deque应该没问题。虽然理论上list将是“完美的”，但在实践中，其糟糕的内存位置和高内存开销将抵消其渐近保证。一条线由几个词组成，所以渐近行为并不重要，高常数也是如此。

渲染

对于渲染，拾取已经足够的长度（一个std::string一起reserve呼叫将做）的缓冲器。通常情况下，你会每次都重写缓冲区，所以不会发生内存分配。

您不需要显示无法看到的内容，但需要知道有多少行，才能选取正确的段落。

一旦你的一段话：

• 设置offset到0
• 隐藏的每一行，增加其长度offset（+ 1后，它的空间）
• 一个字作为访问的_content子串，你可以buffer使用insert方法：buffer.insert(buffer.end(), _content[offset], _content[offset+length])

难度在于维护offset，但这正是使算法高效的原因。

结构

struct LineDisplay: private boost::noncopyable 
{ 
    Paragraph& _paragraph; 
    uint32_t _length; 
    std::vector<uint16_t> _words; // copying around can be done with memmove 
}; 

struct Paragraph: 
{ 
    std::string _content; 
    boost::ptr_vector<LineDisplay> _lines; 
}; 

通过这种结构，实现应该是简单的，尽可能多的在内容的增加不应该慢下来。