JMH benchmark for http://stackoverflow.com/questions/29659883/longest-substring-time-limit-exceeded-java

benchmark.log

# JMH 1.9 (released 3 days ago)
# VM invoker: /usr/lib/jvm/java-7-openjdk-i386/jre/bin/java
# VM options: <none>
# Warmup: 10 iterations, 5 s each
# Measurement: 10 iterations, 5 s each
# Timeout: 10 min per iteration
# Threads: 1 thread, will synchronize iterations
# Benchmark mode: Throughput, ops/time

# author of benchmarked algorithms can be identified by the trailing number
# 1 - http://stackoverflow.com/users/3973077/pbabcdefp
# 2 - http://stackoverflow.com/users/2071828/boris-the-spider
# 3 - http://stackoverflow.com/users/2333222/suboptimal

# Run complete. Total time: 00:25:04

Benchmark                                     Mode  Cnt    Score    Error   Units
LongestSubstring.testFlipped1                thrpt   10  260,926 ± 18,350  ops/ms
LongestSubstring.testFlipped2                thrpt   10  137,811 ± 10,360  ops/ms
LongestSubstring.testFlipped3                thrpt   10  470,187 ±  1,114  ops/ms
LongestSubstring.testOrderedFirstHalf1       thrpt   10  251,782 ± 13,335  ops/ms
LongestSubstring.testOrderedFirstHalf2       thrpt   10  127,163 ±  5,481  ops/ms
LongestSubstring.testOrderedFirstHalf3       thrpt   10  460,318 ±  2,006  ops/ms
LongestSubstring.testOrderedRepeatLastChar1  thrpt   10  274,321 ± 18,891  ops/ms
LongestSubstring.testOrderedRepeatLastChar2  thrpt   10  129,829 ± 10,087  ops/ms
LongestSubstring.testOrderedRepeatLastChar3  thrpt   10  493,207 ±  0,548  ops/ms
LongestSubstring.testOrderedSecondHalf1      thrpt   10  255,474 ± 15,757  ops/ms
LongestSubstring.testOrderedSecondHalf2      thrpt   10  121,800 ±  7,861  ops/ms
LongestSubstring.testOrderedSecondHalf3      thrpt   10  467,896 ±  0,589  ops/ms
LongestSubstring.testRandom1                 thrpt   10  280,299 ± 22,880  ops/ms
LongestSubstring.testRandom2                 thrpt   10  149,972 ±  8,848  ops/ms
LongestSubstring.testRandom3                 thrpt   10  471,278 ±  6,509  ops/ms

LongestSubstring.java

package sub.optimal.benchmark;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Random;
import java.util.Set;
import java.util.concurrent.TimeUnit;
import org.openjdk.jmh.annotations.Benchmark;
import org.openjdk.jmh.annotations.Fork;
import org.openjdk.jmh.annotations.Measurement;
import org.openjdk.jmh.annotations.OutputTimeUnit;
import org.openjdk.jmh.annotations.Scope;
import org.openjdk.jmh.annotations.State;
import org.openjdk.jmh.annotations.Warmup;

@OutputTimeUnit(TimeUnit.MILLISECONDS)
@Warmup(iterations = 10, time = 5)
@Measurement(iterations = 10, time = 5)
@Fork(value = 1)
public class LongestSubstring {

    private static final int STRING_LENGTH = 200;

    /**
     * Generate a string of random choosen characters.
     */
    @State(Scope.Benchmark)
    public static class RandomChars {

        String string = init();

        static String init() {
            int stringLength = STRING_LENGTH;
            StringBuilder sb = new StringBuilder(stringLength);
            Random rand = new Random(1);
            for (int i = 0; i < stringLength; i++) {
                sb.append((char) ('a' + rand.nextInt(25)));
            }
            return sb.toString();
        }
    }

    /**
     * Generate a string of following repeated pattern (all characters randomly
     * choosen).<br>
     * pattern: abcdefghijklmnopqrstuvwxyzabcdefghijklm
     */
    @State(Scope.Benchmark)
    public static class OrderedFirstHalfSubstring {

        String string = init();

        static String init() {
            int stringLength = STRING_LENGTH;
            StringBuilder sb = new StringBuilder(stringLength);
            Random rand = new Random(1);
            StringBuilder longSubstring = new StringBuilder(26);
            for (int i = 0; i < longSubstring.capacity(); i++) {
                longSubstring.append((char) ('a' + rand.nextInt(25)));
            }
            String shortSubstring = longSubstring.substring(0, 13);
            while (sb.length() < stringLength) {
                sb.append(longSubstring).append(shortSubstring);
            }
            return sb.toString();
        }
    }

    /**
     * Generate a string of following repeated pattern (all characters randomly
     * choosen).<br>
     * pattern: abcdefghijklmnopqrstuvwxyznopqrstuvwxyz
     */
    @State(Scope.Benchmark)
    public static class OrderedSecondHalfSubstring {

        String string = init();

        static String init() {
            int stringLength = STRING_LENGTH;
            StringBuilder sb = new StringBuilder(stringLength);
            Random rand = new Random(1);
            StringBuilder longSubstring = new StringBuilder(26);
            for (int i = 0; i < longSubstring.capacity(); i++) {
                longSubstring.append((char) ('a' + rand.nextInt(25)));
            }
            String shortSubstring = longSubstring.substring(13);
            while (sb.length() < stringLength) {
                sb.append(longSubstring).append(shortSubstring);
            }
            return sb.toString();
        }
    }

