Convertir une branche et une boucle liée pour utiliser l'API Java Stream

Question

Convertir une branche et une boucle liée pour utiliser l'API Java Stream

J'ai une branche simple et un algorithme Lié qui fonctionne sur une variante du problème du vendeur itinérant et je pensais que ce serait amusant d'essayer de le convertir pour utiliser l'API Java 8 Stream. J'ai du mal à trouver comment le faire sans compter sur les effets secondaires, cependant.

Code initial

int bound = Integer.MAX_VALUE;
List<Location> bestPath = null;

while(!queue.isEmpty()) {
    Node curr = queue.poll();
    //bound exceeds best, bail
    if (curr.getBound() >= bound) { 
        return bestPath;
    }
    //have a complete path, save it
    if(curr.getPath().size() == locations.size()) {
        bestPath = curr.getPath();
        bound = curr.getBound();
        continue;
    }
    //incomplete path - add all possible next steps
    Set<Location> unvisited = new HashSet<>(locations);
    unvisited.removeAll(curr.getPath());
    for (Location l : unvisited) {
        List<Location> newPath = new ArrayList<>(curr.getPath());
        newPath.add(l);
        Node newNode = new Node(newPath, getBoundForPath(newPath));
        if (newNode.getBound() <= bound){
            queue.add(newNode);
        }
    }
}

J'ai pris une première chance de le convertir en API de flux et j'ai trouvé ce qui suit:

Java 8 Version

Consumer<Node> nodeConsumer = node -> {
    if(node.getPath().size() == locations.size() ) {
        bestPath = node.getPath();
        bound = node.getBound();
    } else {
        locations.stream()
            .filter(l -> !node.getPath().contains(l))
            .map(l -> {
                List<Location> newPath = new ArrayList<>(node.getPath());
                newPath.add(s);
                return new Node(newPath, getBoundForPath(newPath));
            })
            .filter(newNode -> newNode.getBound() <= bound)
            .forEach(queue::add);
    }
};

Stream.generate(() -> queue.poll())
    .peek(nodeConsumer)
    .filter(s -> s.getBound() > bound)
    .findFirst();

return bestPath;

Le problème principal est - ce que le nodeConsumer doit référencer bestPath et bound, qui ne sont pas des variables finales. Je pourrais en faire des variables AtomicReference finales pour contourner cela, mais j'ai l'impression que ce genre de violation de l'esprit de l'API stream. Quelqu'un peut-il m'aider à distiller l'algorithme initial dans une implémentation plus idiomatique?

8

French java java-8 java-stream algorithm lambda

Author: Tagir Valeev, 2015-09-30

Source

1 answers

score 1 · Answer 1

Je me demande si l'utilisation de reduce est la façon de procéder, car elle vous permet de suivre les valeurs sans avoir besoin de variables externes.

Quelque chose comme ce qui suit (j'ai dû deviner quelques-uns des détails de votre code ci-dessus, mais j'espère que je suis sur la bonne voie).

    final BiFunction<Entry<Integer, List<Location>>, Node, Entry<Integer, List<Location>>> accumulator
        = (identity, node) -> {
            if (node.getPath().size() == locations.size() ) {
                return new SimpleEntry<>(node.getBound(), node.getPath());
            } else {
                locations.stream()
                    .filter(l -> !node.getPath().contains(l))
                    .map(l -> {
                        List<Location> newPath = new ArrayList<>(node.getPath());
                        newPath.add(l);
                        return new Node(newPath, getBoundForPath(newPath));
                    })
                    .filter(newNode -> newNode.getBound() <= identity.getKey())
                    .forEach(queue::add);
                return identity;
            }
        };

    final BinaryOperator<Entry<Integer, List<Location>>> combiner
        = (left, right) -> left.getKey() < right.getKey() ? left : right;

    final Entry<Integer, List<Location>> identity
        = new SimpleEntry<>(Integer.MAX_VALUE, null);

    final List<Location> bestValue = Stream.generate(queue::poll)
        .reduce(identity, accumulator, combiner)
        .getValue();

Alternativement, vous pouvez envisager d'utiliser Seqdans Joooλ (une extension séquentielle aux flux) et utiliser foldLeft à la place.