8
\$\begingroup\$

Note

This post is a continuation of Discrete event simulation of a prioritized lunch queue in Java (Data structures). Please refer to it for problem description.

This part about "algorithms": all classes that are more about doing rather than representing information.


PrioritizedQueue.java:

package net.coderodde.simulation.lunch;

import java.util.ArrayDeque;
import java.util.EnumMap;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Queue;

/**
 * This class implements a FIFO queue over priority categories. Not to be 
 * confused with a priority queue.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Dec 3, 2015)
 */
final class PrioritizedQueue {

    private final Map<AcademicDegree, Queue<LunchQueueEvent>> map 
            = new EnumMap<>(AcademicDegree.class);

    private int size;

    void push(LunchQueueEvent event) {
        AcademicDegree degree = event.getPerson().getAcademicDegree();
        map.putIfAbsent(degree, new ArrayDeque<>());
        map.get(degree).add(event);
        ++size;
    }

    boolean isEmpty() {
        return size == 0;
    }

    LunchQueueEvent pop() {
        if (isEmpty()) {
            throw new NoSuchElementException(
                    "Popping from an empty prioritized queue.");
        }

        for (Queue<LunchQueueEvent> queue : map.values()) {
            if (!queue.isEmpty()) {
                --size;
                return queue.remove();
            }
        }

        throw new IllegalStateException(
                "This should never happend. Please debug.");
    }
}

RandomPopulationGenerator.java:

package net.coderodde.simulation.lunch;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.Random;
import static net.coderodde.simulation.lunch.Utils.checkMean;
import static net.coderodde.simulation.lunch.Utils.checkStandardDeviation;

/**
 * This class facilitates random generation of population.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Dec 2, 2015)
 */
public final class RandomPopulationGenerator {

    private final Random random;
    private final Map<AcademicDegree, Integer> distribution;
    private final double meanLunchTime;
    private final double standardDeviationOfLunchTime;

    /**
     * Initiates the strong fluent API for constructing a 
     * {@code RandomPopulationGenerator}.
     * 
     * @param  random the random number generator to use.
     * @return a degree selector.
     */
    public static DegreeCountSelector withRandom(Random random) {
        Objects.requireNonNull(random, "The input Random is null.");
        Configuration configuration = new Configuration();
        configuration.random = random;
        return new DegreeCountSelector(configuration);
    }

    /**
     * Initiates the strong fluent API for constructing a 
     * {@code RandomPopulationGenerator} using a default {@code Random}.
     * 
     * @return a degree selector.
     */
    public static DegreeCountSelector withDefaultRandom() {
        return withRandom(new Random());
    }

    public static final class DegreeCountSelector {

        private final Configuration configuration;

        DegreeCountSelector(Configuration configuration) {
            this.configuration = configuration;
        }

        /**
         * Starts constructing a population  wit selected academic degree.
         * 
         * @param  count the number of persons for a degree group.
         * @return a degree selector for the group being constructed.
         */
        public DegreeSelector with(int count) {
            if (count < 0) {
                throw new IllegalArgumentException(
                        "The people count is negative: " + count);
            }

            return new DegreeSelector(configuration, count);
        }

        /**
         * Terminates creation of groups and selects a mean time at which people
         * go for a lunch. (Lunch time does not mean the duration of a lunch.)
         * 
         * @param  meanLunchTime the mean of lunch times 
         * @return a standard deviation selector.
         */
        public StandardDeviationSelector 
            withMeanLunchTime(double meanLunchTime) {
            checkMean(meanLunchTime);
            configuration.meanLunchTime = meanLunchTime;
            return new StandardDeviationSelector(configuration);
        }
    }

    public static final class DegreeSelector {

        private final Configuration configuration;
        private final int count;

        DegreeSelector(Configuration configuration, int count) {
            this.configuration = configuration;
            this.count = count;
        }

        public DegreeCountSelector peopleWithDegree(AcademicDegree degree) {
            Objects.requireNonNull(degree, "The input degree is null.");
            configuration.distribution.put(degree, count);
            return new DegreeCountSelector(configuration);
        }
    }

    public static final class StandardDeviationSelector {

        private final Configuration configuration;

        StandardDeviationSelector(Configuration configuration) {
            this.configuration = configuration;
        }

        /**
         * Selects the standard deviation and generates a population with
         * specified parameters.
         * 
         * @param  lunchTimeStandardDeviation the standard deviation of the 
         *                                    times at which people go to lunch.
         * @return a population.
         */
        public Population withLunchTimeStandardDeviation(
                double lunchTimeStandardDeviation) {
            checkStandardDeviation(lunchTimeStandardDeviation);
            return new RandomPopulationGenerator(
                    configuration.random,
                    configuration.distribution,
                    configuration.meanLunchTime,
                    lunchTimeStandardDeviation).generate();
        }
    }