    /**
     * Generate a string of following repeated pattern (all characters randomly
     * choosen).<br>
     * pattern: abcdefghijklmnopqrstuvwxyzz
     */
    @State(Scope.Benchmark)
    public static class OrderedSubstringRepeatedLastChar {

        String string = init();

        static String init() {
            int stringLength = STRING_LENGTH;
            StringBuilder sb = new StringBuilder(stringLength);
            Random rand = new Random(1);
            StringBuilder longSubstring = new StringBuilder(26);
            for (int i = 0; i < longSubstring.capacity(); i++) {
                longSubstring.append((char) ('a' + rand.nextInt(25)));
            }
            while (sb.length() < stringLength) {
                sb.append(longSubstring).append(longSubstring.charAt(longSubstring.length() - 1));
            }
            return sb.toString();
        }
    }

    /**
     * Generate a string of following repeated pattern (all characters randomly
     * choosen).<br>
     * pattern: abcdefghijklmnopqrstuvwxyzmlkjihgfedcba
     */
    @State(Scope.Benchmark)
    public static class FlippedSubstrings {

        String string = init();

        static String init() {
            int stringLength = STRING_LENGTH;
            StringBuilder sb = new StringBuilder(stringLength);
            Random rand = new Random(1);
            StringBuilder longSubstring = new StringBuilder(26);
            for (int i = 0; i < longSubstring.capacity(); i++) {
                longSubstring.append((char) ('a' + rand.nextInt(25)));
            }
            StringBuilder shortReverseSubstring = new StringBuilder(longSubstring.subSequence(0, 13)).reverse();
            while (sb.length() < stringLength) {
                sb.append(longSubstring).append(shortReverseSubstring);
            }
            return sb.toString();
        }
    }

    @Benchmark
    public int testRandom1(RandomChars state) {
        return subStringLength(state.string);
    }

    @Benchmark
    public int testRandom2(RandomChars state) {
        return longestNonRepeating(state.string);
    }

    @Benchmark
    public int testRandom3(RandomChars state) {
        return maxSubStringLength(state.string);
    }

    @Benchmark
    public int testOrderedFirstHalf1(OrderedFirstHalfSubstring state) {
        return subStringLength(state.string);
    }

    @Benchmark
    public int testOrderedFirstHalf2(OrderedFirstHalfSubstring state) {
        return longestNonRepeating(state.string);
    }

    @Benchmark
    public int testOrderedFirstHalf3(OrderedFirstHalfSubstring state) {
        return maxSubStringLength(state.string);
    }

    @Benchmark
    public int testOrderedSecondHalf1(OrderedSecondHalfSubstring state) {
        return subStringLength(state.string);
    }

    @Benchmark
    public int testOrderedSecondHalf2(OrderedSecondHalfSubstring state) {
        return longestNonRepeating(state.string);
    }

    @Benchmark
    public int testOrderedSecondHalf3(OrderedSecondHalfSubstring state) {
        return maxSubStringLength(state.string);
    }

    @Benchmark
    public int testOrderedRepeatLastChar1(OrderedSubstringRepeatedLastChar state) {
        return subStringLength(state.string);
    }

    @Benchmark
    public int testOrderedRepeatLastChar2(OrderedSubstringRepeatedLastChar state) {
        return longestNonRepeating(state.string);
    }

    @Benchmark
    public int testOrderedRepeatLastChar3(OrderedSubstringRepeatedLastChar state) {
        return maxSubStringLength(state.string);
    }

    @Benchmark
    public int testFlipped1(FlippedSubstrings state) {
        return subStringLength(state.string);
    }

    @Benchmark
    public int testFlipped2(FlippedSubstrings state) {
        return longestNonRepeating(state.string);
    }

    @Benchmark
    public int testFlipped3(FlippedSubstrings state) {
        return maxSubStringLength(state.string);
    }

    /**
     * algorithm: user http://stackoverflow.com/users/3973077/pbabcdefp
     */
    static int subStringLength(final String s) {
        final Map<Character, Integer> indices = new HashMap<>();
        int max = 0;
        int start = 0;
        final int length = s.length();
        for (int i = 0; i < length; i++) {
            Integer k = indices.put(s.charAt(i), i);
            if (k != null && k >= start) {
                max = Math.max(max, i - start);
                start = k + 1;
            }
        }
        return Math.max(max, length - start);
    }

    /**
     * algorithm: user http://stackoverflow.com/users/2071828/boris-the-spider
     */
    static int longestNonRepeating(final String s) {
        final Set<Character> unique = new HashSet<>();
        int max = 0;
        for (int i = 0; i < s.length(); ++i) {
            final char c = s.charAt(i);
            if (!unique.add(c)) {
                for (int j = i - unique.size(); j < i; ++j) {
                    if (s.charAt(j) != c) {
                        unique.remove(s.charAt(j));
                    } else {
                        break;
                    }
                }
            }
            max = Math.max(max, unique.size());
        }
        return max;
    }

    /**
     * algorithm: user http://stackoverflow.com/users/2333222/suboptimal
     */
    static int maxSubStringLength(String string) {
        if (string.isEmpty()) {
            return 0;
        }
        int maxLength = 1;
        int low = 0;
        for (int high = 1; high < string.length(); high++) {
            for (int pos = high - 1; pos >= low; pos--) {
                if (string.charAt(pos) == string.charAt(high)) {
                    low = pos + 1;
                    break;
                }
            }
            maxLength = Math.max(maxLength, high - low + 1);
            if (string.length() - low <= maxLength) {
                break;
            }
        }
        return maxLength;
    }
}