我做了一些家庭作业,不得不把小说《战争与和平》拿来分别放入HashSet和TreeSet中。我必须安排时间,以检查差异,我的问题是我的实施效果是否良好。
我计算时间的方法是否准确。我正在使用

System.currentMillis()


,但是我在和我自己辩论

System.nanoTime()


是否是更好的选择。我可能只是误解了一些有关赋值的信息,因为这似乎太容易了,无法成为实际的解决方案。

请澄清一下:该代码有效。我在质疑实施的效率。

package SetExercise;

import java.io.*;
import java.util.*;

public class FileToSet {

    public static void main(String[] args) {
        HashSet<String> hs = new HashSet<>();
        TreeSet<String> ts = new TreeSet<>();
        long start = System.currentTimeMillis();
        fileToHashSet("war-and-peace.txt", hs);
        long end = System.currentTimeMillis();
        long elapsed = end - start;
        System.out.println("Total time HashSet (ms): " + elapsed);
        start = System.currentTimeMillis();
        fileToTreeSet("war-and-peace.txt", ts);
        end = System.currentTimeMillis();
        elapsed = end - start;
        System.out.println("Total time TreeSet (ms): " + elapsed);
    }

    static void fileToHashSet(String path, HashSet<String> set) {
        try {
            BufferedReader in = new BufferedReader(new FileReader(path));
            while(in.readLine() != null) {
                String line = in.readLine();
                set.add(line);
            }
            in.close();
        } catch(FileNotFoundException fnfe) {
            System.out.println(fnfe.getMessage());
        } catch(IOException ioe) {
            System.out.println(ioe.getMessage());
        }
    }

    static void fileToTreeSet(String path, TreeSet<String> set) {
        try {
            BufferedReader in = new BufferedReader(new FileReader(path));
            while(in.readLine() != null) {
                String line = in.readLine();
                set.add(line);
            }
            in.close();
        } catch(FileNotFoundException fnfe) {
            System.out.println(fnfe.getMessage());
        } catch(IOException ioe) {
            System.out.println(ioe.getMessage());
        }
    }
}


#1 楼

恐怕您实际上并没有将整个文件读入Set。实际上,您很幸运该代码没有抛出IOException


while(in.readLine() != null) {
    String line = in.readLine();
    set.add(line);
}



此循环在fileToHashSetfileToTreeSet实际上每次迭代读取两行。您只将每隔一行放在Set中,这可能很重要,也可能不会很重要。尝试像下面这样的循环...

String line;
while ((line = in.readLine()) != null) {
  set.add(line);
}



除此之外,我相信您应该安排几个试验的时间并将其平均以获得更多弹性统计。否则,您的结果可能会受到其他因素的太大影响。基准精度很重要,对不对?就像现在一样,您甚至有可能为第二个基准测试提供优势,因为第一个基准测试可能需要较慢的磁盘I / O,而第二个基准测试可能受益于操作系统将文件缓存在内存中的操作系统。

其他可能首先导致劣势的潜在因素是同时进行早期VM初始化,VM分析“启动”即时编译器以允许在VM生命周期中进一步进行更好的动态优化等。


最后一点要注意的是...如果您有两个catch块执行相同的工作,只是异常类型不同,那么我建议您利用Java 7的新功能之一-捕获多个异常类型。实际上,您可能还应该使用(也是最近添加的)try-with-resources

try (final BufferedReader in = new BufferedReader(new FileReader(path))) {
  String line;
  while ((line = in.readLine()) != null) {
    set.add(line);
  }
} catch (final FileNotFoundException | IOException ex) {
  System.err.println(ex);
}


请注意,除非您实际计划使用,否则可能不应该捕获异常他们。让它们传播到main之外,无论如何将它们打印到System.err

这里也没有理由使用两种单独的方法;两者都是Set<String>-为什么不使您的方法具有多态性?

P.S.使用System.err而不是System.out来打印错误消息。

P.P.S.我会给出一个有根据的猜测,由于其基本实现,HashSet会比TreeSet更快。毕竟,这需要总订单。

P.P.P.S.在此处收听Jon并使用nanoTime :-)

评论


\ $ \ begingroup \ $
感谢您的回答。既然您提到它是对的,我可能永远不会加载整个文件x)再次感谢!
\ $ \ endgroup \ $
–OmniOwl
2012年9月11日下午0:16

\ $ \ begingroup \ $
pastebin.com/30a6mTKC这就是我最终得到的。 HashSet似乎可以持续赢得大约20到25毫秒的时间。
\ $ \ endgroup \ $
–OmniOwl
2012年9月11日在3:28



\ $ \ begingroup \ $
@Vipar我不会保存对缓存的引用。除此之外,您应该平均进行数百次甚至数千次试验。您不应该一直像这样对起点和终点进行求和...只是找到迭代之前的时间,计算经过的持续时间,然后除以1,000或您希望执行的迭代次数。除此之外,在每次迭代中都使用Set.clear来初始化一个新的Set。
\ $ \ endgroup \ $
– obataku
2012年9月11日在3:32



