जावा कतार का सर्वोत्तम कार्यान्वयन?

Question

मैं एक रिकर्सिव इमेज प्रोसेसिंग एल्गोरिदम पर काम कर रहा हूं (जावा में) जो एक बिंदु बिंदु से बाहर, छवि के पिक्सल को दोबारा घुमाता है।

दुर्भाग्य से, यह एक स्टैक ओवरफ़्लो का कारण बनता है। इसलिए मैंने एक कतार-आधारित एल्गोरिदम पर स्विच करने का निर्णय लिया है।

अब, यह सब ठीक और बेवकूफ है- लेकिन इस तथ्य पर विचार करते हुए कि यह कतार बहुत ही कम समय में पिक्सल के हजारों का विश्लेषण कर रही है, जबकि एक अनुमानित स्थिति को बनाए रखने के बिना लगातार पॉपिंग और धक्का दे रहा है (यह कहीं भी हो सकता है लंबाई 100, और 20000 के बीच); कतार कार्यान्वयन में तेजी से पॉपिंग और क्षमताओं को धक्का देना आवश्यक है।

एक लिंक्ड सूची सूची में किसी और चीज को पुन: व्यवस्थित किए बिना तत्वों को धक्का देने की अपनी क्षमता के कारण आकर्षक लगती है, लेकिन इसके लिए पर्याप्त तेज़ होने के लिए, इसे अपने सिर, और इसकी पूंछ दोनों तक आसान पहुंच की आवश्यकता होगी (या दूसरा-से-अंतिम नोड यदि यह दोगुना-लिंक नहीं था)। अफसोस की बात है, हालांकि मुझे जावा में लिंक्ड सूचियों के अंतर्निहित कार्यान्वयन से संबंधित कोई जानकारी नहीं मिल रही है, इसलिए यह कहना मुश्किल है कि एक लिंक की गई सूची वास्तव में जाने का तरीका है ...

यह मुझे मेरे प्रश्न पर लाता है। जावा में कतार इंटरफ़ेस का सबसे अच्छा कार्यान्वयन क्या होगा जो मैं करना चाहता हूं? (मैं कतार के सिर और पूंछ के अलावा किसी अन्य चीज़ को संपादित या यहां तक ​​कि एक्सेस करना नहीं चाहता हूं - मैं किसी भी प्रकार की पुनर्व्यवस्थित या कुछ भी नहीं करना चाहता हूं। फ्लिप पक्ष पर, मैं बहुत धक्का देने का इरादा रखता हूं और पॉपिंग, और कतार काफी आकार बदल जाएगी, इसलिए प्रीलोकेटिंग अक्षम होगी)

Answer 1

LinkedList जाने का एक तरीका प्रतीत होता है, लिंक्डलिस्ट एक दोगुनी जुड़ी सूची है, जो एक क्यूई डेटा संरचना (एफआईएफओ) के लिए अच्छा है। । यह एक प्रमुख/पूंछ संदर्भ रखता है, जिसे आप getFirst() और getLast() द्वारा प्राप्त कर सकते हैं।

Answer 2

यदि आप कतार में वस्तुओं की संभावित मात्रा के ऊपरी बाउंड को जानते हैं, तो सर्कुलर बफर लिंक्डलिस्ट से तेज़ है, क्योंकि लिंक्डलिस्ट कतार में प्रत्येक आइटम के लिए ऑब्जेक्ट (लिंक) बनाता है।

Answer 3

Deque इंटरफ़ेस देखें, जो दोनों सिरों पर सम्मिलन/निष्कासन प्रदान करता है। लिंक्डलिस्ट उस इंटरफ़ेस को लागू करता है (जैसा ऊपर बताया गया है), लेकिन आपके उपयोग के लिए, एक ऐरेडेक बेहतर हो सकता है - आप प्रत्येक नोड के लिए निरंतर ऑब्जेक्ट आवंटन की लागत नहीं ले पाएंगे। फिर फिर, इससे कोई फर्क नहीं पड़ता कि आप किस कार्यान्वयन का उपयोग करते हैं।

