Jan Vladimir Mostert Jan Vladimir Mostert - 4 months ago 8
Java Question

Find first matching string in two lists in less than O(n^2) time using a Java8 one-liner

Simple question, I have two arrays / lists, I'm looking for an efficient one-liner in Java8 to match the first argument against a long list of possible arguments.

Arguments are from

public static void main(String... args)
and the other one is from a list of predefined strings which I'll call secondArray,
["a", "b", "cc", "de", ...]
. I want to match the two incoming arrays against each other and find the first matching
arg
ument against a
secondArray
list.

Example:
args = Arrays.asList("r", "b", "c", "d", ...)


secondList = Arrays.asList("q", "z", "x", "c", "d", ...)


The first matching argument would be
"c"


The Java7 (inefficient) way of doing this would have been:

String profile = "default";
for (String arg : args){
if (secondArray.contains(arg)){
profile = arg;
break;
}
}

doSomethingWith(profile);


In Java8, this is what I've done so far, was wondering if there's a better way to do it (more efficient, faster, etc - let's assume both args and secondArray can potentially contain up to 100k entries):

String profile = Arrays.stream(args)
.filter(secondArray::contains)
.findFirst()
.orElse("default");

doSomethingWith(profile);


My assumption is that the filter doing
secondArray::contains
will mean O(n^2) complexity, since
secondArray.contains(arg)
will be called for each of the arguments. Anything closer to O(n) while still maintaining a single line of Java8 is what I'm after.

Answer

The trick to make it a one liner would be to create a set in filter cause

String profile = Arrays.stream(args)
            .filter(new HashSet(secondList)::contains)
            .findFirst()
            .orElse("default");

Such set is going to be created only once. The same instance of set will be used for each item in args.

So this code is O(n) to create a set and then O(n) to finding first arg.


Just keep in mind that expanded lambda like

.filter(arg -> new HashSet(secondList).contains(arg))

will create a set for each argument and will blowup complexity to O(n^2).