una - que es un enum en java

¿Puedes tener colecciones sin almacenar los valores en Java?

Question

Tengo una pregunta sobre las colecciones de Java, como Set o List. En general, objetos que puede usar en un bucle for-each. ¿Existe algún requisito de que los elementos de ellos realmente tengan que almacenarse en alguna parte de una estructura de datos o pueden describirse solo a partir de algún tipo de requisito y calcularse sobre la marcha cuando los necesite? Parece que esto debería poder hacerse, pero no veo ninguna de las clases de colección estándar de Java haciendo algo como esto. ¿Estoy rompiendo algún tipo de contrato aquí?

Lo que estoy pensando acerca de usar estos para es principalmente las matemáticas. Digamos, por ejemplo, quiero tener un conjunto que represente todos los números primos por debajo de 1 000 000. Puede que no sea una buena idea guardarlos en la memoria, sino tener una verificación de método si un número en particular está en la colección o no.

Tampoco soy un experto en las transmisiones de java, pero creo que deberían ser utilizables en las secuencias de java 8, ya que los objetos tienen un estado mínimo (los objetos de la colección ni siquiera existen hasta que intentes iterar sobre ellos). o verificar si existe un objeto particular en la colección).

¿Es posible tener colecciones o iteradores con prácticamente infinitos elementos, por ejemplo, "todos los números en la forma 6 * k + 1", "todos los números primos por encima de 10" o "todos los vectores abarcados por esta base"? Otra cosa en la que estoy pensando es combinar dos conjuntos como la unión de todos los primos por debajo de 1 000 000 y todos los enteros en la forma 2 ^ n-1 y enumerar los números primos de mersenne por debajo de 1 000 000. Siento que sería más fácil razonar sobre ciertos objetos matemáticos si se hizo de esta manera y los elementos no se crearon explícitamente hasta que realmente se necesitan. Puede ser que esté equivocado.

Aquí hay dos clases de maquetas que escribí para intentar ilustrar lo que quiero hacer. No actúan exactamente como yo esperaría (ver salida) lo que me hace pensar que estoy rompiendo algún tipo de contrato aquí con la interfaz iterable o implementándola mal. Siéntase libre de señalar lo que estoy haciendo mal aquí si lo ve o si este tipo de código incluso está permitido en el marco de colecciones.

import java.util.AbstractSet;
import java.util.Iterator;

public class PrimesBelow extends AbstractSet<Integer>{

    int max;
    int size;

    public PrimesBelow(int max) {
        this.max = max;
    }

    @Override
    public Iterator<Integer> iterator() {
        return new SetIterator<Integer>(this);
    }

    @Override
    public int size() {
        if(this.size == -1){
            System.out.println("Calculating size");
            size = calculateSize();
        }else{
            System.out.println("Accessing calculated size");
        }
        return size;
    }

    private int calculateSize() {
        int c = 0;
        for(Integer p: this)
            c++;
        return c;
    }

    public static void main(String[] args){
        PrimesBelow primesBelow10 = new PrimesBelow(10);
        for(int i: primesBelow10)
            System.out.println(i);
        System.out.println(primesBelow10);
    }
}

.

import java.util.Iterator;
import java.util.NoSuchElementException;

public class SetIterator<T> implements Iterator<Integer> {
    int max;
    int current;
    public SetIterator(PrimesBelow pb) {
        this.max= pb.max;
        current = 1;
    }

    @Override
    public boolean hasNext() {
        if(current < max) return true;
        else return false;
    }

    @Override
    public Integer next() {
        while(hasNext()){
            current++;
            if(isPrime(current)){
                System.out.println("returning "+current);
                return current;
            }
        }
        throw new NoSuchElementException();
    }

    private boolean isPrime(int a) {
        if(a<2) return false;
        for(int i = 2; i < a; i++) if((a%i)==0) return false;
        return true;
    }
}

Main function gives the output
returning 2
2
returning 3
3
returning 5
5
returning 7
7
Exception in thread "main" java.util.NoSuchElementException
    at SetIterator.next(SetIterator.java:27)
    at SetIterator.next(SetIterator.java:1)
    at PrimesBelow.main(PrimesBelow.java:38)

edit: detectó un error en el método next (). Se corrigió y cambió la salida a la nueva.

Answer 1

Bueno, como puede ver con su ejemplo (ahora fijo), puede hacerlo fácilmente con Iterables / Iterators . En lugar de tener una colección de respaldo, el ejemplo hubiera sido más agradable con solo un Iterable que toma el número máximo para el que desea calcular los números primos. Solo necesita asegurarse de que maneja el método hasNext() correctamente para que no tenga que lanzar una excepción innecesariamente desde next() .

Las secuencias de Java 8 se pueden usar más fácilmente para realizar este tipo de cosas hoy en día, pero no hay ninguna razón por la que no pueda tener una "colección virtual" que sea simplemente un Iterable . Si comienzas a implementar Collection se vuelve más difícil, pero incluso así no sería completamente imposible, dependiendo de los casos de uso: por ejemplo, podrías implementar contains() que verifica los primos, pero tendrías que calcularlo y sería lento para grandes números.

Un ejemplo (algo intrincado) de un conjunto semiinfinito de números impares que es inmutable y no almacena valores.

public class OddSet implements Set<Integer> {
    public boolean contains(Integer o) {
        return o % 2 == 1;
    }
    public int size() {
        return Integer.MAX_VALUE;
    }
    public boolean add(Integer i) {
        throw new OperationNotSupportedException();
    }

    public boolean equals(Object o) {
        return o instanceof OddSet;
    }
    // etc. etc.
}

Answer 2

Como dijo DwB, esto no es posible con la API de colecciones de Java, ya que cada elemento debe almacenarse en la memoria. Sin embargo, hay una alternativa: ¡esta es precisamente la razón por la cual se implementó la API Stream de Java!

Stream permiten iterar a través de una cantidad infinita de objetos que no están almacenados en la memoria a menos que los recopile explícitamente en una Collection .

De la documentación de IntStream#iterate :

Devuelve un IntStream infinito ordenado secuencialmente producido por la aplicación iterativa de una función f a un elemento inicial semilla, produciendo un flujo que consiste en semilla, f (semilla), f (f (semilla)), etc.

El primer elemento (posición 0) en IntStream será la semilla proporcionada. Para n> 0, el elemento en la posición n, será el resultado de aplicar la función f al elemento en la posición n - 1.

Aquí hay algunos ejemplos que usted propuso en su pregunta:

public class Test {

    public static void main(String[] args) {
        IntStream.iterate(1, k -> 6 * k + 1);
        IntStream.iterate(10, i -> i + 1).filter(Test::isPrime);
        IntStream.iterate(1, n -> 2 * n - 1).filter(i -> i < 1_000_000);
    }

    private boolean isPrime(int a) {
        if (a < 2) {
            return false;
        }

        for(int i = 2; i < a; i++) {
            if ((a % i) == 0) {
                return false;
            }

            return true;
        }
    }
}