\ $ \ begingroup \ $
这里:pastebin.com/KbMqEdbi您能否说这更准确?
\ $ \ endgroup \ $
–OmniOwl
2012年9月11日在3:40



\ $ \ begingroup \ $
@Vipar肯定;这是我的尝试。
\ $ \ endgroup \ $
– obataku
2012年9月11日下午4:03

#2 楼

要测量花费的时间,您应该使用System.nanoTime。只能用于“秒表”类型的操作-绝不能以壁钟方式获取“当前系统时间”。相反,System.currentTimeMillis不应用于“秒表”类型的操作,因为它可能会受到系统时钟更改等的影响。

nanoTime的文档中获取:


此方法只能用于测量经过的时间,并且与系统或挂钟时间的任何其他概念无关。返回的值表示自某个固定但任意的原始时间以来的纳秒(也许是将来的时间,因此值可能为负)。在Java虚拟机的实例中,此方法的所有调用都使用相同的源。其他虚拟机实例可能使用不同的来源。


请注意,重点不是这里的粒度不同,而是目的不同。它们可能都返回毫秒,因此有两个不同的调用仍然很有意义。

评论


\ $ \ begingroup \ $
我明白了。说得通。因此,我的做法仍然正确吗?我应该只使用nanoTime()而不是使用currentMillis()?
\ $ \ endgroup \ $
–OmniOwl
2012-09-10 23:32

\ $ \ begingroup \ $
@Vipar:有点-但是您应该循环执行此操作,并从文件系统中删除文件系统。首先将文件加载到内存中,例如到List 中。您当前的代码很有可能会用IO占大部分时间。
\ $ \ endgroup \ $
–乔恩·斯基特(Jon Skeet)
2012-09-10 23:34

\ $ \ begingroup \ $
我想我必须直接将文件加载到任一集合中。难道不是先将文件加载到列表中然后加载到集合中,如果您不得不检查将文件成功加载到集合中所花费的时间,那会有点“作弊”吗?
\ $ \ endgroup \ $
–OmniOwl
2012-09-10 23:36

\ $ \ begingroup \ $
@Vipar:基本上,您应该测量从文件加载数据的时间。除非您要运行一个测试加载到HashSet中,然后在将文件加载到TreeSet中之前清除文件系统缓存等。
\ $ \ endgroup \ $
–乔恩·斯基特(Jon Skeet)
2012-09-10 23:38

\ $ \ begingroup \ $
@Vipar:这完全取决于操作系统,但是基本上这很痛苦。但是,是的,它与不清除缓存会有非常不同的结果。尝试一下-我希望您会看到,无论您先测试哪种设置,都会降低性能(至少在启动后第一次运行它)。您需要解决自己关心的问题:IO或设置性能。 IO可能会淹没设定的性能。
\ $ \ endgroup \ $
–乔恩·斯基特(Jon Skeet)
2012-09-10 23:44

#3 楼

如果要测试HashSet<E>TreeSet<E>之间的差异,则应将所有其他代码放在被测区域之外—包括任何文件I / O,stdout / stderr I / O,还可能设置初始化(无论是new还是clear() )—以排除与操作系统和设备交互的可变性。

被测区域应仅包含一个循环,在该循环中您可以将预加载的数据添加到集合中。因此,您应该首先加载文件并将其保存在内存结构中,例如String[]

如果决定在测量中包括设置的初始化,请不要使用clear()。在实际情况下,该集合通常仅使用一次,因此请使用new。在
HashSet<E>的情况下,这一点尤其重要,一旦超出负载阈值,添加元素会导致扩展内部存储结构(HashMap<K,V>)的容量。随后调用clear()会使设置的容量保持扩展状态,因此会修改所有后续测量重复的条件。

说到负载阈值,您还必须确定初始容量,因为当您将其设置得太低时(或将其保留为默认值),则可能会发生上述HashSet<E>容量扩展,从而导致该集中存在的所有元素的耗时的重新哈希处理(重复插入)。当然,这也恰恰是您想要包含在度量/比较中的内容。

次要点是集合的类型参数,因为编译器会在下面生成一些强制转换和桥接方法

然后解决方案的核心应如下所示:

public static void main(String[] args) {
    final String[] data = preload(args[0]); // skipped for brevity
    final long count = Long.valueOf(args[1]);
    final Consumer<String> log = System.out::println;

    log.accept("Total time HashSet (ns): " + measure(HashSet::new, data, count));
    log.accept("Total time TreeSet (ns): " + measure(TreeSet::new, data, count));
}

