Оптимизация проекта Эйлера # 22

Question

Заранее спасибо.

Я только что решил Project Euler # 22 * ​​1004 *, проблема, связанная с чтением около 5000 строк текста из файла и определением значения конкретного имени на основе суммы символов этих строк.и его положение в алфавитном порядке.

Однако запуск кода занимает около 5-10 секунд, что немного раздражает.Каков наилучший способ оптимизировать этот код?В настоящее время я использую сканер для чтения файла в строку.Есть ли другой, более эффективный способ сделать это?(Я пытался использовать BufferedReader, но это было еще медленнее)

public static int P22(){


    String s = null;

    try{
        //create a new Scanner to read file
        Scanner in = new Scanner(new File("names.txt"));
        while(in.hasNext()){
            //add the next line to the string
            s+=in.next();
        }

    }catch(Exception e){

    }
    //this just filters out the quotation marks surrounding all the names
    String r = "";
    for(int i = 0;i<s.length();i++){
        if(s.charAt(i) != '"'){
            r += s.charAt(i);
        }
    }
    //splits the string into an array, using the commas separating each name
    String text[] = r.split(",");
    Arrays.sort(text);



    int solution = 0;
    //go through each string in the array, summing its characters
    for(int i = 0;i<text.length;i++){
        int sum = 0;
        String name = text[i];
        for(int j = 0;j<name.length();j++){
            sum += (int)name.charAt(j)-64;
        }
        solution += sum*(i+1);
    }
    return solution;


}

Answer 1

Если вы собираетесь использовать Scanner, почему бы не использовать его для того, что он должен делать (токенизация)?

  Scanner in = new Scanner(new File("names.txt")).useDelimiter("[\",]+");
  ArrayList<String> text = new ArrayList<String>();
  while (in.hasNext()) {
    text.add(in.next());
  }
  Collections.sort(text);

Вам не нужно разбивать кавычки или разделять запятыми -Scanner все делает за вас.

Этот фрагмент, включая время запуска Java, выполняется на моей машине за 0,625 с (время пользователя).Я подозреваю, что это должно быть немного быстрее, чем то, что вы делали.

EDIT OP спросил, какая строка была передана useDelimiter.Это регулярное выражение .Когда вы убираете экранирование, требуемое Java для включения символа кавычки в строку, это [",]+ - и значение:

[...]   character class: match any of these characters, so
[",]    match a quote or a comma
...+    one or more occurence modifier, so
[",]+   match one or more of quotes or commas

Последовательности, которые будут соответствовать этому шаблону, включают:

"
,
,,,,
""",,,",","

и, действительно, ",", к чему мы тут стремились.

Answer 2

Тупое решение, которое может показаться интересным.

long start = System.nanoTime();
long sum = 0;
int runs = 10000;
for (int r = 0; r < runs; r++) {
    FileChannel channel = new FileInputStream("names.txt").getChannel();
    ByteBuffer bb = channel.map(FileChannel.MapMode.READ_ONLY, 0, channel.size());
    TLongArrayList values = new TLongArrayList();

    long wordId = 0;
    int shift = 63;
    while (true) {
        int b = bb.remaining() < 1 ? ',' : bb.get();
        if (b == ',') {
            values.add(wordId);
            wordId = 0;
            shift = 63;
            if (bb.remaining() < 1) break;

        } else if (b >= 'A' && b <= 'Z') {
            shift -= 5;
            long n = b - 'A' + 1;
            wordId = (wordId | (n << shift)) + n;

        } else if (b != '"') {
            throw new AssertionError("Unexpected ch '" + (char) b + "'");
        }
    }

    values.sort();

    sum = 0;
    for (int i = 0; i < values.size(); i++) {
        long wordSum = values.get(i) & ((1 << 8) - 1);
        sum += (i + 1) * wordSum;
    }
}
long time = System.nanoTime() - start;
System.out.printf("%d took %.3f ms%n", sum, time / 1e6);

печать

XXXXXXX took 27.817 ms.

Answer 3

В зависимости от применения, StreamTokenizer часто заметно быстрее, чем Scanner.Примеры, сравнивающие эти два, можно найти здесь и здесь .

Приложение: Euler Project 22 * ​​1012 * включает получение некоторой контрольной суммы символов вкаждый встреченный токенВместо того, чтобы дважды проходить токен, пользовательский анализатор может объединять распознавание и вычисление.Результат будет сохранен в SortedMap<String, Integer> для последующей итерации при поиске общей суммы.

Answer 4

5 + секунд довольно медленно для этой проблемы. Все мое веб-приложение (600 классов Java) компилирует за четыре секунды. Корень вашей проблемы, вероятно, в выделении новой строки для каждого символа в файле: r += s.charAt(i)

Чтобы действительно ускорить это, вы не должны использовать Strings вообще. Получите размер файла и прочитайте все это в байтовом массиве за один вызов ввода / вывода:

public class Names {
  private byte[] data;
  private class Name implements Comparable<Name> {
    private int start; // index into data
    private int length;
    public Name(int start, int length) { ...; }
    public int compareTo(Name arg0) {
      ...
    }
    public int score() 
  }
  public Names(File file) throws Exception {
    data = new byte[(int) file.length()];
    new FileInputStream(file).read(data, 0, data.length);
  }
  public int score() {
    SortedSet<Name> names = new ...
    for (int i = 0; i < data.length; ++i) {
      // find limits of each name, add to the set
    }
    // Calculate total score...
  }
}

Answer 5

Я предлагаю вам запустить свой код с профилировщиком. Это позволяет понять, какая часть действительно медленная (IO / вычисления и т. Д.). Если IO медленный, проверьте NIO: http://docs.oracle.com/javase/1.4.2/docs/guide/nio/.

Answer 6

Добавление строк в цикле с помощью '+', как вы делаете здесь:

/* That's actually not the problem since there is only one line. */
while(in.hasNext()){
    //add the next line to the string
    s+=in.next();
}

медленно, потому что оно должно создавать новую строку и копировать все вокруг в каждой итерации.Попробуйте использовать StringBuilder,

StringBuilder sb = new StringBuilder();
while(in.hasNext()){
    sb.append(in.next());
}
s = sb.toString();

Но вы не должны действительно читать содержимое файла в String, вы должны создать String[] или ArrayList<String> непосредственно из содержимого файла,

int names = 5000; // use the correct number of lines in the file!
String[] sa = new String[names];
for(int i = 0; i < names; ++i){
    sa[i] = in.next();
}

Однако при проверке выясняется, что файл не содержит около 5000 строк, скорее, он находится на одной строке, поэтому ваша большая проблема на самом деле

/* This one is the problem! */
String r = "";
for(int i = 0;i<s.length();i++){
    if(s.charAt(i) != '"'){
        r += s.charAt(i);
    }
}

Используйте StringBuilder для этого.Или, сделайте ваш Scanner прочитанным до следующего ',' и прочитайте непосредственно в ArrayList<String> и просто удалите двойные кавычки из каждого имени в ArrayList.