3

NSString sizeWithFontを返すメソッドと混同しないようにCGSize、私が探しているのはNSString、特定の に制約されたを返すメソッドですCGSize。これを行う理由は、でテキストを描画するときCore Textに、文字列の末尾に省略記号 (...) を追加できるようにするためです。メソッドがこれを行うことは知ってNSString's drawInRectいますが、私は を使用しており、文字列の末尾ではなく各行Core Textの末尾をkCTLineBreakByTruncatingTail切り捨てています。

文字列を特定のwidthに切り詰めるこのメソッドが見つかりました。これを変更して a で機能させるのはそれほど難しくありませんが、アルゴリズムは長い文字列に対して信じられないほど遅く、実際には使用できません。(長い文字列を切り詰めるのに 10 秒以上かかりました)。これをより速く行うには、より「コンピューターサイエンス」/数学的なアルゴリズムの方法が必要です。より高速な実装を考え出すのに十分なほど大胆な人はいますか?CGSize

編集:これをバイナリアルゴリズムに組み込むことができました:

-(NSString*)getStringByTruncatingToSize:(CGSize)size string:(NSString*)string withFont:(UIFont*)font
{
    int min = 0, max = string.length, mid;
    while (min < max) {
        mid = (min+max)/2;

        NSString *currentString = [string substringWithRange:NSMakeRange(min, mid - min)];
        CGSize currentSize = [currentString sizeWithFont:font constrainedToSize:CGSizeMake(size.width, MAXFLOAT)];

        if (currentSize.height < size.height){
            min = mid + 1;
        } else if (currentSize.height > size.height) {
            max = mid - 1;
        } else {
            break;
        }
    }

   NSMutableString *finalString = [[string substringWithRange:NSMakeRange(0, min)] mutableCopy];
   if(finalString.length < self.length)
         [finalString replaceCharactersInRange:NSMakeRange(finalString.length - 3, 3) withString:@"..."];

   return finalString;
}

問題は、これにより弦に余裕があるときに弦が短くなりすぎることがあるということです。これが最後の条件の出番だと思います。切りすぎないようにするにはどうすればよいですか？

4

1 に答える 1

6

朗報です！これをより速く行うための「コンピューターサイエンス/数学的な方法」があります。

リンク先の例では、線形検索が行われます。文字列の末尾から十分に短くなるまで、一度に 1 文字ずつ切り捨てられます。したがって、かかる時間は文字列の長さに比例して増加し、長い文字列では非常に遅くなります。

ただし、バイナリ検索手法を文字列に簡単に適用できます。最後から開始して一度に 1 文字ずつドロップするのではなく、途中から開始します。

THIS IS THE STRING THAT YOU WANT TO TRUNCATE
                       ^

「THIS IS THE STRING THAT」の幅を計算します。幅が広すぎる場合は、テスト ポイントを左側のスペースの中間点に移動します。このような：

THIS IS THE STRING THAT YOU WANT TO TRUNCATE
          ^            |

一方、幅が十分でない場合は、テスト ポイントを残りの半分の中間点に移動します。

THIS IS THE STRING THAT YOU WANT TO TRUNCATE
                       |         ^

幅制限のすぐ下にあるポイントが見つかるまで、これを繰り返します。毎回検索領域を半分に分割しているため、非常に長い文字列の場合でも、非常に速く成長しない log2 N 回 (N は文字列の長さ) を超える幅を計算する必要はありません。 .

別の言い方をすれば、入力文字列の長さを 2 倍にしても、幅の計算が 1 回追加されるだけです。

ウィキペディアの二分探索サンプルから始めて、ここに例を示します。完全一致を探しているわけではないため (適合する最大のものを求めているため)、ロジックが少し異なることに注意してください。

int binary_search(NSString *A, float max_width, int imin, int imax)
{
  // continue searching while [imin,imax] is not empty
  while (imax >= imin)
    {
      /* calculate the midpoint for roughly equal partition */
      int imid = (imin + imax) / 2;

      // determine which subarray to search
      float width = ComputeWidthOfString([A substringToIndex:imid]);
      if      (width < max_width)
        // change min index to search upper subarray
        imin = imid + 1;
      else if (width > max_width )
        // change max index to search lower subarray
        imax = imid - 1;
      else
        // exact match found at index imid
        return imid;
  }
  // Normally, this is the "not found" case, but we're just looking for
  // the best fit, so we return something here.
  return imin;
}

一番下にある正しいインデックスが何であるかを把握するために、いくつかの数学またはテストを行う必要がありますが、それは間違いなくiminまたはimax、プラスまたはマイナス 1 です。

于 2012-05-21T19:02:16.060 に答える