用于在给定字符串中搜索字符集的最快算法

这是我与我的一位朋友进行的一次辩论：制作一个valiation方法的最快方法是检查给定字符串是否具有一个不允许的字符串人物用于在给定字符串中搜索字符集的最快算法

方法一：简单

char [] invalidChars = "[email protected]#$%^...".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; 
       } 
      } 
     }

方法二：开拓地图的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; 
     }

的方法其实我是N2，但如N好时invalidChars是少号。案例一应该优先考虑什么：有很多无效字符，案例二：只有少数无效字符？

注：我没有找任何内置的Java解决方案，但是，只是算法，如果你只在验证ASCII字符兴趣来过滤一些（不是全部）非文本字符

来源

2011-02-01 Taranfx

，那么长-128布尔查找表可能比上述任何一种方法都快。

来源

2011-02-01 08:29:10

虽然这可能是一个解决方案，但它不是真正的问题的答案。 – 2011-02-01 08:32:39

构建一个hashmap并把项目放在那里是相对昂贵的。然而，正如你所说的在一个hashmap中查找项目是O（1）。

所以我们有hashmap填充：O（n日志n）与查找O（1）。

或标准方式（填充O（1）查找O（n））。然而，由于O（n）查找发生在每个字符串中，所以第一个方法总共是O（numberOfInvalidChars + strings * NumberofInValidChars），第二个是O（numInvlogNumInv + strings）。哪些是便宜的，所以几乎总是便宜。

来源

2011-02-01 08:31:52

有一个简单的方法，会给你O(n log(m))时间复杂度，其中n是输入的长度和m是不允许的字符数。

一次扫描输入的一个字符，然后使用二分查找来查找（已排序的）不允许的字符数组中的当前字符。

来源

2011-02-01 08:33:49 NPE

如果使用一个HashSet，它给你O（1）上的附加和包含您有：

O（n）的每个禁止字符
O（M）的插入对于每个比较操作

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

但请记住，大部分东西都会带有开销（如HashSet/HashMap中的“散列”）。所以即使渐近表现可能会更好一点，幼稚的实现可能会更快，小输入。我并不是说你应该使用O（n2）的东西，但可能需要将一个O（n log n）解与O（m）解相比较以获得一组常用数据！

来源

2011-02-01 08:46:32

最快！ HashMap是最快的解决方案，理论上它是O（1）。

在java中：java.util.BitSet中是专为您的需求。或者使用自解包long []/int []数组（取决于目标体系结构32/64）

为什么HashMap不好？来自访问和创建存储桶的额外行李比自己的查询要高。

来源

2011-02-01 09:04:55 bestsss

用于在给定字符串中搜索字符集的最快算法

回答

相关问题