recursivamente - invertir arreglo java

Cómo obtener una secuencia ordenada de una lista en orden inverso en Java 8

Question

¿Existe una forma sensata de obtener una secuencia ordenada de una lista (específicamente, pero no debería importar) que transmite elementos a la inversa de cómo están en la lista original?

Estoy buscando una solución que no implique el almacenamiento en búfer de los datos (recopilador, otra lista, matriz, etc., porque copian el contenedor que es inútil), o utiliza Collections.reverse (porque modifica la lista).

Hasta ahora, las formas más limpias que veo aquí es implementar mi propia versión de Spliterator que se ORDERED y avanza a través de la lista al revés, o implementar un Iterator que se repita en reversa, y usar Spliterators.spliteratorUnknownSize(iterator,ORDERED) en él.

Tenga en cuenta que esta pregunta es diferente del orden inverso de la secuencia de Java 8 : esa otra pregunta se refiere a cómo revertir una secuencia (lo cual es imposible en el caso general), y las respuestas ofrecen revertir la fuente de alguna manera (lo que no quiero hacer), y luego transmitir esa fuente invertida. El costo de revertir la fuente es O (N), y quiero evitarlo si es posible.

Answer 1

La biblioteca de guayaba de Google proporciona una vista inversa de una lista ( Lists#reverse(List) ). También hay un ReverseListIterator en la biblioteca de la colección de Apache Commons.

Answer 2

Si su List es una lista de acceso aleatorio, simplemente puede usar

int num=list.size()-1;
IntStream.rangeClosed(0, num).mapToObj(i->list.get(num-i))

para crear un Stream que tiene las características ORDERED | SIZED | SUBSIZED ORDERED | SIZED | SUBSIZED ORDERED | SIZED | SUBSIZED y ofrece soporte de división completo.

Para una lista de acceso no aleatorio como LinkedList , sería un desastre de rendimiento, sin embargo, ¿quién usa LinkedList todos modos?

También puede consultar primero a través de la list instanceof RandomAccess list instanceof ...

Answer 3

Tiendo a que me gusta la respuesta de @ teppic de usar una biblioteca de terceros para hacer esto. Sin embargo, es un ejercicio interesante tratar de encontrar una solución utilizando solo las API de Java 8. Delegar a un ListIterator es lo más limpio que se me ocurre, pero en realidad no es mucho más limpio que implementar su propio Iterator desde cero.

public static void main(String[] args){
    List<String> l = Arrays.asList("first", "second", "third");

    StreamSupport.stream(Spliterators.spliterator(revit(l), l.size(), 0), false)
                 .forEachOrdered(System.out::println);
}

private static final <T> Iterator<T> revit(List<T> l){
    ListIterator<T> li = l.listIterator(l.size());

    return new Iterator<T>(){
        @Override
        public boolean hasNext(){
            return li.hasPrevious();
        }

        @Override
        public T next(){
            return li.previous();
        }
    };
}

Answer 4

NOTA: Si tiene una ArrayList u otra lista que permita la recuperación de acceso aleatorio por índice ( get(i) ), entonces es preferible el enfoque de Holger . El enfoque a continuación solo es necesario si tiene una estructura de datos que permita el acceso transversal inverso pero no el acceso indexado.

Desafortunadamente, no parece haber una manera realmente simple (es decir, de una sola línea) de hacer esto. Sin embargo, obtener una secuencia invertida utilizando AbstractSpliterator no es demasiado difícil, dado que List ya tiene la capacidad de iterar a la inversa. Aquí hay un método de utilidad para hacer eso:

static <T> Stream<T> reversedStream(List<? extends T> input) {
    ListIterator<? extends T> li = input.listIterator(input.size());
    return StreamSupport.stream(
        new Spliterators.AbstractSpliterator<T>(input.size(), Spliterator.ORDERED) {
            @Override public boolean tryAdvance(Consumer<? super T> action) {
                if (li.hasPrevious()) {
                    action.accept(li.previous());
                    return true;
                } else {
                    return false;
                }
            }
        },
        false);
}

(Supongo que el Spliterator podría tener TAMAÑO, pero eso no tiene sentido porque es un spliterator insensible ).

Tal como está, esto puede permitirse un grado limitado de paralelismo, ya que AbstractSpliterator llamará a tryAdvance varias veces y tryAdvance el trabajo en dos para entregarlo a tareas de fork-join. Pero no es tan eficiente como poder dividirse.

Si la eficiencia paralela es una gran preocupación, uno podría escribir un separador que realmente pueda dividirse, donde las divisiones se atraviesan en orden inverso.