    private RandomPopulationGenerator(Random random, 
                                      Map<AcademicDegree, Integer> distribution,
                                      double meanLunchTime,
                                      double standardDeviationOfLunchTime) {
        this.random       = random;
        this.distribution = distribution;
        this.meanLunchTime = meanLunchTime;
        this.standardDeviationOfLunchTime = standardDeviationOfLunchTime;
    }

    public Population generate() {
        int populationSize = 0;

        for (Map.Entry<AcademicDegree, Integer> entry : distribution.entrySet()) {
            populationSize += entry.getValue();
        }

        List<Person> allPersonList = 
                new ArrayList<>(FIRST_NAMES.length * LAST_NAMES.length);

        List<AcademicDegree> degreeList = new ArrayList<>(populationSize);

        for (AcademicDegree degree : AcademicDegree.values()) {
            int count = distribution.getOrDefault(degree, 0);

            for (int i = 0; i < count; ++i) {
                degreeList.add(degree);
            }
        }


        Collections.<AcademicDegree>shuffle(degreeList, random);
        int i = 0;

        outer:
        for (String firstName : FIRST_NAMES) {
            for (String lastName : LAST_NAMES) {
                if (i == degreeList.size()) {
                    break outer;
                }

                allPersonList.add(Person.withFirstName(firstName)
                                        .withLastName(lastName)
                                        .withAcademicDegree(degreeList.get(i)));
                ++i;
            }
        }

        Collections.shuffle(allPersonList, random);
        populationSize = Math.min(populationSize, allPersonList.size());

        Population population = new Population();

        for (i = 0; i < populationSize; ++i) {
            population.addPerson(allPersonList.get(i))
                      .withArrivalTime(getRandomLunchTime());
        }

        return population;
    }

    private int getRandomLunchTime() {
        return (int)(meanLunchTime + standardDeviationOfLunchTime * 
                                     random.nextGaussian());
    }

    private static final class Configuration {
        private final Map<AcademicDegree, Integer> distribution = 
                new HashMap<>();

        private Random random;
        private double meanLunchTime;
    }

    private static final String[] FIRST_NAMES = {
        "Ada",
        "Alice",
        "Al",
        "Alma",
        "Alvin",
        "Amanda",
        "Bob",
        "Brandon",
        "Brooke",
        "Bruce",
        "Camilla",
        "Cecilia",
        "Carl",
        "David",
        "Elsa",
        "Ida",
        "Jack",
        "John",
        "Nathan",
        "Nick",
        "Phoebe",
        "Rachel",
        "Richard",
        "Rodion",
        "Roger",
        "Roland",
        "Rolf",
        "Roy",
        "Terence",
        "Terry",
        "Viola"
    };

    private static final String[] LAST_NAMES = {
        "Abbey",
        "Ackerman",
        "Bonham",
        "Bradly",
        "Cantrell",
        "Carter",
        "Dawkins",
        "Dawson",
        "Edison",
        "Efremov",
        "Fay",
        "Fleming",
        "Garrett",
        "Hallman",
        "Irvine",
        "Jacobson",
        "Kidd",
        "Lacey",
        "Marlow",
        "Nelson",
        "Oliver",
        "Parks",
        "Pearson",
        "Peterson",
        "Quincey",
        "Ridley",
        "Saunders",
        "Thompson",
        "Walton",
        "Wilkerson"
    };
}

Simulator.java:

package net.coderodde.simulation.lunch;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.Queue;

/**
 * This class runs the lunch queue simulation.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Dec 2, 2015)
 */
public final class Simulator {

    //// Internals.
    private final Map<Person, LunchQueueEvent> arrivalEventMap = 
            new HashMap<>();
    private final Map<Person, LunchQueueEvent> servedEventMap = 
            new HashMap<>();
    private final Map<AcademicDegree, Integer> groupCounts = new HashMap<>();

    private final Map<AcademicDegree, Integer> mapMinimumWaitTime = 
            new HashMap<>();
    private final Map<AcademicDegree, Integer> mapMaximumWaitTime = 
            new HashMap<>();
    private final Map<AcademicDegree, Integer> mapAverageWaitTime = 
            new HashMap<>();
    private final Map<AcademicDegree, Integer> mapWaitTimeSum     = 
            new HashMap<>();
    private final Map<AcademicDegree, Integer> mapWaitTimeDeviation = 
            new HashMap<>();

    private final List<Integer> cashierIdleIntervals = new ArrayList<>();
    private Population population;

    public static PopulationSelector simulate() {

        return new PopulationSelector();
    }

    public static final class PopulationSelector {

        public CashierSelector withPopulation(Population population) {
            Objects.requireNonNull(population, "The input population is null.");
            return new CashierSelector(population);
        }
    }

