在给定字符串中查找一组字符的最快算法

Question

这是我和我的一个朋友进行的一场辩论：如何最快速地创建一个验证方法，检查给定的字符串是否包含任何非允许字符。

方法一：简单

char [] invalidChars = "!@#$%^...".toCharArray();
        for (int i = 0; i < myString.length(); i++) {
            char ch = myString.charAt(i);
            for (int j = 0; j < invalidChars.length; j++) {
                if (invalidChars[j] == ch) {
                    return false;
                }
            }
        }

方法二：利用Map的O(1)

Map <String,String> map = new HashMap<String, String>();
        map.put("!", null);
        map.put("@", null);
        map.put("#", null);
        map.put("$", null);
        map.put("^", null);
        ...
        for (int i = 0; i < labels.length(); i++) {
            char ch = labels.charAt(i);
            if (map.containsKey(ch)) {
                return false;
            }
            return true;
        }

当无效字符较少时，方法I实际上等同于N2但与N一样好。在以下情况下应优先考虑哪种方法：情况I：有很多无效字符，情况II：只有少量无效字符？

注：我不需要任何内置的Java解决方案，只需算法来过滤少量（而非全部）非文本字符。

- Taranfx

Answer 1

如果你只关心验证ASCII字符，那么一个长度为128的布尔查找表可能比上述方法更快。

- Oliver Charlesworth

---

尽管那可能是一个解决方案，但并不真正回答问题。 - Roy T.

不，我的主要目的不是拒绝所有非ASCII字符，而是过滤掉一些。 - Taranfx

@taranfx: 我知道。我不是在暗示那个。我想说的是你可以使用一个布尔值数组，并根据ASCII字符值索引它。 - Oliver Charlesworth

@Oli Charlesworth，总的来说，使用大型布尔查找表会更慢（因为在内存中将布尔值保留为byte[]），因为它比long[]/int[]和位操作更容易出现缓存未命中（尽管在这种情况下表足够小）。 - bestsss

@Tony，如果boolean[]（实际上是byte[]）适合缓存行，则始终单个加载boolean[]可能比位操作更快，否则由于更好的缓存属性，long[]可能会优于boolean[]。如果你现在问为什么Java不将boolean[]实现为long/int[] - 因为元素的更新必须是原子的。 - bestsss

Answer 2

有一个简单的方法可以实现时间复杂度为 O(n log(m)) 的算法，其中 n 是输入的长度，m 是禁止字符的数量。

逐个扫描输入的字符，并使用二分查找在已排序的禁止字符数组中查找当前字符。

- NPE

Answer 3

如果您使用HashSet，它可以在添加和包含操作上达到O(1)：

• 每个禁止字符的插入操作为O(n)
• 每个比较操作为O(m)

这导致了O(m+n)，其中m是禁止字符的数量，n是字符串的长度。但我已经看到了更好的答案。

但请记住，大多数事物都带有开销（例如HashSet/HashMap中的“哈希”）。因此，即使渐近性能可能更好，对于小输入，朴素实现可能更快。我并不是说您应该使用O(n²)的东西，但将O(n log n)的解决方案与常见数据集的O(m)的解决方案进行比较可能是值得的！

- Martin Thurau

Answer 4

最快！ HashMap远非最快的解决方案，仅在理论上是O(1)。

在Java中：java.util.BitSet是为您的需求而设计的。 或者使用自我展开的long[]/int[]数组（取决于目标架构32/64）

为什么HashMap不好？从访问和创建桶中产生的额外负担比其本身的查找要高。

- bestsss

Answer 5

构建哈希表并将项目放入其中相对昂贵。但是正如您所说，在哈希表中查找项目的时间复杂度为O(1)。

因此，我们有哈希表填充：O(n log n)，查找为O(1)。

或者标准方式（填充O(1)，查找O(n)）。

然而，由于每个字符串都需要进行O(n)的查找，因此第一种方法的总时间复杂度为O(numberOfInvalidChars + strings*NumberofInValidChars)，而第二种方法为O(numInv log numInv + strings)。后者要便宜得多，几乎总是更便宜。

- Roy T.