我有一个由 unicode 字符组成的字符串。同一个字符只能出现一次。字符串的长度在 1 到 ~50 之间。
检查特定字符是否在字符串中的最快方法是什么？
迭代字符串不是一个好的选择，不是吗？有没有为此目的的有效算法？
我的第一个想法是保持字符串中的字符按字母顺序排序。它可以快速搜索，但 unicode 字符的排序和比较并不是那么简单（使用正确的排序规则），而且成本很高，可能比迭代整个字符串更大。
也许一些散列？也许迭代是最快的方式？
任何想法？
问问题
806 次
3 回答
4
如果没有预处理，最简单最快的方法是遍历字符。
如果有预处理，以前的方法可能仍然是最好的，或者您可以尝试一个小的哈希表来存储字符串是否包含该字符。存储哈希会占用额外的空间，但对于内存缓存可能会更好（哈希冲突低且假设您不必访问实际字符串）。确保测量性能。
我有一种感觉，你试图过度设计一个非常简单的任务。您是否确认这是您的应用程序中的瓶颈？
于 2013-09-16T19:42:16.087 回答
0
对字符串的线性搜索是 O(n)，每个操作都非常简单。对字符串进行排序是 O(n log n)，操作更复杂。很明显，线性搜索在所有情况下都会更快。
如果字符以 UTF-8 或 UTF-16 编码存储，那么您可能需要搜索多个连续元素。有一些方法可以加快速度，例如Boyer-Moore或Knuth-Morris-Pratt。目前尚不清楚这样短的搜索字符串是否会真正加快速度。
于 2013-09-16T20:24:35.473 回答
0
它是对同一字符串的重复操作还是 1 次任务？如果这是一个 1 次任务，那么在你必须查看所有字符之后，你不能比遍历字符串做得更好。上）
如果是重复操作，则可以对字符串进行一些预处理，以使后续操作更快。最节省空间和最快的方法是为每个字符串中的字符构建布隆过滤器。一旦构建起来也很快，你可以说如果一个字符不存在于 0(1) 中，并且只有当布隆过滤器说是时才对排序的字符串进行二进制搜索。
于 2013-09-16T21:08:17.413 回答