    public static final class CashierSelector {

        private final Population population;

        CashierSelector(Population population) {
            this.population = population;
        }

        public SimulationResult withCashier(Cashier cashier) {
            Objects.requireNonNull(cashier, "The input cashier is null.");
            return new Simulator().simulate(population, cashier);
        }
    }

    private SimulationResult simulate(Population population, Cashier cashier) {
        this.population = population;
        Queue<LunchQueueEvent> inputEventQueue = population.toEventQueue();
        preprocess(inputEventQueue);

        if (population.size() == 0) {
            return new SimulationResult(arrivalEventMap, servedEventMap);
        }

        PrioritizedQueue QUEUE = new PrioritizedQueue();
        int currentClock = inputEventQueue.peek().getTimestamp();

        for (int personsPending = population.size();
                personsPending > 0;
                personsPending--) {
            // Load all hungry people that arrived during the service of the 
            // previously served person.
            while (!inputEventQueue.isEmpty()
                    && inputEventQueue.peek().getTimestamp() 
                    <= currentClock) {
                QUEUE.push(inputEventQueue.remove());
            }

            if (QUEUE.isEmpty()) {
                LunchQueueEvent headEvent = inputEventQueue.remove();
                cashierIdleIntervals.add(headEvent.getTimestamp() - 
                                         currentClock);
                currentClock = headEvent.getTimestamp();
                QUEUE.push(headEvent);
            } else {
                cashierIdleIntervals.add(0);
            }

            // Admit an earliest + highest priority person to the cashier.
            LunchQueueEvent currentEvent = QUEUE.pop();
            Person currentPerson = currentEvent.getPerson();

            // Serving...
            int serviceTime = cashier.getServiceTime();
            currentClock += serviceTime;
            LunchQueueEvent servedEvent = new LunchQueueEvent(currentPerson, 
                                                              currentClock);
            servedEventMap.put(currentPerson, servedEvent);
            // Served!
        }

        return postprocess();
    }

    private void preprocess(Queue<LunchQueueEvent> inputEventQueue) {
        // groupCounts.keySet() will now list only those academic degrees that
        // are present in the population.
        for (LunchQueueEvent event : inputEventQueue) {
            Person person = event.getPerson();
            arrivalEventMap.put(person, event);
            AcademicDegree degree = person.getAcademicDegree();
            groupCounts.put(degree, groupCounts.getOrDefault(degree, 0) + 1);
        }
    }

    private void initWaitingTimeStructures() {
        for (AcademicDegree degree : groupCounts.keySet()) {
            mapMinimumWaitTime.put(degree, Integer.MAX_VALUE);
            mapMaximumWaitTime.put(degree, Integer.MIN_VALUE);
            mapWaitTimeSum.put(degree, 0);
        }
    }

    private void precomputeWaitingTimes() {
        for (Person person : population.getPersonSet()) {
            LunchQueueEvent arrivalEvent = arrivalEventMap.get(person);
            LunchQueueEvent servedEvent  = servedEventMap.get(person);

            int waitTime = servedEvent.getTimestamp() - 
                           arrivalEvent.getTimestamp();

            AcademicDegree degree = person.getAcademicDegree();

            if (mapMinimumWaitTime.get(degree) > waitTime) {
                mapMinimumWaitTime.put(degree, waitTime);
            }

            if (mapMaximumWaitTime.get(degree) < waitTime) {
                mapMaximumWaitTime.put(degree, waitTime);
            }

            mapWaitTimeSum.put(degree, mapWaitTimeSum.get(degree) + waitTime);
        }
    }

    private void precomputeDeviationsPhase1() {
        for (AcademicDegree degree : groupCounts.keySet()) {
            int average = (int) Math.round(1.0 * mapWaitTimeSum.get(degree) / 
                                           groupCounts.get(degree));

            mapAverageWaitTime.put(degree, average);
            mapWaitTimeDeviation.put(degree, 0);
        }
    }

    private void precomputeDeviationsPhase2() {
        for (Person person : population.getPersonSet()) {
            AcademicDegree degree = person.getAcademicDegree();

            int duration = servedEventMap.get(person).getTimestamp() -
                          arrivalEventMap.get(person).getTimestamp();

            int contribution = duration - mapAverageWaitTime.get(degree);

            contribution *= contribution;
            mapWaitTimeDeviation.put(degree, 
                                     mapWaitTimeDeviation.get(degree) +
                                             contribution);
        }
    }

    private void computeStandardDeviations() {
        for (AcademicDegree degree : groupCounts.keySet()) {
            int sum = mapWaitTimeDeviation.get(degree);
            mapWaitTimeDeviation.put(degree, 
                                     (int) Math.round(
                                             Math.sqrt(sum / 
                                                       groupCounts
                                                               .get(degree))));
        }
    }

