java优化项目Euler#22

Question

提前谢谢

我刚刚解决了Project Euler #22，这个问题涉及从一个文件中读取大约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秒（用户时间）执行。我觉得应该比你刚才做的快一点

EDITOP询问传递给useDelimiter的字符串是什么。这是一个regular expression。当你去掉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

在循环中附加带“+”的字符串，如下所示：

/* 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中每个名字的双引号

Answer 3

根据应用程序的不同，^{}通常比^{快得多。比较这两者的例子可以在here和here中找到

附录：Euler Project 22包括推导遇到的每个令牌中字符的一种校验和。自定义analyzer可以将识别和计算结合起来，而不是遍历令牌两次。结果将被存储在SortedMap<String, Integer>中，以便以后在寻找总计时进行迭代