Парсер для КНФ формулы


У меня есть парсер для КНФ формулы в формате Dimacs, что очень медленно. Любые предложения о том, как повысить его скорость? Я сделал некоторые профилирования и мне, возможно, придется заменить сканер. Есть ли что-нибудь быстрее?

Возможные материалы для парсера является:

c A sample .cnf file.
p cnf 3 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;                                                                                      
}                                                                                                       


1925
6
задан 15 февраля 2011 в 12:02 Источник Поделиться
Комментарии
1 ответ

Использовать BufferedInputStream для ускорения доступа к диску. Если этого не достаточно, вы можете прочитать файл построчно и использовать сплит() , чтобы разбить его на отдельные цифры.

6
ответ дан 15 февраля 2011 в 07:02 Источник Поделиться