फिबोनाची संख्याओं को स्ट्रीम करने के लिए स्प्लिटरेटर को कैसे कार्यान्वित करें?

Question

मैं जावा 8 Spliterator के साथ खेल रहा हूं और एक दिए गए एन तक Fibonacci संख्याओं को स्ट्रीम करने के लिए एक बनाया है। तो फिबोनैकी श्रृंखला 0, 1, 1, 2, 3, 5, 8, ...

n fib(n) 
----------- 
-1 0 
1 0 
2 1 
3 1 
4 2 

के बाद के लिए मेरे कार्यान्वयन जो ढेर स्मृति से बाहर चलाने से पहले 1 के एक झुंड प्रिंट है। क्या आप मुझे बग खोजने में मदद कर सकते हैं? (मुझे लगता है कि यह currentIndex को आगे नहीं बढ़ा रहा है, लेकिन मुझे यकीन नहीं है कि इसे किस मूल्य पर सेट करना है)।

संपादित करें 1: यदि आप उत्तर देने का निर्णय लेते हैं, तो कृपया इसे प्रश्न के लिए प्रासंगिक रखें। यह सवाल कुशल फाइबोनैकी नंबर पीढ़ी के बारे में नहीं है; यह स्प्लिटरेटर सीखने के बारे में है।

FibonacciSpliterator:

@RequiredArgsConstructor 
public class FibonacciSpliterator implements Spliterator<FibonacciPair> { 
    private int currentIndex = 3; 
    private FibonacciPair pair = new FibonacciPair(0, 1); 

    private final int n; 

    @Override 
    public boolean tryAdvance(Consumer<? super FibonacciPair> action) { 
//  System.out.println("tryAdvance called."); 
//  System.out.printf("tryAdvance: currentIndex = %d, n = %d, pair = %s.\n", currentIndex, n, pair); 

     action.accept(pair); 

     return n - currentIndex >= 2; 
    } 

    @Override 
    public Spliterator<FibonacciPair> trySplit() { 
//  System.out.println("trySplit called."); 

     FibonacciSpliterator fibonacciSpliterator = null; 

     if (n - currentIndex >= 2) { 
//   System.out.printf("trySplit Begin: currentIndex = %d, n = %d, pair = %s.\n", currentIndex, n, pair); 

      fibonacciSpliterator = new FibonacciSpliterator(n); 

      long currentFib = pair.getMinusTwo() + pair.getMinusOne(); 
      long nextFib = pair.getMinusOne() + currentFib; 

      fibonacciSpliterator.pair = new FibonacciPair(currentFib, nextFib); 
      fibonacciSpliterator.currentIndex = currentIndex + 3; 

//   System.out.printf("trySplit End: currentIndex = %d, n = %d, pair = %s.\n", currentIndex, n, pair); 
     } 

     return fibonacciSpliterator; 
    } 

    @Override 
    public long estimateSize() { 
     return n - currentIndex; 
    } 

    @Override 
    public int characteristics() { 
     return ORDERED | IMMUTABLE | NONNULL; 
    } 
} 

FibonacciPair:

@RequiredArgsConstructor 
@Value 
public class FibonacciPair { 
    private final long minusOne; 
    private final long minusTwo; 

    @Override 
    public String toString() { 
     return String.format("%d %d ", minusOne, minusTwo); 
    } 
} 

उपयोग:

Spliterator<FibonacciPair> spliterator = new FibonacciSpliterator(5); 

StreamSupport.stream(spliterator, true) 
    .forEachOrdered(System.out::print); 

Answer 1

ठीक है, चलिए स्प्लिटरेटर लिखें। OfLong का उपयोग करना अभी भी बहुत उबाऊ है: चलिए BigInteger पर स्विच करें और 92 तक उपयोगकर्ता को सीमित न करें। यहां मुश्किल चीज तुरंत दिए गए फिबोनाची नंबर पर कूदना है। मैं इस उद्देश्य के लिए here वर्णित मैट्रिक्स गुणा एल्गोरिदम का उपयोग करूंगा।

