3

不要与NSString sizeWithFont返回 a 的方法混淆CGSize，我正在寻找的是一个返回 aNSString约束到某个的方法CGSize。我想这样做的原因是，当用 绘制文本时Core Text，我可以在字符串的末尾附加一个省略号 (...)。我知道NSString's drawInRect方法为我做这个，但我正在使用Core Text, 并kCTLineBreakByTruncatingTail截断每行的结尾而不是字符串的结尾。

我发现有一种方法可以将字符串截断到一定的宽度，并且更改它以使其适用于 a 并不难CGSize，但是该算法对于长字符串来说速度慢得令人难以置信，并且实际上无法使用。（截断一个长字符串需要 10 多秒）。必须有一种更“计算机科学”/数学算法的方法来更快地做到这一点。有人敢于尝试提出更快的实现吗？

编辑：我已经设法把它变成了一个二进制算法：

-(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

好消息！有一种“计算机科学/数学方法”可以更快地做到这一点。

您链接到的示例进行线性搜索：它只是从字符串末尾一次切掉一个字符，直到它足够短。因此，它所花费的时间将与字符串的长度成线性比例，而对于长字符串，它会非常慢，正如您所发现的那样。

但是，您可以轻松地将二进制搜索技术应用于字符串。与其从末尾开始，一次丢掉一个字符，不如从中间开始：

THIS IS THE STRING THAT YOU WANT TO TRUNCATE
                       ^

您计算“这是那个字符串”的宽度。如果它太宽，则将测试点移动到左侧空间的中点。像这样：

THIS IS THE STRING THAT YOU WANT TO TRUNCATE
          ^            |

另一方面，如果它不够宽，则将测试点移动到另一半的中点：

THIS IS THE STRING THAT YOU WANT TO TRUNCATE
                       |         ^

重复此操作，直到找到刚好低于宽度限制的点。因为您每次都将搜索区域分成两半，所以您永远不需要计算超过 log2 N 次的宽度（其中 N 是字符串的长度），即使对于非常长的字符串，它也不会增长得很快.

换句话说，如果将输入字符串的长度加倍，那只是一个额外的宽度计算。

从Wikipedia 的二分搜索示例开始，这里有一个示例。请注意，由于我们不是在寻找精确匹配（您想要最大的匹配），因此逻辑略有不同。

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

你需要做一些数学或测试来找出底部的正确索引，但它肯定是iminor imax，加或减一。

于 2012-05-21T19:02:16.060 回答