Ordre inverse du flux Java 8

StackOverflow https://stackoverflow.com//questions/24010109

  •  21-12-2019
  •  | 
  •  

Question

Question générale:Quelle est la bonne façon d’inverser un flux ?En supposant que nous ne sachions pas de quel type d'éléments se compose ce flux, quelle est la manière générique d'inverser n'importe quel flux ?

Question spécifique :

IntStream fournit une méthode de plage pour générer des entiers dans une plage spécifique IntStream.range(-range, 0), maintenant que je veux l'inverser, la plage de commutation de 0 à négatif ne fonctionnera pas, je ne peux pas non plus l'utiliser Integer::compare

List<Integer> list = Arrays.asList(1,2,3,4);
list.stream().sorted(Integer::compare).forEach(System.out::println);

avec IntStream J'obtiendrai cette erreur du compilateur

Erreur :(191, 0) ajc :La méthode sorted() dans le genre IntStream n'est pas applicable pour les arguments (Integer::compare)

Qu'est-ce que j'oublie ici?

Était-ce utile?

La solution

Pour la question spécifique de la génération d'un reverse IntStream, essayez quelque chose comme ceci :

static IntStream revRange(int from, int to) {
    return IntStream.range(from, to)
                    .map(i -> to - i + from - 1);
}

Cela évite le boxage et le tri.

Pour la question générale de savoir comment inverser un flux de tout type, je ne connais pas de méthode « appropriée ».Il y a plusieurs façons auxquelles je peux penser.Les deux finissent par stocker les éléments du flux.Je ne connais pas de moyen d'inverser un flux sans stocker les éléments.

Cette première méthode stocke les éléments dans un tableau et les lit dans un flux dans l'ordre inverse.Notez que comme nous ne connaissons pas le type d'exécution des éléments du flux, nous ne pouvons pas taper le tableau correctement, ce qui nécessite une conversion non vérifiée.

@SuppressWarnings("unchecked")
static <T> Stream<T> reverse(Stream<T> input) {
    Object[] temp = input.toArray();
    return (Stream<T>) IntStream.range(0, temp.length)
                                .mapToObj(i -> temp[temp.length - i - 1]);
}

Une autre technique utilise des collectionneurs pour accumuler les éléments dans une liste inversée.Cela fait beaucoup d'insertions à l'avant de ArrayList objets, donc il y a beaucoup de copie en cours.

Stream<T> input = ... ;
List<T> output =
    input.collect(ArrayList::new,
                  (list, e) -> list.add(0, e),
                  (list1, list2) -> list1.addAll(0, list2));

Il est probablement possible d'écrire un collecteur inverseur beaucoup plus efficace en utilisant une sorte de structure de données personnalisée.

MISE À JOUR 2016-01-29

Étant donné que cette question a retenu un peu l'attention récemment, je pense que je devrais mettre à jour ma réponse pour résoudre le problème d'insertion au début de ArrayList.Ce sera horriblement inefficace avec un grand nombre d'éléments, nécessitant une copie O(N^2).

Il est préférable d'utiliser un ArrayDeque au lieu de cela, ce qui prend en charge efficacement l'insertion à l'avant.Un petit problème est que nous ne pouvons pas utiliser la forme à trois arguments de Stream.collect();cela nécessite que le contenu du deuxième argument soit fusionné dans le premier argument, et il n'y a pas d'opération groupée "ajouter tout au premier plan" sur Deque.Au lieu de cela, nous utilisons addAll() pour ajouter le contenu du premier argument à la fin du second, puis nous renvoyons le second.Cela nécessite d'utiliser le Collector.of() méthode d'usine.

Le code complet est le suivant :

Deque<String> output =
    input.collect(Collector.of(
        ArrayDeque::new,
        (deq, t) -> deq.addFirst(t),
        (d1, d2) -> { d2.addAll(d1); return d2; }));

Le résultat est un Deque au lieu d'un List, mais cela ne devrait pas poser vraiment de problème, car il peut facilement être itéré ou diffusé dans l'ordre désormais inversé.

