Java Arrays.sort()需要很长时间

Question

我正在使用Java的Arrays.sort()函数按照上次修改时间对文件列表进行排序.245个文件的排序大约需要5秒钟.这对我来说似乎太长了.我觉得它不应该超过0.5秒.这是一个很好的假设吗？我究竟做错了什么？或者这听起来正常吗？

public static class LastModifiedComparator implements Comparator<File> {
    @Override
    public int compare(File f1, File f2) {
        return (int)(f1.lastModified() - f2.lastModified());
    }       
}

File folder = new File( "C:\\Whatever\\" );
File[] filesInFolder = folder.listFiles();
logger.debug("Starting File Sort");
Arrays.sort(filesInFolder, new LastModifiedComparator());
logger.debug("Done File Sort");

日志输出

2012-08-10 14:24:20,333 DEBUG http-8080-4 <ClassName>:73 - Starting File Sort
2012-08-10 14:24:25,915 DEBUG http-8080-4 <ClassName>:75 - Done File Sort

Answer 1

File.lastModified必须去操作系统查询文件上次修改的时间 - 它没有被缓存.你在每次比较时都做了两次,而Arrays.sort使用了mergesort - O(n log n).插入245 n,这是大约580次比较,或1100次调用操作系统以获得最后修改时间.这意味着您每秒可以获得大约230个最后修改过的调用.这看起来似乎有点慢,但肯定比在JVM比较中花费那么长时间更合理

正如Marko Topolnik abd NgSan指出的那样,修复方法是首先缓存所有文件的最后修改时间.我会通过创建一个结合了File和那个时间的新类对象,然后对这些对象进行排序来实现.这样你只需要245次调用File.lastModified,排序大约需要1/5的时间.

Answer 2

您需要改进Comparator逻辑.您需要缓存的lastModified()值,因为该方法的实现是相当缓慢.我建议将File实例包装到您制作的类似对象中,以缓存该值:

public class FileLmWrapper implements Comparable<FileLmWrapper> {
  public final File f;
  public final long lastModified;
  public FileLmWrapper(File f) { 
    this.f = f; 
    lastModified = f.lastModified();
  }
  public int compareTo(FileLmWrapper other) {
    return Long.compare(this.lastModified, other.lastModified);
  }
}