優化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; 
}; 

通過這種結構，實現應該是簡單的，儘可能多的在內容的增加不應該慢下來。