Статьи

Бесконечные множества в Java 9

Декабрь 10, 2018

Множество

Set — это набор элементов, в котором любой данный элемент в Set появляется только один раз.

Более формально, множество не содержит пары элементов e1 и e2 , для которых e1.equals(e2) .

Мы можем легко создать Set в Java 9 следующим образом:

1
2
final Set<Integer> s = Set.of(1, 2, 3);
System.out.println(s);

Это может привести к следующему выводу:

1
[2, 3, 1]

Произведенное выше Set является неизменным, то есть оно не может изменяться, и оно также конечно, потому что в Set есть различное количество элементов, а именно три. Порядок, в котором элементы возвращаются через его методы чтения (такие как stream() , iterator() и forEach() ), не указан.

Бесконечный набор

Бесконечный набор содержит неограниченное количество элементов. Одним примером бесконечного набора является набор всех целых чисел […, -1, 0, 1, 2,…], где целое число не является классом Java Integer а является целым числом в соответствии с математическим определением целого числа, посредством которого существует всегда большее целое число n + 1 для любого заданного целого числа n.

Существует множество бесконечных множеств, таких как множество всех простых чисел, множество четных целых чисел, множество чисел Фибоначчи и т. Д.

По понятным причинам мы не можем предварительно вычислить и сохранить все элементы бесконечного Set Java. Если мы попробуем, у нас в конечном итоге не хватит памяти

Фундаментальный вопрос, который мы должны задать себе: есть ли на самом деле бесконечные множества для типов Java, которые у нас есть? Если у нас есть Set<Byte> то в Set<Byte> не более 256 элементов, и это далеко не бесконечно, то же самое относится и к Short и даже к Integer . В конце концов, существует всего около четырех миллиардов различных объектов Integer и если бы мы использовали битовую карту для представления членства, мы могли бы поместить Set<Integer> всего в 0,5 ГБ. Хоть и большой, но не бесконечный.

Но если мы говорим об элементах Long или String , мы приближаемся, по крайней мере, к практически бесконечным множествам. Для хранения растрового изображения всех длинных потребуется количество ПБ внутренней памяти. Истинный бесконечный Set — это Set String со всеми возможными комбинациями символов [az] любой длины.

Прежде чем мы продолжим, я хотел бы отметить, что код в этом посте также доступен на GitHub, как описано в самом конце поста.

ImmutableStreamSet

Чтобы отойти от парадигмы, в которой мы храним элементы Set , мы могли бы создать ImmutableStreamSet который определяет элементы Set только через его метод stream() . ImmutableStreamSet может быть определен как FunctionalInterface следующим образом:

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
@FunctionalInterface
public interface ImmutableStreamSet<E> extends Set<E> {
 
    // This is the only method we need to implements
    @Override
    public Stream<E> stream();
 
    @Override
    default int size() {
        return (int) stream().limit(Integer.MAX_VALUE).count();
    }
 
    @Override
    default boolean contains(Object o) {
        return stream().anyMatch(e -> Objects.equals(e, o));
    }
 
    @Override
    default boolean containsAll(Collection<?> c) {
        return (this == c) ? true : c.stream().allMatch(this::contains);
    }
 
    @Override
    default boolean isEmpty() {
        return !stream().findAny().isPresent();
    }
 
    @Override
    default <T> T[] toArray(T[] a) {
        return stream().collect(toList()).toArray(a);
    }
 
    @Override
    default Object[] toArray() {
        return stream().toArray();
    }
 
    @Override
    default Spliterator<E> spliterator() {
        return stream().spliterator();
    }
 
    @Override
    default Iterator<E> iterator() {
        return stream().iterator();
    }
 
    @Override
    default Stream<E> parallelStream() {
        return stream().parallel();
    }
 
    @Override
    default void forEach(Consumer<? super E> action) {
        stream().forEach(action);
    }
 
    // We are immutable
    @Override
    default boolean removeIf(Predicate<? super E> filter) {
        throw new UnsupportedOperationException();
    }
 
    @Override
    default void clear() {
        throw new UnsupportedOperationException();
    }
 
    @Override
    default boolean removeAll(Collection<?> c) {
        throw new UnsupportedOperationException();
    }
 
    @Override
    default boolean retainAll(Collection<?> c) {
        throw new UnsupportedOperationException();
    }
 
    @Override
    default boolean addAll(Collection<? extends E> c) {
        throw new UnsupportedOperationException();
    }
 
    @Override
    default boolean remove(Object o) {
        throw new UnsupportedOperationException();
    }
 
    @Override
    default boolean add(E e) {
        throw new UnsupportedOperationException();
    }
 
    static <E> ImmutableStreamSet<E> of(Supplier<Stream<E>> supplier) {
    // Check out GitHub to see how this Impl class is implemented
        return new ImmutableStreamSetImpl<>(supplier);
    }
 
}

