عرض عملي: المجموعة الخاطئة، بالقياس

Written Explanation

The experiment

We want to compare one operation, "is this number in the collection?", on two structures that hold the same 100,000 integers, 0 to 99,999. We ask 10,000 questions on each and measure the total time.

To avoid timing the cheapest case, we look up values from the end of the range (99,999 down to 90,000). A list scans from the front, so these lookups walk almost the whole list every time. Every lookup is a hit, and we count hits to prove the code did what we think.

How to time code

System.nanoTime() returns a number of nanoseconds from an arbitrary starting point. Its documentation says to use it only to measure elapsed time, by subtracting two readings, not as a clock. A nanosecond is a billionth of a second, so we divide to get friendlier units.

long start = System.nanoTime();
// ... the work being measured ...
long elapsed = System.nanoTime() - start;

The program

import java.util.*;

public class Bench {
    static int N = 100_000;
    static final int LOOKUPS = 10_000;

    static long timeLookups(Collection<Integer> c) {
        int hits = 0;
        long start = System.nanoTime();
        for (int i = 0; i < LOOKUPS; i++) {
            if (c.contains(N - 1 - i)) hits++;
        }
        long elapsed = System.nanoTime() - start;
        if (hits != LOOKUPS) System.out.println("unexpected hits " + hits);
        return elapsed / 1_000;   // microseconds
    }

    public static void main(String[] args) {
        if (args.length > 0) N = Integer.parseInt(args[0]);
        List<Integer> list = new ArrayList<>();
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < N; i++) { list.add(i); set.add(i); }
        for (int run = 1; run <= 5; run++) {
            long listUs = timeLookups(list);
            long setUs = timeLookups(set);
            System.out.println("run " + run + ": list " + listUs + " us, set " + setUs + " us");
        }
    }
}

A few details. The method takes a Collection<Integer>, so the same timing code serves both structures, which keeps the comparison fair (Lesson 1). The underscores in 100_000 are just readability separators in number literals. N - 1 - i is an int, and Java automatically converts it to an Integer for contains. Setting args[0] lets us change the size from the command line (BEG-007).

What the results mean

One run of this program on the JDK 21 used for this lesson printed:

run 1: list 2783642 us, set 1447 us
run 2: list 2708372 us, set 584 us
run 3: list 2723488 us, set 208 us
run 4: list 2748484 us, set 145 us
run 5: list 2687757 us, set 152 us

Read the units: the list needed roughly 2.7 seconds for 10,000 lookups, the set a fraction of a millisecond to about one and a half. That is a difference of thousands of times, and it is the same ranking on every run even though the individual numbers move.

Why? ArrayList.contains starts at index 0 and compares each element with equals until it finds a match, so looking up a value near the end touches nearly all 100,000 elements. HashSet.contains uses the value's hashCode() to jump to the right place and compares only a handful of elements (Lessons 3 and BEG-026). The HashSet documentation says its basic operations take constant time, assuming a good hash function, while the list's cost grows with its size.

The planned mistake: trusting one run

Look at the set column: run 1 took 1447 microseconds, and runs 4 and 5 about 150. The program did not change, but the first run was about ten times slower. The Java virtual machine starts by running code in a slower mode and optimizes it after seeing it repeatedly (a "warm-up"); other programs on your computer also add noise. If you had stopped after run 1 you would have reported a slower set than the real steady state, and a different run on a busy machine might even reverse a small difference.

The habit this teaches:

• Repeat the measurement several times and look at the whole set of numbers.
• Discard or flag the first run when measuring something small.
• Prefer big differences (thousands of times) as evidence; ignore small differences (10% or 20%) from a simple benchmark like this.

Professional benchmarking uses a dedicated tool (the Java Microbenchmark Harness, JMH) to handle warm-up and other pitfalls. A loop with nanoTime is a good teaching tool and a rough sanity check, but not a basis for fine-grained decisions.

Does the size matter?

Run the program with a different size, for example java Bench 50000 and java Bench 200000. In the runs recorded for this lesson, the list's total time for 10,000 lookups rose from about 0.7 seconds at 50,000 elements to about 2.7 seconds at 100,000 and about 7 seconds at 200,000, while the set stayed in the range of a few hundred microseconds. The list grows with the size; the set barely notices. Your numbers will differ, and the list time may grow faster than the size because larger data also hurts memory behavior. We therefore make only the safe claim: the list gets slower as the data grows; the set does not.

Maps and other comparisons

The same reasoning applies to Map: a HashMap.containsKey on 100,000 keys for the same 10,000 queries took under a millisecond in a single run on the same machine, roughly the same as the set. Another experiment from Lesson 2: reading the middle element by index 2,000 times took about 0.2 to 0.7 ms on an ArrayList and about 0.35 to 0.63 seconds on a LinkedList of 100,000 elements, because the linked list must walk to the middle each time.

What the benchmark does not show: the cost of building the set (it uses more memory than the list), or what happens with tiny collections. For 10 elements a list scan is trivially fast, and the choice does not matter for speed; it still matters for meaning (uniqueness, key lookup). Choose by the requirement first (Lesson 6), and use measurement to confirm a suspected problem, not to guess one.