Is there a more elegant way to get random not used item from list using java 8?

Question

Function to be refactored...

<T> T notUsedRandomItem(List<T> allItems, List<T> usedItems) {
    return allItems.stream()
            .filter(item -> !usedItems.contains(item))
            .sorted((o1, o2) -> new Random().nextInt(2) - 1)
            .findFirst()
            .orElseThrow(() -> new RuntimeException("Did not find item!"));
}

Function might be used like this...

System.out.println(
            notUsedRandomItem(
                    Arrays.asList(1, 2, 3, 4), 
                    Arrays.asList(1, 2)
            )
    ); // Should print either 3 or 4

Edit: Collected suggested implementations and tested efficiency by running them against Person lists.

edit2: Added missing equals method to Person class.

import java.util.*;
import java.util.concurrent.TimeUnit;
import java.util.function.BiFunction;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

import static java.util.stream.Collectors.toList;

class Functions {

    <T> T notUsedRandomItemOriginal(List<T> allItems, List<T> usedItems) {
        return allItems.stream()
                .filter(item -> !usedItems.contains(item))
                .sorted((o1, o2) -> new Random().nextInt(2) - 1)
                .findFirst()
                .orElseThrow(() -> new RuntimeException("Did not find item!"));
    }

    <T> T notUsedRandomItemByAominè(List<T> allItems, List<T> usedItems) {
        List<T> distinctItems = allItems.stream()
                .filter(item -> !usedItems.contains(item))
                .collect(toList());

        if (distinctItems.size() == 0) throw new RuntimeException("Did not find item!");

        return distinctItems.get(new Random().nextInt(distinctItems.size()));
    }

    <T> T notUsedRandomItemByEugene(List<T> allItems, List<T> usedItems) {

        // this is only needed because your input List might not support removeAll
        List<T> left = new ArrayList<>(allItems);
        List<T> right = new ArrayList<>(usedItems);

        left.removeAll(right);

        return left.get(new Random().nextInt(left.size()));
    }

    <T> T notUsedRandomItemBySchaffner(List<T> allItems, List<T> usedItems) {

        Set<T> used = new HashSet<>(usedItems);
        List<T> all = new ArrayList<>(allItems);

        Collections.shuffle(all);

        for (T item : all) if (!used.contains(item)) return item;

        throw new RuntimeException("Did not find item!");
    }
}

public class ComparingSpeedOfNotUsedRandomItemFunctions {

    public static void main(String[] plaa) {
        runFunctionsWith(100);
        runFunctionsWith(1000);
        runFunctionsWith(10000);
        runFunctionsWith(100000);
        runFunctionsWith(200000);
    }

    static void runFunctionsWith(int itemCount) {

        TestConfiguration testConfiguration = new TestConfiguration();
        Functions functions = new Functions();

        System.out.println("Function execution time with " + itemCount + " items...");

        System.out.println("Schaffner: " +
                testConfiguration.timeSpentForFindingNotUsedPeople(
                        itemCount, (allPeople, usedPeople) ->
                                functions.notUsedRandomItemBySchaffner(allPeople, usedPeople)
                ));

        System.out.println("Eugene: " +
                testConfiguration.timeSpentForFindingNotUsedPeople(
                        itemCount, (allPeople, usedPeople) ->
                                functions.notUsedRandomItemByEugene(allPeople, usedPeople)
                ));

        System.out.println("Aominè: " +
                testConfiguration.timeSpentForFindingNotUsedPeople(
                        itemCount, (allPeople, usedPeople) ->
                                functions.notUsedRandomItemByAominè(allPeople, usedPeople)
                ));

        System.out.println("Original: " +
                testConfiguration.timeSpentForFindingNotUsedPeople(
                        itemCount, (allPeople, usedPeople) ->
                                functions.notUsedRandomItemOriginal(allPeople, usedPeople)
                ));
    }

}

class TestConfiguration {

    Long timeSpentForFindingNotUsedPeople(int numberOfPeople, BiFunction<List<Person>, List<Person>, Person> function) {

        ArrayList<Person> people = new ArrayList<>();
        IntStream.range(1, numberOfPeople).forEach(i -> people.add(new Person()));
        Collections.shuffle(people);

        List<Person> halfOfPeople =
                people.stream()
                        .limit(numberOfPeople / 2)
                        .collect(Collectors.toList());

        Collections.shuffle(halfOfPeople);

        long before = System.nanoTime();
        Person foundItem = function.apply(people, halfOfPeople);
        long after = System.nanoTime();

        // Return -1 if function do not return valid answer
        if (halfOfPeople.contains(foundItem))
            return (long) -1;

        return TimeUnit.MILLISECONDS.convert(after - before, TimeUnit.NANOSECONDS);
    }

    class Person {
        public final String name = UUID.randomUUID().toString();

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;

            Person person = (Person) o;

            return name != null ? name.equals(person.name) : person.name == null;
        }

        @Override
        public int hashCode() {
            return name != null ? name.hashCode() : 0;
        }
    }
}

Results:

Function execution time with 100 items...
Schaffner: 0
Eugene: 1
Aominè: 2
Original: 5
Function execution time with 1000 items...
Schaffner: 0
Eugene: 14
Aominè: 13
Original: 5
Function execution time with 10000 items...
Schaffner: 2
Eugene: 564
Aominè: 325
Original: 348
Function execution time with 20000 items...
Schaffner: 3
Eugene: 1461
Aominè: 1418
Original: 1433
Function execution time with 30000 items...
Schaffner: 3
Eugene: 4616
Aominè: 2832
Original: 4567
Function execution time with 40000 items...
Schaffner: 4
Eugene: 10889
Aominè: 4903
Original: 10394

Conclusion

When list size reach 10000 items then so far only Schaffner's implementation is usable.

And because it's fairly simple to read I will pick it as the most elegant solution.

Answer 1

I can think of this, but no idea what-so-ever how it will scale compared to your existing solution:

<T> T notUsedRandomItem(List<T> allItems, List<T> usedItems) {

    // this is only needed because your input List might not support removeAll
    List<T> left = new ArrayList<>(allItems);
    List<T> right = new ArrayList<>(usedItems);

    left.removeAll(right);

    return left.get(new Random().nextInt(left.size()));

}

One thing to keep in mind is that sorted is a stateful operation, so it will sort the entire "diff", but you only retrieve one element from that. Also your Comparator is wrong, for the same two values o1 and o2 you might say they are different - this can break in mysterious ways.