Круто, теперь мы можем создавать бесконечные множества, просто предоставив поставщика потоков, например так:

1
2
ImmutableStreamSet<Long> setOfAllLong
            = LongStream.rangeClosed(Long.MIN_VALUE, Long.MAX_VALUE)::boxed;

Это создаст Set всех Long значений (например, с 2 ^ 64 элементами). При предоставлении поставщика потока обязательно убедитесь, что он придерживается свойства Set уникальности элемента. Рассмотрим следующий незаконный набор:

1
2
final ImmutableStreamSet<Long> illegalSet =
            () -> Stream.of(1l, 2l, 1l);

Ясно, что 11 встречается два раза в наборе, что заставляет этот объект нарушать требования набора.

Как мы увидим, было бы лучше создать конкретные классы бесконечных множеств, которые мы рассматриваем. Одна конкретная проблема, связанная с реализацией по умолчанию выше, заключается в том, что метод contains() может быть очень медленным. Прочитайте следующие главы и узнайте, почему и как это решить.

PositiveLongSet

Давайте предположим, что мы хотим создать Set со всеми положительными длинными значениями и хотим, чтобы мы могли эффективно использовать Set с другими наборами и объектами. Вот как мы можем это сделать:

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public final class PositiveLongSet implements ImmutableStreamSet<Long> {
 
    public static final PositiveLongSet INSTANCE = new PositiveLongSet();
 
    private PositiveLongSet() {
    }
 
    @Override
    public Stream<Long> stream() {
        return LongStream.rangeClosed(1, Long.MAX_VALUE).boxed();
    }
 
    @Override
    public int size() {
        return Integer.MAX_VALUE;
    }
 
    @Override
    public boolean contains(Object o) {
        return SetUtil.contains(this, Long.class, other -> other > 0, o);
    }
 
    @Override
    public boolean isEmpty() {
        return false;
    }
 
    @Override
    public String toString() {
        return SetUtil.toString(this);
    }
 
}

Обратите внимание, как мы соблюдаем формальное требование в методе size() где мы возвращаем Integer.MAX_VALUE хотя Set намного больше. Если бы Set был определен сегодня, вполне вероятно, что size() вернул бы long вместо int . Но в начале 90-х годов объем внутренней оперативной памяти обычно составлял менее 1 ГБ. Мы используем два служебных метода в классе:

SetUtil.toString() принимает Set , перебирает первые восемь элементов и возвращает String представление этих элементов.

Метод SetUtil.contains() принимает Set , класс типа Element (здесь Long.class ) и Predicate который вызывается, если объект, который мы сравниваем, имеет заданный класс типа Element (если объект, с которым мы сравниваем, является null или другого типа, тогда тривиально Set не содержит объект).

Вот как выглядит SetUtil :

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
final class SetUtil {
 
    private static final int TO_STRING_MAX_ELEMENTS = 8;
 
    static <E> String toString(Set<E> set) {
        final List<String> first = set.stream()
            .limit(TO_STRING_MAX_ELEMENTS + 1)
            .map(Object::toString)
            .collect(toList());
 
        final String endMarker = first.size() > TO_STRING_MAX_ELEMENTS ? ", ...]" : "]";
 
        return first.stream()
            .limit(TO_STRING_MAX_ELEMENTS)
            .collect(
                joining(", ", "[", endMarker)
            );
    }
 
    static <E> boolean contains(
        final Set<E> set,
        final Class<E> clazz,
        final Predicate<E> predicate,
        final Object o
    ) {
        if (o == null) {
            return false;
        }
        if (!(clazz.isAssignableFrom(o.getClass()))) {
            return false;
        }
        final E other = clazz.cast(o);
        return predicate.test(other);
    }
 
}

Вооружившись классами SetUtil и SetUtil мы теперь можем легко создавать другие бесконечные наборы, такие как PostitiveEvenLongSet (не показан ниже, попробуйте написать его самостоятельно), PrimeLongSet (содержащий все простые числа, которые могут быть представлены Long ) и даже FibonacciLongSet (содержащий все числа FibonacciLongSet что может быть представлено Long ). Вот как могут выглядеть эти классы:

PrimeLongSet

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public final class PrimeLongSet implements ImmutableStreamSet<Long> {
 
    public static final PrimeLongSet INSTANCE = new PrimeLongSet();
 
    private PrimeLongSet() {
    }
 
    private static final LongPredicate IS_PRIME =
        x -> LongStream.rangeClosed(2, (long) Math.sqrt(x)).allMatch(n -> x % n != 0);
 
    @Override
    public Stream<Long> stream() {
        return LongStream.rangeClosed(2, Long.MAX_VALUE)
            .filter(IS_PRIME)
            .boxed();
    }
 
    @Override
    public int size() {
        return Integer.MAX_VALUE;
    }
 
    @Override
    public boolean contains(Object o) {
        return SetUtil.contains(this, Long.class, IS_PRIME::test, o);
    }
 
    @Override
    public boolean isEmpty() {
        return false;
    }
 
    @Override
    public String toString() {
        return SetUtil.toString(this);
    }
 
}