Autres conseils

Solution élégante 

List<Integer> list = Arrays.asList(1,2,3,4);
list.stream()
    .boxed() // Converts Intstream to Stream<Integer>
    .sorted(Collections.reverseOrder()) // Method on Stream<Integer>
    .forEach(System.out::println);

La plupart des solutions proposées ici trient ou inversent les IntStream, mais cela nécessite inutilement un stockage intermédiaire. La solution de Stuart Marks est la voie à suivre :

static IntStream revRange(int from, int to) {
    return IntStream.range(from, to).map(i -> to - i + from - 1);
}

Il gère également correctement le débordement, en réussissant ce test :

@Test
public void testRevRange() {
    assertArrayEquals(revRange(0, 5).toArray(), new int[]{4, 3, 2, 1, 0});
    assertArrayEquals(revRange(-5, 0).toArray(), new int[]{-1, -2, -3, -4, -5});
    assertArrayEquals(revRange(1, 4).toArray(), new int[]{3, 2, 1});
    assertArrayEquals(revRange(0, 0).toArray(), new int[0]);
    assertArrayEquals(revRange(0, -1).toArray(), new int[0]);
    assertArrayEquals(revRange(MIN_VALUE, MIN_VALUE).toArray(), new int[0]);
    assertArrayEquals(revRange(MAX_VALUE, MAX_VALUE).toArray(), new int[0]);
    assertArrayEquals(revRange(MIN_VALUE, MIN_VALUE + 1).toArray(), new int[]{MIN_VALUE});
    assertArrayEquals(revRange(MAX_VALUE - 1, MAX_VALUE).toArray(), new int[]{MAX_VALUE - 1});
}

Question générale:

Stream ne stocke aucun élément.

Ainsi, itérer les éléments dans l’ordre inverse n’est pas possible sans stocker les éléments dans une collection intermédiaire.

Stream.of("1", "2", "20", "3")
      .collect(Collectors.toCollection(ArrayDeque::new)) // or LinkedList
      .descendingIterator()
      .forEachRemaining(System.out::println);

Mise à jour:Changement de LinkedList en ArrayDeque (mieux) voir ici pour plus de détails

Impressions :

3

20

2

1

D'ailleurs, en utilisant sort la méthode n'est pas correcte lors du tri, PAS de l'inverse (en supposant que le flux puisse contenir des éléments non ordonnés)

Question spécifique :

J'ai trouvé cela simple, plus facile et intuitif (copié @Holger commentaire)

IntStream.iterate(to - 1, i -> i - 1).limit(to - from)

sans bibliothèque externe...

import java.util.List;
import java.util.Collections;
import java.util.stream.Collector;

public class MyCollectors {

    public static <T> Collector<T, ?, List<T>> toListReversed() {
        return Collectors.collectingAndThen(Collectors.toList(), l -> {
            Collections.reverse(l);
            return l;
        });
    }

}

Si mis en œuvre Comparable<T> (ex. Integer, String, Date), vous pouvez le faire en utilisant Comparator.reverseOrder().

List<Integer> list = Arrays.asList(1, 2, 3, 4);
list.stream()
     .sorted(Comparator.reverseOrder())
     .forEach(System.out::println);

Vous pouvez définir votre propre collecteur qui collecte les éléments dans l'ordre inverse :

public static <T> Collector<T, List<T>, List<T>> inReverse() {
    return Collector.of(
        ArrayList::new,
        (l, t) -> l.add(t),
        (l, r) -> {l.addAll(r); return l;},
        Lists::<T>reverse);
}

Et utilisez-le comme :

stream.collect(inReverse()).forEach(t -> ...)

J'utilise un ArrayList dans l'ordre direct pour insérer efficacement la collecte des éléments (à la fin de la liste) et Guava Lists.reverse pour donner efficacement une vue inversée de la liste sans en faire une autre copie.

Voici quelques cas de test pour le collecteur personnalisé :

import static org.hamcrest.MatcherAssert.assertThat;
import static org.hamcrest.Matchers.*;

