जावा स्ट्रीम एपीआई

Question

का उपयोग करने के लिए शाखा और बाउंड लूप को कनवर्ट करें मेरे पास एक साधारण शाखा और बाउंड एल्गोरिदम है जो ट्रैवलिंग सेल्समैन समस्या के एक संस्करण पर काम करता है और मैंने सोचा कि यह जावा 8 स्ट्रीम एपीआई का उपयोग करने के लिए इसे आजमाने और बदलने में मजेदार होगा । मुझे साइड इफेक्ट्स पर भरोसा किए बिना इसे कैसे करना है, यह पता लगाने में मुश्किल हो रही है।

प्रारंभिक कोड

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); 
     } 
    } 
} 

मैं इसे स्ट्रीम एपीआई को बदलने में एक पहला शॉट लिया और निम्नलिखित के साथ आया था:

जावा 8 संस्करण

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; 

मुख्य समस्या यह है कि नोड कॉन्स्यूमर को सर्वश्रेष्ठ पाथ और बाध्य संदर्भित करना है, जो हैं अंतिम चर नहीं। मैं उन्हें चारों ओर काम करने के लिए अंतिम परमाणु संदर्भ चर बना सकता हूं, लेकिन मुझे लगता है कि इस तरह के स्ट्रीम एपीआई की भावना का उल्लंघन करता है। क्या कोई मुझे प्रारंभिक एल्गोरिदम को एक और बेवकूफ कार्यान्वयन में आसवित करने में मदद कर सकता है?

Answer 1

मुझे आश्चर्य है कि reduce का उपयोग करने का तरीका यह है कि, क्योंकि यह आपको बाहरी चर की आवश्यकता के बिना मूल्यों को ट्रैक करने की अनुमति देता है।

कुछ ऐसा कुछ है (मुझे आपके उपरोक्त कोड के कुछ विवरणों पर अनुमान लगाना पड़ा है, लेकिन उम्मीद है कि मैं सही रास्ते पर हूं)।

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(); 

वैकल्पिक रूप से, आप jOOλ में Seq (स्ट्रीम करने के लिए एक अनुक्रमिक विस्तार) का उपयोग कर देखो, और बदले foldLeft इस्तेमाल कर सकते हैं।