4
votes

Itérateur en sens inverse - pour la fonctionnalité reductionRight

Tentative d'implémentation de certaines fonctionnalités de reductionRight. Pour les performances, ce serait bien d'itérer de droite à gauche, sans tout inverser d'abord, puis de gauche à droite. Normalement, nous faisons:

ArrayList<...> a = new ArrayList<...>();

// Add elements to list.

// Generate an iterator. Start just after the last element.
ListIterator li = a.listIterator(a.size());

// Iterate in reverse.
while(li.hasPrevious()) {
  System.out.println(li.previous());
}

mais je cherche quelque chose comme:

Iteratable iterable ...;
Iterator iterator = iterable.reverseIterator();
iterator.next();

Je vois cette solution: Parcourir une liste dans l'ordre inverse en Java

La réponse acceptée actuelle dit que cela fonctionne:

Iteratable iterable ...;
Iterator iterator = iterable.iterator();
iterator.next();

Quelqu'un sait comment implémenter l'itération inverse avec seulement un Iterable en main? Je n'ai pas de ArrayList ou List en main, j'ai un Iterable en main. Je suppose que je peux convertir l'Iterable en ArrayList, inverser la liste, puis obtenir un itérateur, mais ce ne serait pas amusant :)

java iterator iterable

6 commentaires

Vous ne pouvez pas. Iterator ne prend en charge la traversée que dans une seule direction. Vous devrez copier les éléments dans une pile et les faire apparaître. Étant donné que vous essayez d'atteindre des performances, je ne ferais pas cela - voyez si vous pouvez repeindre votre réduction dans l'autre sens.

@BoristheSpider ouais c'est ce que j'ai pensé, étant donné les informations dans OP, pouvez-vous donner la meilleure solution possible? Merci

N'oubliez pas qu'un Iterable peut être théoriquement infini. C'est pourquoi cela ne peut pas être pris en charge au niveau de l'API. Vous devez utiliser une structure de données qui prend en charge les traversées inverses.

@JoeC c'est pour une bibliothèque donc essayer de prendre en charge autant de types de données que possible en utilisant Iterable

github.com/google/guava/issues/980 si vous avez le temps, sinon simplement utiliser les listes de goyave.newArrayList (iterable) .reverse ()

Le point de @ JoeC est bon à garder à l'esprit - les deux Stream et Iterator peuvent être infinis; prenez Iterators.cycle de Guava par exemple. J'éviterais d'exposer une API qui permet des choses que vous ne pouvez pas prendre en charge.

3 Réponses :

1
votes

Vous devrez parcourir une fois l ' itérateur original pour construire un itérateur inversé (en supposant que votre itérateur original est fini) .

Par exemple:

static <T> Iterator<T> getReversedIterator(Iterable<T> iterable) {
    Iterator<T> iter = iterable.iterator();
    List<T> rev = new ArrayList<>();
    while (iter.hasNext()) {
        rev.add (0, iter.next());
    }
    return rev.iterator();
}

0 commentaires

2
votes

Réponse simple: impossible de manière générique et performante.

L'essence de l'itérateur est de vous donner une direction, pas les deux. Et imaginez une liste uniquement liée. Cette chose n'a vraiment "qu'une seule direction"!

Donc, la question de savoir comment inverser une chose itérable vous oblige vraiment à regarder l'implémentation exacte. Sans cette possibilité, vous devez utiliser une structure de données intermédiaire pour récupérer toutes les entrées avant d'annuler.

0 commentaires

1
votes

Si vous avez un Iterable en main, comme vous l'avez écrit dans votre question, quelqu'un vous l'a fourni. Je suggérerais de demander au fournisseur de fournir un Iterable qui prend en charge l'itération inverse.

1 commentaires

Cela ou implémentez simplement réduire et n'implémentez pas reductionRight et attendez-vous à ce qu'ils aient la liste dans le bon ordre. Mais je pense que c'est bien de faire le travail pour l'utilisateur de la lib.