import java.util.ArrayList;
import java.util.List;
import java.util.function.BiConsumer;
import java.util.function.BinaryOperator;
import java.util.function.Function;
import java.util.function.Supplier;
import java.util.stream.Collector;

import org.hamcrest.Matchers;
import org.junit.Test;

import com.google.common.collect.Lists;

public class TestReverseCollector {
    private final Object t1 = new Object();
    private final Object t2 = new Object();
    private final Object t3 = new Object();
    private final Object t4 = new Object();

    private final Collector<Object, List<Object>, List<Object>> inReverse = inReverse();
    private final Supplier<List<Object>> supplier = inReverse.supplier();
    private final BiConsumer<List<Object>, Object> accumulator = inReverse.accumulator();
    private final Function<List<Object>, List<Object>> finisher = inReverse.finisher();
    private final BinaryOperator<List<Object>> combiner = inReverse.combiner();

    @Test public void associative() {
        final List<Object> a1 = supplier.get();
        accumulator.accept(a1, t1);
        accumulator.accept(a1, t2);
        final List<Object> r1 = finisher.apply(a1);

        final List<Object> a2 = supplier.get();
        accumulator.accept(a2, t1);
        final List<Object> a3 = supplier.get();
        accumulator.accept(a3, t2);
        final List<Object> r2 = finisher.apply(combiner.apply(a2, a3));

        assertThat(r1, Matchers.equalTo(r2));
    }

    @Test public void identity() {
        final List<Object> a1 = supplier.get();
        accumulator.accept(a1, t1);
        accumulator.accept(a1, t2);
        final List<Object> r1 = finisher.apply(a1);

        final List<Object> a2 = supplier.get();
        accumulator.accept(a2, t1);
        accumulator.accept(a2, t2);
        final List<Object> r2 = finisher.apply(combiner.apply(a2, supplier.get()));

        assertThat(r1, equalTo(r2));
    }

    @Test public void reversing() throws Exception {
        final List<Object> a2 = supplier.get();
        accumulator.accept(a2, t1);
        accumulator.accept(a2, t2);

        final List<Object> a3 = supplier.get();
        accumulator.accept(a3, t3);
        accumulator.accept(a3, t4);

        final List<Object> r2 = finisher.apply(combiner.apply(a2, a3));

        assertThat(r2, contains(t4, t3, t2, t1));
    }

    public static <T> Collector<T, List<T>, List<T>> inReverse() {
        return Collector.of(
            ArrayList::new,
            (l, t) -> l.add(t),
            (l, r) -> {l.addAll(r); return l;},
            Lists::<T>reverse);
    }
}

réaction des cyclopes StreamUtils a une méthode Stream inversée (javadoc). 

  StreamUtils.reverse(Stream.of("1", "2", "20", "3"))
             .forEach(System.out::println);

Il fonctionne en collectant dans une ArrayList, puis en utilisant la classe ListIterator qui peut itérer dans les deux sens, pour parcourir la liste en arrière.

Si vous disposez déjà d’une Liste, elle sera plus efficace

  StreamUtils.reversedStream(Arrays.asList("1", "2", "20", "3"))
             .forEach(System.out::println);

Voici la solution que j'ai trouvée :

private static final Comparator<Integer> BY_ASCENDING_ORDER = Integer::compare;
private static final Comparator<Integer> BY_DESCENDING_ORDER = BY_ASCENDING_ORDER.reversed();

puis en utilisant ces comparateurs :

