ComparativeTest.java

package perf;

import java.lang.reflect.Constructor;
import java.lang.reflect.InvocationTargetException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
import java.util.Random;
import java.util.TreeSet;
import java.util.stream.Collectors;
import java.util.stream.Stream;

import net.tuis.ubench.UBench;

public class ComparativeTest {

	public interface NLongest {

		void evaluate(String line);

		List<String> result();

		void reset();
	}

	public static class SimonSays implements NLongest {
		private final TreeSet<String> treeSet;
		private final int n;
		private int shortestLongestLine;
		private final List<String> result;

		public SimonSays(Integer aN) {
			n = aN.intValue();
			treeSet = new TreeSet<>(Comparator.comparing(String::length).reversed());
			result = new ArrayList<>(n);
		}

		@Override
		public void evaluate(String line) {
			if (treeSet.size() >= n) {
				if (line.length() > shortestLongestLine) {
					treeSet.add(line);
					if (treeSet.size() > n) {
						treeSet.pollLast();
					}
					shortestLongestLine = treeSet.last().length();
				}
			} else {
				treeSet.add(line);
				if (treeSet.size() == n) {
					shortestLongestLine = treeSet.last().length();
				}
			}
		}

		@Override
		public List<String> result() {
			result.clear();
			result.addAll(treeSet);
			return result;
		}

		@Override
		public void reset() {
			treeSet.clear();
		}
	}

	public static class RolfLSays implements NLongest {
		private final int n;
		private final List<String> longestLines = new LinkedList<>();
		private final List<String> result = new LinkedList<>();
		private int shortestLongLine = -1;
		private final static Comparator<String> CMP = Comparator.comparingInt(String::length);

		public RolfLSays(Integer aN) {
			n = aN.intValue();
		}

		@Override
		public void evaluate(String line) {
			if (shortestLongLine > 0 && line.length() < shortestLongLine)
				return;

			ListIterator<String> it;
			for (it = longestLines.listIterator(); it.hasNext();) {
				if (CMP.compare(it.next(), line) >= 0) {
					it.previous();
					break;
				}
			}
			it.add(line);
			if (longestLines.size() > n) {
				longestLines.remove(0);
				shortestLongLine = longestLines.get(0).length();
			}
		}

		@Override
		public List<String> result() {
			result.clear();
			while (!longestLines.isEmpty()) {
				// Reverse linked list
				result.add(0, longestLines.remove(0));
			}
			return result;
		}

		@Override
		public void reset() {
			shortestLongLine = -1;
			longestLines.clear();
		}
	}

	public static class Original implements NLongest {
		private final int n;
		private final List<String> longestLines;
		private int shortestLongLine;

		public Original(Integer aN) {
			n = aN.intValue();
			longestLines = new ArrayList<>(aN + 1);
		}

		@Override
		public void evaluate(String line) {
			if (longestLines.size() < n) {
				insertSorted(line);
				if (longestLines.size() == n) {
					shortestLongLine = longestLines.get(longestLines.size() - 1).length();
				}
			} else {
				if (line.length() > shortestLongLine) {
					insertSorted(line);
					longestLines.remove(longestLines.size() - 1);
					shortestLongLine = longestLines.get(longestLines.size() - 1).length();
				}
			}
		}

		@Override
		public List<String> result() {
			return longestLines;
		}

		private void insertSorted(String aString) {
			int max = longestLines.size();
			int min = 0;
			int pivot = min + (max - min) / 2;
			final int argLen = aString.length();

			// Binary search for insertion point.
			while (min < max) {
				int c = longestLines.get(pivot).length() - argLen;
				if (c <= 0) {
					max = pivot;
				} else {
					min = pivot + 1;
				}
				pivot = min + (max - min) / 2;
			}
			longestLines.add(min, aString);
		}

		@Override
		public void reset() {
			longestLines.clear();
		}
	}

	public static char nextSymbol(char aVal) {
		char ans = (char) (aVal + 1);
		if (ans > 'Z')
			ans = 'A';
		return ans;
	}

	public static void main(String[] args) throws Exception {
		final UBench bench = new UBench("N Longest Lines");
		final Random rnd = new Random(0);
		final int maxStrings = 1001;

		final List<Class<? extends NLongest>> contenders = createTestAlgorithms();
		final List<String> sortedInput = createTestStrings(maxStrings);

		for (int strings = 100; strings < maxStrings; strings *= 10) {
			List<String> rawInput = sortedInput.stream().limit(strings)
					.collect(Collectors.toCollection(ArrayList::new));

			runForAllN("Increasing", bench, contenders, strings,
					rawInput.stream().sorted(Comparator.comparingInt(String::length)));
			runForAllN("Decreasing", bench, contenders, strings,
					rawInput.stream().sorted(Comparator.comparingInt(String::length).reversed()));

			Collections.shuffle(rawInput, rnd);
			runForAllN("Shuffled", bench, contenders, strings, rawInput.stream());
		}

		bench.press(100).report("Comparison of N-Longest Lines algorithms");
	}

	private static void runForAllN(final String aDataset, final UBench aBench,
			final List<Class<? extends NLongest>> aContenders, int aStrings, Stream<String> aInput)
					throws NoSuchMethodException, InstantiationException, IllegalAccessException,
					InvocationTargetException {
		List<String> preparedInput = aInput.collect(Collectors.toCollection(ArrayList::new));
		for (int n = 2; n < aStrings; n += aStrings / 4) {
			List<String> expected = preparedInput.stream().sorted(Comparator.comparingInt(String::length).reversed())
					.limit(n).collect(Collectors.toCollection(ArrayList::new));
			final int N = n;
			for (Class<? extends NLongest> contender : aContenders) {
				Constructor<? extends NLongest> ctor = contender.getConstructor(Integer.class);
				NLongest cut = ctor.newInstance(N);
				aBench.addTask(aDataset + " Strings=" + aStrings + " N=" + n + " Algo:" + contender.getSimpleName(),
						() -> {
							cut.reset();
							preparedInput.forEach(line -> cut.evaluate(line));
							return cut.result();
						} , (ans) -> {
							return ans.equals(expected);
						});
			}
		}
	}

	private static List<Class<? extends NLongest>> createTestAlgorithms() {
		final List<Class<? extends NLongest>> contenders = new ArrayList<>();
		contenders.add(Original.class);
		contenders.add(SimonSays.class);
		contenders.add(RolfLSays.class);
		return contenders;
	}

	private static List<String> createTestStrings(final int maxStrings) {
		final List<String> sortedInput = new ArrayList<>(maxStrings);
		String previous = "A";
		sortedInput.add(previous);
		while (sortedInput.size() < maxStrings) {
			String value = previous + nextSymbol(previous.charAt(previous.length() - 1));
			sortedInput.add(value);
			previous = value;
		}
		return sortedInput;
	}
}