    private void loadStatistics(SimulationResult result) {
        for (AcademicDegree degree : groupCounts.keySet()) {
            result.putWaitMinimumTime(degree, mapMinimumWaitTime.get(degree));
            result.putWaitMaximumTime(degree, mapMaximumWaitTime.get(degree));
            result.putAverageWaitTime(degree, mapAverageWaitTime.get(degree));
            result.putWaitTimeStandardDeviation(degree,
                                                mapWaitTimeDeviation
                                                        .get(degree));
        }
    }

    private void computeCashierStatistics(SimulationResult result) {
        if (cashierIdleIntervals.isEmpty()) {
            return;
        }

        int sum = 0;
        int min = cashierIdleIntervals.get(0);
        int max = cashierIdleIntervals.get(0);

        for (int value : cashierIdleIntervals) {
            sum += value;

            if (min > value) {
                min = value;
            } else if (max < value) {
                max = value;
            }
        }

        double average = 1.0 * sum / cashierIdleIntervals.size();

        sum = 0;

        // Compute standard deviation:
        for (int value : cashierIdleIntervals) {
            double diff = average - value;
            diff *= diff;
            sum += diff;
        }

        int standardDeviation = 
                (int)(Math.round(
                        Math.sqrt(1.0 *sum / cashierIdleIntervals.size())));

        result.putCashierMinimumIdleTime(min);
        result.putCashierAverageIdleTime((int)(Math.round(average)));
        result.putCashierMaximumIdleTime(max);
        result.putCashierStandardDeviation(standardDeviation);
    }

    private SimulationResult postprocess() {
        initWaitingTimeStructures();
        precomputeWaitingTimes();
        precomputeDeviationsPhase1();
        precomputeDeviationsPhase2();
        computeStandardDeviations();

        SimulationResult result = new SimulationResult(arrivalEventMap, 
                                                       servedEventMap);
        loadStatistics(result);
        computeCashierStatistics(result);
        return result;
    }
}

Demo.java:

import java.util.Random;
import net.coderodde.simulation.lunch.AcademicDegree;
import net.coderodde.simulation.lunch.Cashier;
import net.coderodde.simulation.lunch.Population;
import net.coderodde.simulation.lunch.RandomPopulationGenerator;
import net.coderodde.simulation.lunch.SimulationResult;
import net.coderodde.simulation.lunch.Simulator;

public class Demo {

    public static void main(final String... args) {
        long seed = System.nanoTime();
        Random random = new Random(seed);

        Population population = 
                RandomPopulationGenerator 
                .withRandom(random)
                .with(15).peopleWithDegree(AcademicDegree.DOCTOR)
                .with(40).peopleWithDegree(AcademicDegree.MASTER)
                .with(100).peopleWithDegree(AcademicDegree.BACHELOR)
                .with(250).peopleWithDegree(AcademicDegree.UNDERGRADUATE)
                .withMeanLunchTime(10800.0)
                .withLunchTimeStandardDeviation(1200.0);

        // Cashier serves in average in 15 seconds, s.d. 2 seconds.
        Cashier cashier = Cashier.withRandom(random)
                                 .withMeanServiceTime(15.0)
                                 .withStandardDeviationOfServiceTime(2.0);

        System.out.println("Seed = " + seed);

        long startTime = System.nanoTime();
        SimulationResult result = Simulator.simulate()
                                           .withPopulation(population)
                                           .withCashier(cashier);
        long endTime = System.nanoTime();

        System.out.printf("Simulated in %.2f milliseconds.\n", 
                          (endTime - startTime) / 1e6);

        System.out.println(result);
    }
}

Is my coding style/naming conventions/API design reasonable on this part? Any critique much appreciated!

\$\endgroup\$
2
\$\begingroup\$

This is an interesting programming exercise. I appreciate that you made a significant attempt to make your code elegant, but it didn't work out that well, in my opinion.

I'm not a fan of the Niklaus Wirth quote in your related question ("Algorithms + Data Structures = Programs"). Data structures should be designed to support your algorithms, and there is opportunity for the sum to be greater than the parts, if they work together well. (Example: the Union-Find data structure, which is the heart of the associated algorithm.) This synergy is especially important for an object-oriented language like Java, in which the goal is to design classes that act like "smart data".

Anyway, I find it hard to split the review for that reason, and will just answer everything here.

As for the code length… I've written a solution in ~400 lines, about a third of your solution of ~1200 lines. Granted, about 90 of your lines were dedicated to naming your model customers (Why bother?), but still, that's a substantial simplification.

Fluent interface