static class FiboSpliterator implements Spliterator<BigInteger> { 
    private final static BigInteger[] STARTING_MATRIX = { 
     BigInteger.ONE, BigInteger.ONE, 
     BigInteger.ONE, BigInteger.ZERO}; 

    private BigInteger[] state; // previous and current numbers 
    private int cur; // position 
    private final int fence; // max number to cover by this spliterator 

    public FiboSpliterator(int max) { 
     this(0, max); 
    } 

    // State is not initialized until traversal 
    private FiboSpliterator(int cur, int fence) { 
     assert fence >= 0; 
     this.cur = cur; 
     this.fence = fence; 
    } 

    // Multiplication of 2x2 matrix, by definition  
    static BigInteger[] multiply(BigInteger[] m1, BigInteger[] m2) { 
     return new BigInteger[] { 
      m1[0].multiply(m2[0]).add(m1[1].multiply(m2[2])), 
      m1[0].multiply(m2[1]).add(m1[1].multiply(m2[3])), 
      m1[2].multiply(m2[0]).add(m1[3].multiply(m2[2])), 
      m1[2].multiply(m2[1]).add(m1[3].multiply(m2[3]))}; 
    } 

    // Log(n) algorithm to raise 2x2 matrix to n-th power  
    static BigInteger[] power(BigInteger[] m, int n) { 
     assert n > 0; 
     if(n == 1) { 
      return m; 
     } 
     if(n % 2 == 0) { 
      BigInteger[] root = power(m, n/2); 
      return multiply(root, root); 
     } else { 
      return multiply(power(m, n-1), m); 
     } 
    } 

    @Override 
    public boolean tryAdvance(Consumer<? super BigInteger> action) { 
     if(cur == fence) 
      return false; // traversal finished 
     if(state == null) { 
      // initialize state: done only once 
      if(cur == 0) { 
       state = new BigInteger[] {BigInteger.ZERO, BigInteger.ONE}; 
      } else { 
       BigInteger[] res = power(STARTING_MATRIX, cur); 
       state = new BigInteger[] {res[1], res[0]}; 
      } 
     } 
     action.accept(state[1]); 
     // update state 
     if(++cur < fence) { 
      BigInteger next = state[0].add(state[1]); 
      state[0] = state[1]; 
      state[1] = next; 
     } 
     return true; 
    } 

    @Override 
    public Spliterator<BigInteger> trySplit() { 
     if(fence - cur < 2) 
      return null; 
     int mid = (fence+cur) >>> 1; 
     if(mid - cur < 100) { 
      // resulting interval is too small: 
      // instead of jumping we just store prefix into array 
      // and return ArraySpliterator 
      BigInteger[] array = new BigInteger[mid-cur]; 
      for(int i=0; i<array.length; i++) { 
       tryAdvance(f -> {}); 
       array[i] = state[0]; 
      } 
      return Spliterators.spliterator(array, ORDERED | NONNULL | SORTED); 
     } 
     // Jump to another position 
     return new FiboSpliterator(cur, cur = mid); 
    } 

    @Override 
    public long estimateSize() { 
     return fence - cur; 
    } 

    @Override 
    public int characteristics() { 
     return ORDERED | IMMUTABLE | SIZED| SUBSIZED | NONNULL | SORTED; 
    } 

    @Override 
    public Comparator<? super BigInteger> getComparator() { 
     return null; // natural order 
    } 
} 

यह वास्तव में तेजी से समानांतर में बहुत बड़ा fence मूल्य के लिए कार्यान्वयन (जैसे 100000): यहाँ मेरी कोड है। शायद यहां तक ​​कि बुद्धिमान कार्यान्वयन भी संभव है जो मैट्रिक्स गुणा के मध्यवर्ती परिणामों को असमान रूप से पुन: उपयोग करने के लिए विभाजित होगा।

Answer 2

