HashSet and TreeSet

Question

I got some homework in which I had to take the novel War and Peace and put it into a HashSet and TreeSet respectively. I had to time it, to check differences and my question is whether my implementation is good or not. If the way I calculate time is even accurate. I am using

System.currentMillis()

but I was debating with myself whether

System.nanoTime()

would be a better choice. I might just have misunderstood something about the assignment since this just seems way too easy to be the actual solution.

Just to clarify: The code works. I am questioning the efficiency of my implementation.

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());
        }
    }
}

Answer 1

I'm afraid you aren't actually reading the entire file into either Set. In fact, you're quite lucky this code isn't throwing an IOException.

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

This loop, present in both fileToHashSet and fileToTreeSet, is actually reading two lines every iteration. You're only placing every other line into either Set, which may or may not be significant. Try a loop like the below instead...

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

---

Aside from that, I believe you should be timing several trials and averaging these to get a more resilient statistic. Otherwise, your results might be too influenced by other factors. Benchmark accuracy is important, right? As you have it now, you're potentially even giving an advantage to the second benchmark, since the first may require slower disk I/O, while the second might be benefit from the OS caching the file in memory.

Other potential factors that may disadvantage the first are early VM initialization ocurring simultaneously, VM analysis "priming" the just-in-time compiler to allow better dynamic optimizations further along during the VM life, etc.

---

And, lastly, a small notice... if you have two catch blocks that do identical work, only differing in exception type, I suggest you take advantage of one of the newer features of Java 7 -- catching multiple exception types. In fact, you should probably also use the (also a recent addition) 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);
}

Note you should probably not catch exceptions unless you actually plan to use them. Let them propagate out of main, where they will be printed to System.err, anyways.

There's also no reason to have two separate methods here, either; both are Set<String> -- why not make your method polymorphic?

P.S. use System.err for printing error messages rather than System.out.

P.P.S. I'll give an educated guess that HashSet will be faster than TreeSet by virtue of the underlying implementation... one necessitates a total order, after all.

P.P.P.S. Listen to Jon and use nanoTime here :-)

Answer 2

To measure the time taken, you should use System.nanoTime. That should only be used for "stopwatch" type operations - never for taking the "current system time" in a wall-clock way. Conversely, System.currentTimeMillis should not be used for "stopwatch" type operations, as it can be affected by system clock changes etc.

From the docs for nanoTime:

This method can only be used to measure elapsed time and is not related to any other notion of system or wall-clock time. The value returned represents nanoseconds since some fixed but arbitrary origin time (perhaps in the future, so values may be negative). The same origin is used by all invocations of this method in an instance of a Java virtual machine; other virtual machine instances are likely to use a different origin.

Note that the important point isn't the difference in granularity here - it's the difference in purpose. They could both be returning milliseconds, and it would still make sense to have two different calls.

Answer 3

If you want to test differences between HashSet<E> and TreeSet<E>, you should put all the other code out of the measured region — that includes any file I/O, stdout/stderr I/O, and possibly also set initialization (be it new or clear()) — to factor out the variability of interaction with OS and devices.

The measured region should contain only a loop in which you add the preloaded data into the set. You should therefore load the file first and keep it in a memory construct, e.g. String[].

If you decide to include the set initialization in the measurement, don't use clear(). In a real-world scenario, the set is usually used only once, hence use new. This is specifically important in the case of HashSet<E>, where additions of elements can result in extending the capacity of internal storage structure (a HashMap<K,V>) once a load threshold is exceeded. Calling subsequently clear() leaves the set capacity extended, thus it modifies conditions for all following measurement repetitions.

Speaking of the load threshold, you also have to decide upon the initial capacity, because when you set it too low (or leave it as default), the aforementioned HashSet<E> capacity extension may occur, resulting in a time-expensive rehashing (a repeated insertion) of all elements present in the set. Of course, this as well can be exactly what you want to include in the measurement / comparison.

A minor point would be the type parameter of a set, as the compiler generates some casts and bridge methods under the hood, but this is not meant to advocate the use of a raw type.

The core of the solution then should look like this:

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();
}

Or if you opt for the clear() initialization method anyway:

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);
}

Answer 4

A few libraries that you could use:

• FileUtils.readLines from Apache Commons IO or Files.readLines(File, Charset) from Guava if you want to preload the file to the memory before adding the lines to the sets.

• FileUtils.lineIterator(File file, String encoding) from Apache Commons IO otherwise.

• StopWatch from Apache Commons Lang or Stopwatch from Guava for the timing.

See also: Effective Java, 2nd edition, Item 47: Know and use the libraries

Answer 5

To the time measurements, I like the math in the way you compute the elapsed time by summing:

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;

Why you should not do this, however, is that you can quickly run out of the long range. Slightly refined:

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;

But what can happen here is that if the fileToSet() is faster than the system time granularity, you may end up summing zeroes. That's why you'd be better using an inverse approach instead — measure all operations outside the benchmarked code, then substract this from the total time:

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;

Answer 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);
}

The test I've done show that putting String s outside the while is faster
But Scanner, in this case, it very slow (but it is very powerful and useful for managing input)
Hash is naturally faster than Tree, above all if they are opened with good size, and you have to put outside the time scope the print to have real results