A lot of the complexity in the code goes to support the fluent configuration calls used in Demo.main(). It feels like you are trying to mold Java into Objective C. I think it's a bad idea because

  • These clauses tend to introduce different scopes. For example, the with() clause needs to be followed by a peopleWithDegree() call. It's not obvious what the correct "grammar" of the "sentence" has to be.

    In contrast, chained calls work very well for jQuery since every call produces a jQuery object just like any other jQuery object.

    It would help a bit if you toned down the interface by "uncurrying" the calls. If you had…

    withNPeopleWithDegree(15, AcademicDegree.DOCTOR)
    

    … then at least you wouldn't be introducing another grammatical context ("selectors", as you call them in your code).

  • The grammar is somewhat arbitrary, and adherence to the grammar makes your code rigid. Who would guess withCashier(…) is the special clause at the end of the "sentence" that kicks off the simulation (in Simulator.CashierSelector.withCashier(…))?

    Even more surprising: who would guess that Simulator.simulate() doesn't kick off a simulation at all, but merely returns a PopulationSelector? (Note that the public Simulator.simulate() is completely different from the private Simulator.simulate(Population, Cashier), which is weird.)

    Note that your grammar is inspired by English word order, which isn't necessarily the most logical word order. A Subject-Object-Verb language would have avoided this specific problem with simulate().

  • It's still a lot of code for little benefit. It's debatable whether it makes your Demo.main() more readable, but you definitely pay the price in the clutter you introduce to RandomPopulationGenerator.

    If you really wanted an elegant way to configure the simulation parameters, why not just implement a configuration file format, perhaps based on or ?

The Simulator and Demo classes are tightly coupled to each other. Demo is nothing more than a main() method to launch Simulator with specific parameters. I suggest merging the two classes.

Models

I think that you are modelling the problem too literally. You would be better off naming your classes using standard vocabulary from queuing theory, rather than the objects specific to this scenario. The code would be more reusable, and easier to understand by other programmers. For example,

  • Cashier is a "server"
  • Person is a "customer"
  • AcademicDegree is a "customer class"

Note that you can still name instances using scenario-specific words (e.g. Server cashier = new Server(…)).

You modelled the queue discipline as a single PrioritizedQueue. When certain customers can queue-jump, I'm not sure that it's fair to call it a "queue" anymore. I'd call it four queues. (That's how the priority scheme would be implemented in real life, right?) With four queues, you can eliminate the awkward PrioritizedQueue class that is, in your own words, "not to be confused with a priority queue".

Accounting

The accounting is complicated by the fact that the statistics are not stored with the associated objects. Rather, you have a SimulationResult that is calculated in Simulator.postprocess() from the arrivalEventMap and the servedEventMap. (You also have an inexplicable special case in Simulator.simulate(Population, Cashier) for zero-sized populations.)

The presence of helper methods in Simulatorpreprocess(), initWaitingTimeStructures(), precomputeWaitingTimes(), precomputeDeviationsPhase1(), precomputeDeviationsPhase2(), computeStandardDeviations(), loadStatistics(), computeCashierStatistics(), and postprocess() — is a code smell. The fact that it takes so many steps, which probably need to be executed in a specific order, indicates that the code is fragile. If you have a good OOP design, no pre- and post-processing should be necessary: you simply say what you want to do, and the method should just work.

The SimulationResult class feels repetitive, with a lot of almost copy-and-paste code.

Event handling

The main event loop should be very simple and generic. Rather, you have a Simulator.simulate(Population, Cashier) method that is rather complicated.

First of all, while accepting parameters Population and Cashier might work for a simple system like this, it wouldn't scale well to more complex systems. The state of the simulation should be held in the Simulator instance.

Let's look at the main loop.


for (int personsPending = population.size();
        personsPending > 0;
        personsPending--) {
    …
}

Why does the population size need to be known in advance? Each iteration through the loop means that one customer is served. This assumption won't scale to handle more complex scenarios, where all sorts of events could be happening. (Some people may balk and leave if the queue is too long. You might want to add a salad bar and a sandwich bar to the system.)

    // Load all hungry people that arrived during the service of the 
    // previously served person.
    while (!inputEventQueue.isEmpty()
            && inputEventQueue.peek().getTimestamp()
            <= currentClock) {
        QUEUE.push(inputEventQueue.remove());
    }

The while loop to properly enqueue all of the hungry people who were scheduled to arrive while the cashier was busy is also awkward. This is a form of time travel, necessitated by poor logic later in the loop.

To solution to both of those problems is to make the loop event-based: each iteration of the loop represents one event, be it a customer entering the queue, the cashier finishing a transaction, or a customer walking from the salad bar to the sandwich bar.


    if (QUEUE.isEmpty()) {
        LunchQueueEvent headEvent = inputEventQueue.remove();
        cashierIdleIntervals.add(headEvent.getTimestamp() -
                                 currentClock);
        currentClock = headEvent.getTimestamp();
        QUEUE.push(headEvent);
    } else {
        cashierIdleIntervals.add(0);
    }