तथ्य यह है कि अपने कोड अधूरा है, आपकी tryAdvance विधि में कम से कम दो त्रुटियाँ हैं इसके अलावा पहचानने योग्य। सबसे पहले, आप वास्तव में कोई अग्रिम नहीं कर रहे हैं। आप अपने स्प्लिटरेटर की किसी भी स्थिति को संशोधित नहीं कर रहे हैं। दूसरा, आप बिना शर्त कार्रवाई की accept विधि का आह्वान कर रहे हैं जो इस तथ्य से मेल नहीं खा रहा है कि आप true के बजाय एक सशर्त मूल्य लौट रहे हैं।

tryAdvance का उद्देश्य है:

• के रूप में नाम का सुझाव, एक अग्रिम बनाने के लिए, यानी, एक अगले मूल्य की गणना
• अगर वहाँ एक अगले मूल्य है की कोशिश है कि मूल्य के साथ action.accept आह्वान और true वापसी
• अन्यथा सिर्फ लौट false

नोट आगे अपने trySplit() कि बहुत दृढ़ दिखता नहीं है, मुझे यह भी नहीं पता कि कहां से शुरू करना है। आप बेहतर हैं, AbstractSpliterator से विरासत में हैं और एक कस्टम trySplit() लागू नहीं कर रहे हैं। आपका ऑपरेशन वैसे भी समानांतर निष्पादन से लाभ नहीं उठाता है। उस स्रोत के साथ निर्मित एक धारा केवल समानांतर निष्पादन से लाभ प्राप्त कर सकती है यदि आप शांत महंगी प्रति-तत्व संचालन के साथ इसे चेन करते हैं।

Answer 3

सामान्य रूप से आपको स्प्लिटरेटर को लागू करने की आवश्यकता नहीं है।

Spliterator.OfLong spliterator = Stream 
     .iterate(new long[] { 0, 1 }, 
       prev -> new long[] { prev[1], prev[0] + prev[1] }) 
     .mapToLong(pair -> pair[1]).spliterator(); 

परीक्षण::

for(int i=0; i<20; i++) 
    spliterator.tryAdvance((LongConsumer)System.out::println); 

कृपया ध्यान दें कि long चर में फिबोनैकी संख्या पकड़े संदिग्ध है: क्या तुम सच में एक Spliterator वस्तु की जरूरत है, तो आप इस उद्देश्य के लिए धारा का उपयोग कर सकते यह फिबोनैकी संख्या 92 के बाद overflows ।तो तुम spliterator जो सिर्फ पहले 92 फिबोनैकी संख्या से अधिक दोहराता है, मैं इस उद्देश्य के लिए पूर्वनिर्धारित सरणी का उपयोग करने के सुझाव देंगे बनाना चाहते हैं:

Spliterator.OfLong spliterator = Spliterators.spliterator(new long[] { 
     1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 
     10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 
     3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 
     267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073L, 4807526976L, 
     7778742049L, 12586269025L, 20365011074L, 32951280099L, 53316291173L, 86267571272L, 139583862445L, 
     225851433717L, 365435296162L, 591286729879L, 956722026041L, 1548008755920L, 2504730781961L, 
     4052739537881L, 6557470319842L, 10610209857723L, 17167680177565L, 27777890035288L, 
     44945570212853L, 72723460248141L, 117669030460994L, 190392490709135L, 308061521170129L, 
     498454011879264L, 806515533049393L, 1304969544928657L, 2111485077978050L, 3416454622906707L, 
     5527939700884757L, 8944394323791464L, 14472334024676221L, 23416728348467685L, 37889062373143906L, 
     61305790721611591L, 99194853094755497L, 160500643816367088L, 259695496911122585L, 420196140727489673L, 
     679891637638612258L, 1100087778366101931L, 1779979416004714189L, 2880067194370816120L, 
     4660046610375530309L, 7540113804746346429L 
}, Spliterator.ORDERED); 

सरणी spliterator भी अच्छी तरह से विभाजित करता है, तो आप असली समानांतर प्रसंस्करण होगा।