सामान्य बहुलकवाद की भलाई खेलने के लिए आता है: इसके किसी भी विशिष्ट कार्यान्वयन के बजाय डेक इंटरफ़ेस के खिलाफ लेखन की सुंदरता यह है कि आप परीक्षण करने के लिए बहुत आसानी से कार्यान्वयन स्विच कर सकते हैं कि कौन सा सर्वश्रेष्ठ प्रदर्शन करता है। इसमें new के साथ बस लाइन बदलें, और शेष कोड वही रहता है।

Answer 4

मुझे लगता है कि आप कुछ ऊपर कार्यान्वयन की तरह साधारण साथ

package DataStructures; 

public class Queue<T> { 

    private Node<T> root; 

    public Queue(T value) { 
     root = new Node<T>(value); 
    } 

    public void enque(T value) { 
     Node<T> node = new Node<T>(value); 
     node.setNext(root); 
     root = node; 
    } 

    public Node<T> deque() { 

     Node<T> node = root; 
     Node<T> previous = null; 

     while(node.next() != null) { 
     previous = node; 
     node = node.next(); 
     } 
     node = previous.next(); 
     previous.setNext(null); 
     return node; 
    } 

    static class Node<T> { 

     private T value; 
     private Node<T> next; 

     public Node (T value) { 
     this.value = value; 
     } 

     public void setValue(T value) { 
     this.value = value; 
     } 

     public T getValue() { 
     return value; 
     } 

     public void setNext(Node<T> next) { 
     this.next = next; 
     } 

     public Node<T> next() { 
     return next; 
     } 
    } 
} 

Answer 5

हालांकि, अगर आप अभी भी पुनरावर्ती एल्गोरिदम उपयोग करना चाहते हैं, तो आप इसे "tail-recursive" जो शायद JVM ढेर से बचने के लिए अनुकूलित है होना करने के लिए बदल सकते हैं कर सकते हैं अतिप्रवाह।

Answer 6

यदि आप लिंक्डलिस्ट का उपयोग सावधान रहें। तो आप इसे इस का उपयोग करते हैं:

LinkedList<String> queue = new LinkedList<String>(); 

तो आप कतार परिभाषा का उल्लंघन कर सकता है, क्योंकि यह संभव है पहले की तुलना में अन्य तत्वों को दूर करने के (वहाँ LinkedList में इस तरह के तरीके हैं)।

लेकिन आप इस तरह से इसका इस्तेमाल करता है, तो:

Queue<String> queue = new LinkedList<String>(); 

यह, ठीक होना चाहिए क्योंकि इस उपयोगकर्ता कि सम्मिलन केवल केवल मोर्चे पर वापस और विलोपन में होने चाहिए करने के लिए सिर-अप है।

आप लिंक्डलिस्ट क्लास को एक PureQueue क्लास में विस्तारित करके कतार इंटरफ़ेस के दोषपूर्ण कार्यान्वयन को दूर कर सकते हैं जो किसी भी अपमानजनक विधियों के असमर्थितऑपरेशन अपवाद को फेंकता है। या आप केवल एक फ़ील्ड के साथ PureQueue बनाकर aggreagation के साथ दृष्टिकोण ले सकते हैं, जो कि लिंक्डलिस्ट ऑब्जेक्ट, सूची है, और एकमात्र विधियां एक डिफ़ॉल्ट कन्स्ट्रक्टर, एक प्रति कन्स्ट्रक्टर, isEmpty(), size(), add(E element), remove(), और element() होगी। उन सभी तरीकों उदाहरण के लिए के रूप में एक-लाइनर्स होना चाहिए,:

/** 
* Retrieves and removes the head of this queue. 
* The worstTime(n) is constant and averageTime(n) is constant. 
* 
* @return the head of this queue. 
* @throws NoSuchElementException if this queue is empty. 
*/ 
public E remove() 
{ 
    return list.removeFirst(); 
} // method remove() 

Answer 7

यह जब ढेर और कतार जावा में लागू करने ArrayDeque बजाय LinkedList का उपयोग करने के लिए बेहतर है। स्टैक इंटरफ़ेस (जब स्टैक थ्रेड-सुरक्षित है) की तुलना में ऐरेडेक तेज होता है, जब स्टैक के रूप में उपयोग किया जाता है, और कतार के रूप में उपयोग किए जाने पर लिंक्डलिस्ट से तेज़ होता है। इस लिंक को देखें Use ArrayDeque instead of LinkedList or Stack।