Java 8 - How to build up a string from initial string with only one traversal

Question

I have an url like: String url = "https://.../foo/a/555/data1";

Goal: Transform the url to the string: a555data1

I want to build this result traversing the string only once. I decided for the following process:

1. I want to "stream" the string starting from the back.
2. If it is not a backslash insert/append at the front of a deque.
3. If it is the third backslash end

I have successfully written a horrible solution below, can it be made pretty using streams?

Deque<String> lifo = new ArrayDeque<>();

int count = 0;
for (int i = testUrl.length() - 1; count < 3 ; --i) {
    if (testUrl.codePointAt(i) == ((int) '/') ) {
        ++count;
        continue;
    }

    result.addFirst(testUrl.substring(i,i+1));

}

String foo = result.stream().collect(Collectors.joining());
assertThat(foo).isEqualTo("a606KAM1");

Answer 1

An alternative solution without loops and streams:

String[] split = url.split("/");
int n = split.length;
return split[n - 3] + split[n - 2] + split[n - 1];

Answer 2

Another way would be a regex:

String result = url.replaceAll(".+/(.+)/(.+)/(.+)", "$1$2$3");

Answer 3

If you want to do it really fast, you have to reduce the amount of data copying happening with every string construction.

int ix1 = url.lastIndexOf('/'), ix2 = url.lastIndexOf('/', ix1-1),
    ix3 = url.lastIndexOf('/', ix2-1);
String result = new StringBuilder(url.length() - ix3 - 3)
    .append(url, ix3+1, ix2)
    .append(url, ix2+1, ix1)
    .append(url, ix1+1, url.length())
    .toString();

Even when you expand it to support a configurable number of parts,

int chunks = 3;
int[] ix = new int[chunks];
int index = url.length();
for(int a = ix.length-1; a >= 0; a--) index = url.lastIndexOf('/', (ix[a] = index)-1);
StringBuilder sb = new StringBuilder(url.length() - index - chunks);
for(int next: ix) sb.append(url, index+1, index = next);
String result = sb.toString();

it’s likely faster than all alternatives.

Answer 4

You may do it like so,

final String[] splitStrArr = url.split("/");
String result = Arrays.stream(splitStrArr).skip(splitStrArr.length - 3)
                    .collect(Collectors.joining(""));

Answer 5

Initially my thought was that streams should not be used here due to supposed performance overhead, so I created a little performance test for solutions proposed in another answers:

import static java.util.Arrays.stream;

import java.util.concurrent.TimeUnit;
import java.util.stream.Collectors;

import org.openjdk.jmh.annotations.Benchmark;
import org.openjdk.jmh.annotations.BenchmarkMode;
import org.openjdk.jmh.annotations.Fork;
import org.openjdk.jmh.annotations.Mode;
import org.openjdk.jmh.annotations.OutputTimeUnit;
import org.openjdk.jmh.annotations.Scope;
import org.openjdk.jmh.annotations.State;

@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
@Fork(value = 1)
public class CJMH {

    @State(Scope.Thread)
    public static class CState {
        public String url = "https://.../foo/a/555/data1";
    }

    @Benchmark
    public String fastest(CState state) {
        String url = state.url;
        int chunks = 3;
        int[] ix = new int[chunks];
        int index = url.length();
        for(int a = ix.length-1; a >= 0; a--) index = url.lastIndexOf('/', (ix[a] = index)-1);
        StringBuilder sb = new StringBuilder(url.length() - index - chunks);
        for(int next: ix) sb.append(url, index+1, index = next);
        return sb.toString();
    }

    @Benchmark
    public String splitAndStreams(CState state) {
        final String[] splitStrArr = state.url.split("/");
        String result = stream(splitStrArr).
                skip(splitStrArr.length - 3).
                collect(Collectors.joining(""));

        return result;
    };

    @Benchmark
    public String splitAndIterate(CState state) {
        final String[] splitStrArr = state.url.split("/");

        String result = "";
        for (int k=splitStrArr.length - 3; k<splitStrArr.length; k++) {
            result += splitStrArr[k];
        }

        return result;
    };

    @Benchmark
    public String splitAndSum(CState state) {
        String[] split = state.url.split("/");
        int n = split.length;
        return split[n - 3] + split[n - 2] + split[n - 1];
    };

    @Benchmark
    public String regexp(CState state) {
        return state.url.replaceAll(".+/(.+)/(.+)/(.+)", "$1$2$3");
    };
}

And the output was:

Benchmark             Mode  Cnt    Score    Error  Units
CJMH.fastest          avgt    5   46.731 ±  0.445  ns/op
CJMH.regexp           avgt    5  937.797 ± 11.928  ns/op
CJMH.splitAndIterate  avgt    5  194.626 ±  1.880  ns/op
CJMH.splitAndStreams  avgt    5  275.640 ±  1.887  ns/op
CJMH.splitAndSum      avgt    5  180.257 ±  2.986  ns/op

So surprisingly streams are in no way much slower than iterating over the array. The fastest one is a no-copy algorithm provided by @Holger in this answer. And do not use regexps if you could avoid it!

Answer 6

I'd probably simplify your code a bit to:

StringBuilder sb = new StringBuilder();

    char c;
    for (int i = testUrl.length() - 1, count = 0; count < 3 ; --i) {
        if ((c = testUrl.charAt( i )) ==  '/') {
            ++count;
            continue;
        }
        sb.append( c );
    }
    String foo = sb.reverse().toString();

In my opinion there is no real point in using stream here - the url isn't long enough to justify effor spent setting up stream. Also we can use StringBuilder - which will be used during joining anyways.