FibonacciLongSet

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
public final class FibonacciLongSet implements ImmutableStreamSet<Long> {
 
    public static final FibonacciLongSet INSTANCE = new FibonacciLongSet();
 
    private FibonacciLongSet() {
    }
 
    @Override
    public Stream<Long> stream() {
        return Stream.concat(
            Stream.of(0l),
            Stream.iterate(new Fibonacci(0, 1), Fibonacci::next)
                .mapToLong(Fibonacci::getAsLong)
                .takeWhile(fib -> fib > 0)
                .boxed()
        );
    }
 
    @Override
    public int size() {
        return 92;
    }
 
    @Override
    public boolean contains(Object o) {
        return SetUtil.contains(
            this,
            Long.class,
            other -> stream().anyMatch(fib -> Objects.equals(fib, other)),
            o
        );
    }
 
    @Override
    public boolean isEmpty() {
        return false;
    }
 
    @Override
    public String toString() {
        return SetUtil.toString(this);
    }
 
    private static class Fibonacci {
 
        final long beforeLast;
        final long last;
 
        public Fibonacci(long beforeLast, long last) {
            this.beforeLast = beforeLast;
            this.last = last;
        }
 
        public Fibonacci next() {
            return new Fibonacci(last, last + beforeLast);
        }
 
        public long getAsLong() {
            return beforeLast + last;
        }
 
    }
 
}

Обратите внимание, как мы используем Stream::takeWhile чтобы разорвать поток, когда long оборачивается в отрицательное значение. Возможно, мы «обманываем», когда выполняем предварительные вычисления и предоставляем размер 92, но в противном случае size() был бы немного медленнее.

Сшить все это

Предоставляя интерфейс со статическими поставщиками для экземпляров этих классов, мы можем инкапсулировать наши предопределенные наборы и убедиться, что в JVM есть только один их экземпляр:

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
public interface Sets {
 
    static Set<Long> positiveLongSet() {
        return PositiveLongSet.INSTANCE;
    }
 
    static Set<Long> positiveEvenLongSet() {
        return PositiveEvenLongSet.INSTANCE;
    }
 
    static Set<Long> primeLongSet() {
        return PrimeLongSet.INSTANCE;
    }
 
    static Set<Long> fibonacciLongSet() {
        return FibonacciLongSet.INSTANCE;
    }
 
}

Мы также можем инкапсулировать наш код в модуль Java 9, чтобы убедиться, что видны только классы Sets и ImmutableStreamSet , выставив их в самом верхнем пакете проектов и поместив все остальные классы в пакет с именем «internal» (который не выставляется ).

Вот module-info.java может выглядеть наш module-info.java при условии, что два открытых класса находятся в com.speedment.infinite_sets а классы реализации — в пакете, подобном com.speedment.infinite_sets.internal :

module-info.java

1
2
3
module com.speedment.infinite_sets {
    exports com.speedment.infinite_sets;
}

Пробовать

Теперь мы можем создать еще один модуль, который использует наши бесконечные множества, сначала объявив об использовании нашего существующего модуля следующим образом:

module-info.java

1
2
3
module Infinite_sets_app {
    requires com.speedment.infinite_sets;
}

И тогда у нас есть доступ к открытым частям модуля. Вот один из способов опробовать бесконечные множества:

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
import static com.speedment.infinite_sets.Sets.*;
public class Main {
 
    public static void main(String[] args) {
 
        Stream.of(
            Set.of(1, 2, 3),
            positiveLongSet(),
            positiveEvenLongSet(),
            primeLongSet(),
            fibonacciLongSet()
        ).forEachOrdered(System.out::println);
 
        // This actually completes fast due to identity equality
        positiveLongSet().containsAll(positiveLongSet());
 
    }
 
}

Это может привести к следующему выводу:

1
2
3
4
5
[3, 2, 1]
[1, 2, 3, 4, 5, 6, 7, 8, ...]
[2, 4, 6, 8, 10, 12, 14, 16, ...]
[2, 3, 5, 7, 11, 13, 17, 19, ...]
[0, 1, 2, 3, 5, 8, 13, 21, ...]

Заниматься на GitHub

Исходный код в этом посте доступен на GitHub здесь .
Игра, сет и матч …

Смотрите оригинальную статью здесь: Бесконечные множества в Java 9

Мнения, высказанные участниками Java Code Geeks, являются их собственными.

49
Share: