CNF公式解析器

Question

我在Dimacs格式中有一个CNF公式解析器，它非常慢。对如何提高速度有什么建议吗？我做了一些分析，我可能不得不替换Scanner。还有更快的吗？

解析器的一个可能输入是：

C一个样本.cnf文件。2 1 -3 0 2 3 -1 0

守则：

/**
 * Parses a stream for a CNF instance.                                                                  
 *
 * @param source input stream                                                                           
 * @return read skeleton
 * @throws ParseException if stream contains an invalid instance                                        
 */
private static Skeleton parseStream(final InputStream source)                                           
    throws IOException, ParseException {                                                                
  Scanner scanner = new Scanner(source);                                                                

  // Skip comments
  try {                                                                                                 
    String token = scanner.next();                                                                      
    while (token.equals("c")) {                                                                         
      scanner.nextLine();
      token = scanner.next();                                                                           
    }
    if (!token.equals("p")) {
      throw new ParseException(                                                                         
          "Excepted 'p', but '" + token + "' was found");                                               
    }
  } catch (NoSuchElementException e) {
    throw new ParseException("Header not found");                                                       
  }

  // Reads header
  int numVariables, numClauses;                                                                         
  try {
    String cnf = scanner.next();                                                                        
    if (!cnf.equals("cnf")) {                                                                           
      throw new ParseException(                                                                         
          "Expected 'cnf', but '" + cnf + "' was found");                                               
    }
    numVariables = scanner.nextInt();                                                                   
    numClauses = scanner.nextInt();
  } catch (NoSuchElementException e) {
    throw new ParseException("Incomplete header");                                                      
  }
  logger.debug("p cnf " + numVariables + " " + numClauses);                                             

  // Reads clauses
  Skeleton skeleton = new Skeleton(numVariables);
  try {
    while (numClauses > 0) {
      int literal = scanner.nextInt();
      skeleton.cnf.add(literal);
      if (literal == 0) {
        numClauses--;
      }
    }
  } catch (NoSuchElementException e) {
    throw new ParseException(
        "Incomplete problem: " + numClauses + " clauses are missing");
  }

  return skeleton;                                                                                      
}                                                                                                       

Answer 1

使用BufferedInputStream来加快磁盘访问速度。如果这还不够，您可以逐行读取文件，并使用split()将其分解为单个数字。