IntStream.range(-range, 0).boxed().sorted(BY_DESCENDING_ORDER).forEach(// etc...

Je suggérerais d'utiliser jOOλ, c'est une excellente bibliothèque qui ajoute de nombreuses fonctionnalités utiles aux flux et aux lambdas Java 8.

Vous pouvez alors procéder comme suit :

List<Integer> list = Arrays.asList(1,2,3,4);    
Seq.seq(list).reverse().forEach(System.out::println)

Aussi simple que cela.C'est une bibliothèque assez légère qui mérite d'être ajoutée à n'importe quel projet Java 8.

Manière la plus simple (collecte simple - prend en charge les flux parallèles) :

public static <T> Stream<T> reverse(Stream<T> stream) {
    return stream
            .collect(Collector.of(
                    () -> new ArrayDeque<T>(),
                    ArrayDeque::addFirst,
                    (q1, q2) -> { q2.addAll(q1); return q2; })
            )
            .stream();
}

Voie avancée (prend en charge les flux parallèles de manière continue) :

public static <T> Stream<T> reverse(Stream<T> stream) {
    Objects.requireNonNull(stream, "stream");

    class ReverseSpliterator implements Spliterator<T> {
        private Spliterator<T> spliterator;
        private final Deque<T> deque = new ArrayDeque<>();

        private ReverseSpliterator(Spliterator<T> spliterator) {
            this.spliterator = spliterator;
        }

        @Override
        @SuppressWarnings({"StatementWithEmptyBody"})
        public boolean tryAdvance(Consumer<? super T> action) {
            while(spliterator.tryAdvance(deque::addFirst));
            if(!deque.isEmpty()) {
                action.accept(deque.remove());
                return true;
            }
            return false;
        }

        @Override
        public Spliterator<T> trySplit() {
            // After traveling started the spliterator don't contain elements!
            Spliterator<T> prev = spliterator.trySplit();
            if(prev == null) {
                return null;
            }

            Spliterator<T> me = spliterator;
            spliterator = prev;
            return new ReverseSpliterator(me);
        }

        @Override
        public long estimateSize() {
            return spliterator.estimateSize();
        }

        @Override
        public int characteristics() {
            return spliterator.characteristics();
        }

        @Override
        public Comparator<? super T> getComparator() {
            Comparator<? super T> comparator = spliterator.getComparator();
            return (comparator != null) ? comparator.reversed() : null;
        }

        @Override
        public void forEachRemaining(Consumer<? super T> action) {
            // Ensure that tryAdvance is called at least once
            if(!deque.isEmpty() || tryAdvance(action)) {
                deque.forEach(action);
            }
        }
    }

    return StreamSupport.stream(new ReverseSpliterator(stream.spliterator()), stream.isParallel());
}

Notez que vous pouvez rapidement l'étendre à d'autres types de flux (IntStream, ...).

Essai:

// Use parallel if you wish only
revert(Stream.of("One", "Two", "Three", "Four", "Five", "Six").parallel())
    .forEachOrdered(System.out::println);

Résultats:

Six
Five
Four
Three
Two
One

Notes complémentaires: Le simplest way ce n'est pas très utile lorsqu'il est utilisé avec d'autres opérations de flux (la jointure de collecte brise le parallélisme).Le advance way n'a pas ce problème, et il conserve également les caractéristiques initiales du flux, par exemple SORTED, et donc, c'est la voie à suivre pour l'utiliser avec d'autres opérations de flux après l'inverse.

Qu’en est-il de cette méthode utilitaire ?

public static <T> Stream<T> getReverseStream(List<T> list) {
    final ListIterator<T> listIt = list.listIterator(list.size());
    final Iterator<T> reverseIterator = new Iterator<T>() {
        @Override
        public boolean hasNext() {
            return listIt.hasPrevious();
        }

        @Override
        public T next() {
            return listIt.previous();
        }
    };
    return StreamSupport.stream(Spliterators.spliteratorUnknownSize(
            reverseIterator,
            Spliterator.ORDERED | Spliterator.IMMUTABLE), false);
}

Semble fonctionner avec tous les cas sans duplication.

On pourrait écrire un collecteur qui collecte les éléments dans l’ordre inverse :

public static <T> Collector<T, ?, Stream<T>> reversed() {
    return Collectors.collectingAndThen(Collectors.toList(), list -> {
        Collections.reverse(list);
        return list.stream();
    });
}

Et utilisez-le comme ceci :

Stream.of(1, 2, 3, 4, 5).collect(reversed()).forEach(System.out::println);

Réponse originale (contient un bug - cela ne fonctionne pas correctement pour les flux parallèles) :

Une méthode d’inversion de flux à usage général pourrait ressembler à :

public static <T> Stream<T> reverse(Stream<T> stream) {
    LinkedList<T> stack = new LinkedList<>();
    stream.forEach(stack::push);
    return stack.stream();
}

Concernant la question spécifique de la génération d'un reverse IntStream:

a partir de Java9 vous pouvez utiliser la version à trois arguments du IntStream.iterate(...):

IntStream.iterate(10, x -> x >= 0, x -> x - 1).forEach(System.out::println);

// Out: 10 9 8 7 6 5 4 3 2 1 0

où:

IntStream.iterate​(int seed, IntPredicate hasNext, IntUnaryOperator next);

  • seed - l'élément initial ;
  • hasNext - un prédicat s'appliquer aux éléments pour déterminer quand le flux doit se terminer;
  • next - Une fonction à appliquer à l'élément précédent pour produire un nouvel élément.

Pour référence, je regardais le même problème, je voulais joindre la valeur de chaîne des éléments de flux dans l'ordre inverse.

itemList = {dernier, milieu, premier } => premier, milieu, dernier

J'ai commencé à utiliser une collection intermédiaire avec collectingAndThen depuis comonade ou la ArrayDeque collectionneur de Stuart Marques, même si je n'étais pas satisfait de la collecte intermédiaire et du streaming à nouveau

itemList.stream()
        .map(TheObject::toString)
        .collect(Collectors.collectingAndThen(Collectors.toList(),
                                              strings -> {
                                                      Collections.reverse(strings);
                                                      return strings;
                                              }))
        .stream()
        .collect(Collector.joining());

J'ai donc parcouru la réponse de Stuart Marks qui utilisait le Collector.of usine, qui a l'intéressant finisseur lambda.

itemList.stream()
        .collect(Collector.of(StringBuilder::new,
                             (sb, o) -> sb.insert(0, o),
                             (r1, r2) -> { r1.insert(0, r2); return r1; },
                             StringBuilder::toString));

Puisque dans ce cas le flux n'est pas parallèle, le combineur n'est pas très pertinent, j'utilise insert de toute façon, par souci de cohérence du code, mais cela n'a pas d'importance car cela dépend du constructeur de chaînes construit en premier.

J'ai regardé le StringJoiner, mais il n'a pas de insert méthode.

Répondre à une question spécifique sur l'inversion avec IntStream ci-dessous a fonctionné pour moi :

IntStream.range(0, 10)
  .map(x -> x * -1)
  .sorted()
  .map(Math::abs)
  .forEach(System.out::println);

Pas purement Java8, mais si vous utilisez la méthode Lists.reverse() de guava conjointement, vous pouvez facilement y parvenir :

List<Integer> list = Arrays.asList(1,2,3,4);
Lists.reverse(list).stream().forEach(System.out::println);

ArrayDeque sont plus rapides dans la pile qu’une Stack ou une LinkedList."push()" insère des éléments à l'avant du Deque

 protected <T> Stream<T> reverse(Stream<T> stream) {
    ArrayDeque<T> stack = new ArrayDeque<>();
    stream.forEach(stack::push);
    return stack.stream();
}

Inversion de chaîne ou n'importe quel tableau

(Stream.of("abcdefghijklm 1234567".split("")).collect(Collectors.collectingAndThen(Collectors.toList(),list -> {Collections.reverse(list);return list;}))).stream().forEach(System.out::println);

le fractionnement peut être modifié en fonction du délimiteur ou de l'espace

la solution la plus simple consiste à utiliser List::listIterator et Stream::generate

List<Integer> list = Arrays.asList(1, 2, 3, 4, 5);
ListIterator<Integer> listIterator = list.listIterator(list.size());

Stream.generate(listIterator::previous)
      .limit(list.size())
      .forEach(System.out::println);

C'est comme ça que je procède.

Je n'aime pas l'idée de créer une nouvelle collection et de l'inverser.

L'idée IntStream#map est plutôt intéressante, mais je préfère la méthode IntStream#iterate, car je pense que l'idée d'un compte à rebours jusqu'à zéro est mieux exprimée avec la méthode iterate et plus facile à comprendre en termes de parcours du tableau d'arrière en avant.

import static java.lang.Math.max;

private static final double EXACT_MATCH = 0d;

public static IntStream reverseStream(final int[] array) {
    return countdownFrom(array.length - 1).map(index -> array[index]);
}

public static DoubleStream reverseStream(final double[] array) {
    return countdownFrom(array.length - 1).mapToDouble(index -> array[index]);
}

public static <T> Stream<T> reverseStream(final T[] array) {
    return countdownFrom(array.length - 1).mapToObj(index -> array[index]);
}

public static IntStream countdownFrom(final int top) {
    return IntStream.iterate(top, t -> t - 1).limit(max(0, (long) top + 1));
}

Voici quelques tests pour prouver que cela fonctionne :

import static java.lang.Integer.MAX_VALUE;
import static org.junit.Assert.*;

@Test
public void testReverseStream_emptyArrayCreatesEmptyStream() {
    Assert.assertEquals(0, reverseStream(new double[0]).count());
}

@Test
public void testReverseStream_singleElementCreatesSingleElementStream() {
    Assert.assertEquals(1, reverseStream(new double[1]).count());
    final double[] singleElementArray = new double[] { 123.4 };
    assertArrayEquals(singleElementArray, reverseStream(singleElementArray).toArray(), EXACT_MATCH);
}

@Test
public void testReverseStream_multipleElementsAreStreamedInReversedOrder() {
    final double[] arr = new double[] { 1d, 2d, 3d };
    final double[] revArr = new double[] { 3d, 2d, 1d };
    Assert.assertEquals(arr.length, reverseStream(arr).count());
    Assert.assertArrayEquals(revArr, reverseStream(arr).toArray(), EXACT_MATCH);
}

@Test
public void testCountdownFrom_returnsAllElementsFromTopToZeroInReverseOrder() {
    assertArrayEquals(new int[] { 4, 3, 2, 1, 0 }, countdownFrom(4).toArray());
}

@Test
public void testCountdownFrom_countingDownStartingWithZeroOutputsTheNumberZero() {
    assertArrayEquals(new int[] { 0 }, countdownFrom(0).toArray());
}

@Test
public void testCountdownFrom_doesNotChokeOnIntegerMaxValue() {
    assertEquals(true, countdownFrom(MAX_VALUE).anyMatch(x -> x == MAX_VALUE));
}

@Test
public void testCountdownFrom_givesZeroLengthCountForNegativeValues() {
    assertArrayEquals(new int[0], countdownFrom(-1).toArray());
    assertArrayEquals(new int[0], countdownFrom(-4).toArray());
}

Dans tout cela, je ne vois pas la réponse à laquelle je voudrais répondre en premier.

Ce n’est pas exactement une réponse directe à la question, mais c’est une solution potentielle au problème.

Construisez simplement la liste à l’envers en premier lieu.Si vous le pouvez, utilisez une LinkedList au lieu d'une ArrayList et lorsque vous ajoutez des éléments, utilisez "Push" au lieu d'ajouter.La liste sera construite dans l’ordre inverse et sera ensuite diffusée correctement sans aucune manipulation.

Cela ne convient pas aux cas où vous avez affaire à des tableaux ou des listes primitifs déjà utilisés de diverses manières, mais qui fonctionnent bien dans un nombre surprenant de cas.

Liste newStream = list.stream().sorted(Collections.reverseOrder()).collect(Collectors.toList());newStream.forEach(System.out::println);

La manière la plus générique et la plus simple d’inverser une liste sera :

public static <T> void reverseHelper(List<T> li){

 li.stream()
.sorted((x,y)-> -1)
.collect(Collectors.toList())
.forEach(System.out::println);

    }

Méthode Java 8 pour procéder :

    List<Integer> list = Arrays.asList(1,2,3,4);
    Comparator<Integer> comparator = Integer::compare;
    list.stream().sorted(comparator.reversed()).forEach(System.out::println);
Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top