0

名前のない言語で書いているプログラムに、幅が不明なテキスト ブロックがあり、このテキスト ブロックの最大幅しかわかりません。この情報を考慮して、このテキストの可能な最小幅を見つける必要があります (文字/グリフまたは文字数のメトリックを使用できないと仮定します)。これまでのところ、次のようなブルー​​トフォースソリューションがあります。

for (int i = .1; i < maxTextWidth; i += .1)
{
       if (textFitsInGivenWidth(text, i))
       {
             textWidth = i;
             break;
       }
}

できる限りこれを最適化して試してみたいと思います。私の最初の考えは、二分探索を使用することでしたが、これを適切な方法で実装するのに問題があります (それが可能かどうかさえわかりません)。上記のソリューションで指定したものだけを使用して実行時間を改善するために、ここでできることについて何か提案はありますか?

4

1 に答える 1

2

二分探索は確かに答えです。

http://en.wikipedia.org/wiki/Binary_search_algorithm

整数二分探索の場合、次のようになります。

minW=0, maxW=maxTextWidth
while(minW<=maxW){

  mid=(minW+maxW)/2;
  if (textFitsInGivenWidth(text, mid)){
    maxW=mid-1;
  }else{
    minW=mid+1;
  }
}
textWidth=minW

アイデアは、もしあなたが持っているならtextFitsInGivenWidth(text, mid) == True、

それからあなたはtextFitsInGivenWidth(text, i) == Trueすべてのために持っている必要がありますi>=mid、

False の場合はtextFitsInGivenWidth(text, i) == False、i<=mid

そのため、チェックする間隔の中央をチェックするたびに、間隔を半分に減らします。時間は O(logN) で、N=maxTextWidth です。

更新: float のサポートについては、以下の例を参照してください。

float minW=0, maxW=maxTextWidth
while(1){
  if (maxW-minW<0.05)
    break;
  float mid=(minW+maxW)/2;
  if (textFitsInGivenWidth(text, mid)){
    maxW=mid;
  }else{
    minW=mid;
  }
}

textWidth=minW

.1 の精度を得るには、最後の行を次のように変更します。

textWidth=int(minW*10)/10.0
于 2012-08-03T07:34:14.443 に答える