static <E> long measure(Supplier<Set<E>> factory, E[] data, long count) {
    return Stream.generate(factory)
            .limit(count)
            .mapToLong(set -> {
                final Stream<E> stream = Stream.of(data);
                final long start = System.nanoTime();
                stream.forEach(set::add);
                return System.nanoTime() - start;
            }).sum();
}


或者如果您仍然选择clear()初始化方法:

static <E> long measureClear(Supplier<Set<E>> factory, E[] data, long count)) {
    final Set<E> set = factory.get();
    set.addAll(Arrays.asList(data)); // ensure capacity to avoid rehashing
    return measure(() -> {set.clear(); return set;}, data, count);
}


#4 楼

您可以使用一些库:





来自Apache Commons IO的FileUtils.readLines或来自Guava的Files.readLines(File, Charset),如果要在将行添加到集合之前将文件预加载到内存中。
否则请从Apache Commons IO获得FileUtils.lineIterator(File file, String encoding)
来自Apache Commons Lang的StopWatch或来自Guava的Stopwatch进行计时。

另请参见:有效的Java,第二版,项目47:了解和使用库

评论


\ $ \ begingroup \ $
好吧,但是Josh Bloch在这里明确地谈论了标准的Java库,而不是第三方的库。即使您可以将各种Apache项目视为“通用”项目,但在质量和适用性方面却有很多项目,但您无法跟踪所有项目。仅使用一个呼叫使用第三方库(与实现合适的库相比,您可以更快地重新实现)是一种矫...过正...
\ $ \ endgroup \ $
–查理
2012-09-20 22:25

\ $ \ begingroup \ $
通常,学生只能使用教授提供的第三方图书馆。
\ $ \ endgroup \ $
– Eva
13年1月16日在11:58

#5 楼

对于时间测量,我喜欢通过求和来计算经过时间的方式中的数学运算:

long start = 0;
long end = 0;
for(int i = 0; i < count; i++) {
    start += System.nanoTime();
    fileToSet(path,hs);
    end += System.nanoTime();
    hs.clear();
}
long average = (end - start) / count;


为什么不应该这样做,但是可以很快超出了long范围。稍作改进:

long elapsed = 0;
for(int i = 0; i < count; i++) {
    long start = System.nanoTime();
    fileToSet(path,hs);
    elapsed += System.nanoTime() - start;
    hs.clear();
}
long average = elapsed / count;


但是这里可能发生的情况是,如果fileToSet()的速度快于系统时间的粒度,则最终可能会求和零。这就是为什么最好使用反向方法的原因-测量基准测试代码之外的所有操作,然后从总时间中减去:

long start = System.nanoTime();
long end = start;
long exclude = 0;
for(int i = 0; i < count; i++) {
    exclude += System.nanoTime() - end;
    fileToSet(path,hs);
    end = System.nanoTime();
    hs.clear();
}
long elapsed = (end - start) - exclude;
long average = elapsed / count;


#6 楼

final long[] tabTime = new long[6];
tabTime[0] = System.nanoTime();
Set<String> set;
// Java 7 used, no need to have HashSet<String>(5000)
set = new HashSet<>(5000); // numberOfLines
// set = new TreeSet<>(5000); // numberOfLines
try {
    tabTime[1] = System.nanoTime();
    final BufferedReader in = new BufferedReader(new FileReader(
     System.getProperty("user.home") + "/WarAndPeace.txt"));
    tabTime[2] = System.nanoTime();
    String s;
    while ((s = in.readLine()) != null) {
        set.add(s);
    }
    tabTime[3] = System.nanoTime();
    in.close();
} catch (final FileNotFoundException fnfe) {
    System.out.println(fnfe.getMessage());
} catch (final IOException ioe) {
    System.out.println(ioe.getMessage());
}
tabTime[4] = System.nanoTime();
final Set treeSet = new TreeSet(set);
tabTime[5] = System.nanoTime();
for (int i = 1, n = tabTime.length; i < n; i++) {
    System.out.format("%d.%d%n", (tabTime[i] - tabTime[0]) / 1000000,
        (tabTime[i] - tabTime[0]) % 1000000);
}


我所做的测试表明,将String放置在while之外的速度更快
,但是在这种情况下,Scanner速度非常慢(但它非常强大,对于管理输入非常有用哈希自然比Tree快,首先是如果它们以适当的大小打开,那么您必须将其放在时间范围之外才能获得真实结果

评论


\ $ \ begingroup \ $
从外观上看,这段代码看起来很混乱而且不可读。
\ $ \ endgroup \ $
–康拉德·鲁道夫(Konrad Rudolph)
2012年9月11日9:53



\ $ \ begingroup \ $
@KonradRudolph与Vipar一样,具有用于跟踪时间消耗的工具。因此,他可以玩HashSet / TreeSet并将String放入和放出一段时间,以查看发生了什么,仅此而已。无意太冗长。
\ $ \ endgroup \ $
–cl-r
2012年9月11日下午12:10