优化大量Scanner.findWithinHorizo​​n（pattern，0）调用

Question

我正在构建一个从6个csv样式文件提取数据和两个布局错误的.txt报告并构建输出CSV的过程，我完全意识到有数千次的空白搜索，但我从来没有预料到转换大约50,000条记录需要12个小时。

摘译我手动匹配代码（我知道这是可怕的，我用这样的令牌的列表，但它是我能想到的最好的事情）：

public static String lookup(Pattern tokenBefore, 
          List<String> tokensAfter) 
{ 
    String result = null; 

    while(_match(tokenBefore)) { // block until all input is read 
     if(id.hasNext()) 
     { 
      result = id.next(); // capture the next token that matches 

      if(_matchImmediate(tokensAfter)) // try to match tokensAfter to this result 
       return result; 
     } else 
      return null; // end of file; no match 
    } 

    return null; // no matches 
} 

private static boolean _match(List<String> tokens) 
{ 
    return _match(tokens, true); 
} 

private static boolean _match(Pattern token) 
{ 
    if(token != null) 
    { 
     return (id.findWithinHorizon(token, 0) != null); 
    } else { 
     return false; 
    } 
} 

private static boolean _match(List<String> tokens, boolean block) 
{ 
    if(tokens != null && !tokens.isEmpty()) { 
     if(id.findWithinHorizon(tokens.get(0), 0) == null) 
      return false; 

     for(int i = 1; i <= tokens.size(); i++) 
     { 
      if (i == tokens.size()) { // matches all tokens 
       return true; 
      } else if(id.hasNext() && !id.next().matches(tokens.get(i))) { 
       break; // break to blocking behaviour 
      } 
     } 
    } else { 
     return true; // empty list always matches 
    } 

    if(block) 
     return _match(tokens); // loop until we find something or nothing 
    else 
     return false; // return after just one attempted match 
} 

private static boolean _matchImmediate(List<String> tokens) 
{ 
    if(tokens != null) { 

     for(int i = 0; i <= tokens.size(); i++) 
     { 
      if (i == tokens.size()) { // matches all tokens 
       return true; 
      } else if(!id.hasNext() || !id.next().matches(tokens.get(i))) { 
       return false; // doesn't match, or end of file 
      } 
     } 

     return false; // we have some serious problems if this ever gets called 
    } else { 
     return true; // empty list always matches 
    } 
} 

基本上不知道我会怎样工作，有效的字符串搜索（Boyer-Moore或类似的）。我的扫描仪id正在扫描java.util.String，将其缓存到内存将减少I/O，因为此处的搜索正在相对较小的文件上执行数千次。与扫描BufferedReader（FileReader（File））相比，性能提高可能不到1％，但该过程仍然需要很长时间。

我也追踪过执行过程，整个转换过程的速度肯定在查找方法的第一个和最后一个之间。事实上，我运行了一个快捷方式来计算.csv样式文件中各种标识符的出现次数（我使用2个查找方法，这只是其中的一个），并且该过程完成了大约4个不同的索引不到一分钟内就可以找到50,000条记录的标识符。与12小时相比，这是即时的。

的一些注意事项（更新2010年6月6日）：

1. 我仍然需要tokensBefore模式匹配行为。
2. 我需要的所有ID号不一定始于一行中的固定位置，但可以保证在ID令牌之后是相应对象的名称。
3. 我会理想地想返回一个字符串，而不是结果的开始位置作为一个int或东西。

即使每次搜索节省1ms，任何帮助我的东西都会有所帮助，因此所有的输入都会被赞赏。谢谢！

---

使用场景1：我在文件中的对象，谁在老式的系统有一个ID号的列表，它是不是在文件A.它是，但是，可能在另一个CSV风格文件（文件B）或可能仍在.txt报告（文件C）中，每个文件都包含一些其他信息，这些信息在这里没有用处，因此文件B需要通过对象的全名进行搜索它将驻留在任何给定行的第二列内），然后第一列应该是ID号。如果这不起作用，那么我们必须先将搜索标记以空格分隔成单独的标记，然后再为这些标记搜索文件C。

广义代码：

String field; 
for (/* each record in file A */) 
{ 
    /* construct the rest of this object from file A info */ 
    // now to find the ID, if we can 
    List<String> objectName = new ArrayList<String>(1); 
    objectName.add(Pattern.quote(thisObject.fullName)); 
    field = lookup(objectSearchToken, objectName); // search file B 
    if(field == null) // not found in file B 
    { 
     lookupReset(false); // initialise scanner to check file C 
     objectName.clear(); // not using the full name 

     String[] tokens = thisObject.fullName.split(id.delimiter().pattern()); 
     for(String s : tokens) 
      objectName.add(Pattern.quote(s)); 

     field = lookup(objectSearchToken, objectName); // search file C 
     lookupReset(true); // back to file B 
    } else { 
     /* found it, file B specific processing here */ 
    } 

    if(field != null) // found it in B or C 
     thisObject.ID = field; 
} 

的对象名令牌在他们可能连字号或撇号，用空格分隔所有大写单词（一个人的名字）。

根据aioobe的回答，我已经预编译了我的常量搜索令牌的正则表达式，在这种情况下，它只是\r\n。在另一个进程中，注意到的加速大约是20x，我编译了[0-9]{1,3}\\.[0-9]%|\r\n|0|[A-Z'-]+，虽然在上面的代码中没有注意到\r\n。沿着这些线路工作，它有我想知道：

如果只有可用的匹配将在非空格字符开始的行上匹配\r\n[^ ]会更好吗？它可能会减少_match执行的次数。

另一个可能的优化是这样的：连接所有的标记后，并提前(.*)。它会减少大约2/3编译的正则表达式的数量（所有这些都是字面的），并且希望允许我从该分组中取出文本，而不是保留每一行的“潜在标记”一个ID就可以了。这也值得去做吗？

上述情况可以解决，如果我可以让java.util.Scanner在调用findWithinHorizo​​n之后返回之前的当前令牌。

Answer 1

东西入手：每单次运行id.next().matches(tokens.get(i))执行以下代码：

Pattern p = Pattern.compile(regex); 
Matcher m = p.matcher(input); 
return m.matches(); 

编译正则表达式是不平凡的，你应该考虑在编译模式一劳永逸你程序：

pattern[i] = Pattern.compile(tokens.get(i)); 

，然后简单地调用像

pattern[i].matcher(str).matches()