That's weird. There is a separate codepath for enqueuing a person who arrives while the queue is empty.

And why is the main simulation loop responsible for tracking the cashier's idle time? Why can't the cashier track its own idle time?


    // Admit an earliest + highest priority person to the cashier.
    LunchQueueEvent currentEvent = QUEUE.pop();
    Person currentPerson = currentEvent.getPerson();

That's fine, except that it's not immediately obvious why QUEUE.pop() must succeed. (It's because the if (QUEUE.isEmpty()) branch causes a QUEUE.push(headEvent), and the inputEventQueue.remove() that produces headEvent must succeed because… well, the explanation is complicated.)


    // Serving...
    int serviceTime = cashier.getServiceTime();
    currentClock += serviceTime;
    LunchQueueEvent servedEvent = new LunchQueueEvent(currentPerson,
                                                      currentClock);
    servedEventMap.put(currentPerson, servedEvent);
    // Served!

The currentClock += serviceTime line is responsible for the time-travel problem mentioned earlier. When you advance the clock by the cashier's serviceTime, you potentially skip over arrival events that occurred in the interim, this requiring you to retroactively enqueue those people in the next loop iteration.

Attaching the servedEvent to the person is an indirect way to account for the person's use of time. As mentioned before, the accounting code would be simplified if you just recorded the elapsed time right here.

Suggested solution

Since this was such a fun problem to solve, I wrote a solution from scratch. I've taken advantage of Java 8's DoubleStream in a few places, but you could backport it using lists and arrays instead.

Generic support for discrete-event simulation

The classes RandomDistribution, NormalDistribution, Event, EventHandler, Statistic, and Simulation could be useful for any discrete-event simulation.

RandomDistribution.java

import java.util.Random;
import java.util.stream.DoubleStream;

public interface RandomDistribution {
    double next(Random r);

    default DoubleStream generate(Random r, int howMany) {
        return DoubleStream.generate(() -> this.next(r)).limit(howMany);
    }
}

NormalDistribution.java

import java.util.Random;
import java.util.stream.DoubleStream;

public class NormalDistribution implements RandomDistribution {
    public final double mean, sd;

    public NormalDistribution() {
        this(1, 1);
    }

    public NormalDistribution(double mean, double sd) {
        this.mean = mean;
        this.sd = sd;
    }

    @Override
    public double next(Random r) {
        return this.mean + this.sd * r.nextGaussian();
    }
}

Event.java

public class Event implements Comparable<Event> {
    public final double time;
    public final EventHandler handler;
    public final Object what;

    public Event(double time, EventHandler handler, Object what) {
        this.time = time;
        this.handler = handler;
        this.what = what;
    }

    @Override
    public int compareTo(Event e) {
        return Double.compare(this.time, e.time);
    }
}

EventHandler.java

public interface EventHandler {
    default void handleEvent(double time, Object what) {
    }
}

Statistic.java

import java.util.Arrays;
import java.util.DoubleSummaryStatistics;
import java.util.stream.DoubleStream;

/**
 * Wrapper for DoubleSummaryStatistics that supports standard deviation.
 */
public class Statistic {
    private DoubleStream.Builder builder = DoubleStream.builder();
    private double[] values;
    private DoubleSummaryStatistics summary;

    public void accept(double d) {
        builder.accept(d);
    }

    private void close() {
        if (this.values == null) {
            this.values = this.builder.build().toArray();
            this.summary = Arrays.stream(this.values).summaryStatistics();
        }
    }

    public long getCount() {
        this.close();
        return this.summary.getCount();
    }

    public double getMin() {
        this.close();
        return this.summary.getMin();
    }

    public double getMax() {
        this.close();
        return this.summary.getMax();
    }

    public double getAverage() {
        this.close();
        return this.summary.getAverage();
    }

    public double getStandardDeviation() {
        double avg = this.getAverage();
        return Math.sqrt(Arrays.stream(this.values).map((d) -> (d - avg) * (d - avg)).sum()) / Math.sqrt(this.getCount());
    }
}

Simulation.java

import java.util.PriorityQueue;
import java.util.Random;

public abstract class Simulation {
    private final Random random;
    private final PriorityQueue<Event> eventTimes = new PriorityQueue<>();
    private double time;

    protected Simulation(Random random) {
        this.random = random;
    }

    public Random getRandom() {
        return this.random;
    }

    public double getTime() {
        return this.time;
    }

    /**
     * Schedules a callback at a specified time.
     *
     * @param time    The time of the event (no earlier than the current time)
     * @param handler The EventHandler whose handleEvent() is to be called
     * @param what    Optional information to be passed to the event handler
     */
    public void scheduleEvent(double time, EventHandler handler, Object what) {
        assert time > this.getTime();
        this.eventTimes.add(new Event(time, handler, what));
    }

    /**
     * Calls handleEvent(Event) for all scheduled events.
     */
    public void run() {
        while (!this.eventTimes.isEmpty()) {
            this.handleEvent(this.eventTimes.poll());
        }
    }

    /**
     * Advances time and calls the event handler for the event.
     */
    protected void handleEvent(Event e) {
        this.time = e.time;
        if (e.handler != null) {
            e.handler.handleEvent(this.time, e.what);
        }
    }
}

Scenario-specific classes

Then we have the objects in our scenario: Server, Customer, and CustomerClass. The LunchSimulation class ties everything together.

Instead of printing out each person's experience, I've chosen to display an animation of the queue lengths instead. You can suppress the animation by commenting out LunchSimulation.handleEvent().

Server.java

public class Server implements EventHandler {
    private final LunchSimulation sim;
    private final RandomDistribution serviceTimes;
    private final Statistic idleTimes = new Statistic();
    private Customer currentCustomer;

    // Set to NaN to disregard idle time before the first customer
    private double idleStarted = Double.NaN;

    public Server(LunchSimulation sim, RandomDistribution serviceTimes) {
        this.sim = sim;
        this.serviceTimes = serviceTimes;
    }

    public boolean isBusy() {
        return this.currentCustomer != null;
    }

    public void accept(Customer c) {
        assert !this.isBusy();
        this.currentCustomer = c;
        double now = this.sim.getTime();
        if (!Double.isNaN(this.idleStarted)) {
            idleTimes.accept(now - this.idleStarted);
        }
        c.service(now);
        double serviceTime = this.serviceTimes.next(this.sim.getRandom());
        double willFinish = this.sim.getTime() + serviceTime;
        this.sim.scheduleEvent(willFinish, this, "done");
    }

    @Override
    public void handleEvent(double time, Object what) {
        assert "done".equals(what);
        assert this.isBusy();
        this.currentCustomer.exit(time);
        this.currentCustomer = null;
        this.idleStarted = time;
        this.sim.advanceQueue();
    }

    public Statistic getIdleTimes() {
        return this.idleTimes;
    }
}

Customer.java

public class Customer {
    private final CustomerClass customerClass;
    private double queuingTime = Double.NaN,
                   servicingTime = Double.NaN,
                   lastTransitionTime = Double.NaN;

    public Customer(CustomerClass cls) {
        this.customerClass = cls;
    }

    public void enqueue(double time) {
        assert Double.isNaN(this.lastTransitionTime);
        assert Double.isNaN(this.queuingTime);
        this.lastTransitionTime = time;
    }

    public void service(double time) {
        assert Double.isNaN(this.queuingTime);
        assert !Double.isNaN(this.lastTransitionTime);
        this.queuingTime = time - this.lastTransitionTime;
        this.lastTransitionTime = time;
    }

    public void exit(double time) {
        assert Double.isNaN(this.servicingTime);
        assert !Double.isNaN(this.lastTransitionTime);
        this.servicingTime = time - this.lastTransitionTime;
        this.lastTransitionTime = time;
        this.customerClass.exited(this);
    }

    public double getQueuingTime() {
        return this.queuingTime;
    }

    public double getServicingTime() {
        return this.servicingTime;
    }
}

CustomerClass.java

import java.util.Arrays;
import java.util.LinkedList;
import java.util.NoSuchElementException;
import java.util.Queue;
import java.util.stream.DoubleStream;

public class CustomerClass implements EventHandler {
    private final LunchSimulation sim;
    private final String name;
    private final Queue<Customer> q = new LinkedList<Customer>();
    private final Statistic queuingTimes = new Statistic(),
                            waitingTimes = new Statistic();

    public CustomerClass(LunchSimulation sim, String name) {
        this.sim = sim;
        this.name = name;
    }

    @Override
    public String toString() {
        return this.name;
    }

    public CustomerClass scheduleArrivals(DoubleStream arrivalTimes) {
        arrivalTimes.forEach((time) -> this.sim.scheduleEvent(time, this, "arrival"));
        return this;
    }

    @Override
    public void handleEvent(double time, Object what) {
        assert "arrival".equals(what);
        Customer c = new Customer(this);
        c.enqueue(time);
        this.q.add(c);
        this.sim.advanceQueue();
    }

    public int getQueueLength() {
        return this.q.size();
    }

    public Customer nextCustomer() throws NoSuchElementException {
        return this.q.poll();
    }

    /**
     * Note customer experience statistics after exiting the system.
     */
    public void exited(Customer c) {
        this.queuingTimes.accept(c.getQueuingTime());
        this.waitingTimes.accept(c.getQueuingTime() + c.getServicingTime());
    }

    public Statistic getQueuingTimes() {
        return this.queuingTimes;
    }

    public Statistic getWaitingTimes() {
        return this.waitingTimes;
    }
}

LunchSimulation.java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Random;

public class LunchSimulation extends Simulation {
    private final List<CustomerClass> customerClasses = new ArrayList<>();
    private final List<Server> servers = new ArrayList<>();

    public LunchSimulation(Random random) {
        super(random);
    }

    public void addCustomerClass(CustomerClass q) {
        this.customerClasses.add(q);
    }

    public List<CustomerClass> getCustomerClasses() {
        return Collections.unmodifiableList(this.customerClasses);
    }

    public void addServer(Server s) {
        this.servers.add(s);
    }

    public List<Server> getServers() {
        return Collections.unmodifiableList(this.servers);
    }

    /**
     * Possibly move one customer to a server, if a server is free and any
     * customer is queued.  Triggered by either a customer arrival or a server
     * done event.
     */
    public void advanceQueue() {
        for (Server server : this.servers) {
            if (!server.isBusy()) {
                for (CustomerClass cls : this.customerClasses) {
                    if (cls.getQueueLength() > 0) {
                        server.accept(cls.nextCustomer());
                        break;
                    }
                }
                break;
            }
        }
    }

    /**
     * Optional ASCII art visualiation of the queues.
     */
    @Override
    public void handleEvent(Event e) {
        if (this.getTime() > 0) try {
            Thread.sleep((long)(e.time - this.getTime()));
        } catch (InterruptedException exc) {}

        super.handleEvent(e);

        // ESC[2J clears the screen
        // ESC[H  moves the cursor to the top left
        System.err.printf("\u001b[2J\u001b[HTime: %11.3f\n", this.getTime());
        for (CustomerClass c : this.customerClasses) {
            char[] bar = new char[c.getQueueLength()];
            Arrays.fill(bar, '#');
            System.err.printf("%13s %s\n", c, new String(bar));
        }
    }

    public static void main(String[] args) {
        long seed = (args.length > 0) ? Long.valueOf(args[0]) : System.nanoTime();
        System.out.println("Seed = " + seed);
        Random rand = new Random(seed);

        /* Configure */
        long startTime = System.nanoTime();

        LunchSimulation sim = new LunchSimulation(rand);

        RandomDistribution lunchTimes = new NormalDistribution(10800, 1200);
        sim.addCustomerClass(new CustomerClass(sim, "PhD").scheduleArrivals(lunchTimes.generate(rand, 15)));
        sim.addCustomerClass(new CustomerClass(sim, "MSc").scheduleArrivals(lunchTimes.generate(rand, 40)));
        sim.addCustomerClass(new CustomerClass(sim, "BSc").scheduleArrivals(lunchTimes.generate(rand, 100)));
        sim.addCustomerClass(new CustomerClass(sim, "Undergraduate").scheduleArrivals(lunchTimes.generate(rand, 250)));

        sim.addServer(new Server(sim, new NormalDistribution(15, 2)));

        /* Run */

        sim.run();
        long endTime = System.nanoTime();
        System.out.printf("Simulation in %.2f milliseconds\n", (endTime - startTime) / 1e6);

        /* Display results */

        System.out.println("Average queuing times for...");
        for (CustomerClass cls : sim.getCustomerClasses()) {
            Statistic waits = cls.getWaitingTimes();
            System.out.printf(
                "%s:\n" +
                "    Minimum waiting time: %5.0f seconds.\n" +
                "    Average waiting time: %5.0f seconds.\n" +
                "    Maximum waiting time: %5.0f seconds.\n" +
                "    Standard deviation:   %5.0f seconds.\n",
                cls,
                waits.getMin(),
                waits.getAverage(),
                waits.getMax(),
                waits.getStandardDeviation());
        }
        for (Server server : sim.getServers()) {
            Statistic idles = server.getIdleTimes();
            System.out.printf(
                "%s:\n" +
                "    Minimum idle time:    %5.0f seconds.\n" +
                "    Average idle time:    %5.0f seconds.\n" +
                "    Maximum idle time:    %5.0f seconds.\n" +
                "    Standard deviation:   %5.0f seconds.\n",
                "Cashier",
                idles.getMin(),
                idles.getAverage(),
                idles.getMax(),
                idles.getStandardDeviation());
        }
    }
}
\$\endgroup\$
  • \$\begingroup\$ Should it be request or customer to go with server? Re naming (and Simulation.java): naming something too narrow is a show stopper, provoking Oh, this is just for … (imagine Dahl/Nygaard chose Model/Set/Process in stead of Simula/Simset/Simulation). \$\endgroup\$ – greybeard Jan 14 '16 at 11:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.