जावा के लिए घुसपैठ सूची कार्यान्वयन?

Question

जावा के लिए उपलब्ध कोई भी (अच्छी तरह से कार्यान्वित) घुसपैठ डबल लिंक्ड सूची वर्ग (एसएस) है? या मुझे अपना खुद का करना चाहिए? बूस्ट के लिए सी ++: http://beta.boost.org/doc/libs/1_40_0/doc/html/boost/intrusive/list.html है।

घुसपैठ सूची एक कंटेनर है जिसमें (इस मामले में) तत्व के भीतर अगला और पिछला पॉइंटर्स है, इसलिए प्रतिस्थापन और निकालने जैसे विशिष्ट सूची संचालन सीधे कंटेनर वर्ग के बजाय प्राथमिक वर्ग में लक्षित किए जा सकते हैं। कुछ निश्चित स्थितियां हैं, जहां घुसपैठ सूची सबसे अच्छा समाधान है।

मैं एक उपयुक्त उदाहरण देने का प्रयास करता हूं। आइए मान लीजिए कि मैंने अलग-अलग प्रकार के वर्ग X1 और Y2 के स्वामित्व वाली सूची एल सूची 1 और एल सूची 2 को लिंक किया है।

कक्षा क्यू (जिसमें ऐसा करने के लिए कुछ भी नहीं है या आसानी से x1 और वाई 2 के इंटरफेस तक नहीं पहुंचता है) i) को प्रतिस्थापित करने की आवश्यकता है, ii) तत्व ई के लिए ऑपरेशन को हटाएं, जो सूची में हमेशा कहीं मौजूद है, सूची 1 में xor list2 रन-टाइम स्थिति के आधार पर, लेकिन वह जानकारी सीधे कहीं भी संग्रहीत नहीं होती है।

घुसपैठ सूची के साथ क्यू केवल सदस्य तत्व ई के लिए तत्व को संदर्भित कर सकता है और यह हमेशा सही जगह को इंगित करता है।

अन्यथा आपको एक या दूसरे कई स्पष्ट रूप से अधिक जटिल कामकाजों में से चुनना होगा। - तत्व ई के लिए रैपर वर्ग और संचालन I और ii को पूरा करने के लिए अतिरिक्त विधियां। सं।

मूल रूप से, प्रश्न अभी भी प्रदर्शन के बारे में नहीं बल्कि वास्तुशिल्प जटिलता के बारे में है। इसे एक प्रकार की साझा ऑब्जेक्ट स्थिति के रूप में भी समझा जा सकता है जहां समाधान आईएल प्रत्येक क्लाइंट एलएक्स और क्यू

के लिए अद्यतन आवश्यकता से बचाता है कृपया ध्यान दें कि मुझे अन्य मानक कंटेनरों के लिए संगतता की आवश्यकता नहीं है। अज्ञात तत्व वर्ग के साथ उपयोग किए जाने वाले संचालन को जोड़ने, जोड़ने, निकालने और खोजने के साथ बस एक सामान्य घुसपैठ lsit कार्यान्वयन।

धन्यवाद।

Answer 1

मुझे किसी भी मौजूदा कार्यान्वयन से अवगत नहीं है (और नहीं, मैं सामान्य जावा संग्रह को घुसपैठ करने वाला नहीं मानता)।

ऐसा शायद इसलिए है क्योंकि जावा में ऐसी सूची का एकमात्र प्रमुख लाभ होगा remove() कॉल जब आपके पास पहले से ही एलिमेंट को हटाया जाना है (और उस स्थिति में Iterator नहीं है)। जावा में कॉपी-कॉपी-द-एलिमेंट मान्य तर्क नहीं है, क्योंकि जावा List कार्यान्वयन केवल वैसे भी संदर्भों को संभालता है (और पूरी ऑब्जेक्ट को कभी कॉपी नहीं करता है)।

लेकिन आप आसानी से एक सामान्य प्रयोजन List कार्यान्वयन कि आवश्यक इंटरफेस बनाने के द्वारा घुसपैठ लिख सकते हैं:

public interface IntrusiveListElement<E extends<IntrusiveListElement<E>> { 
    public void setNext(E next); 
    public E getNext(); 
    public void setPrev(E prev); 
    public E getPrev(); 
} 

public class IntrusiveList<E extends IntrusiveListElement<E>> implements List<E> { 
    // implement your run-of-the-mill double-linked list here 
} 

आपका तत्व वर्ग ऐसा दिखाई दे सकता:

public class MyBusinessElement implements IntrusiveListElement<MyBusinessElement> { 
    private MyBusinessElement prev; 
    private MyBusinessElement next; 

    public void setNext(MyBusinessElement next) { 
    this.next = next; 
    } 

     public MyBusinessElement getNext() { 
    return next; 
    } 

    public void setPrev(MyBusinessElement prev) { 
    this.prev = prev; 
    } 

    public MyBusinessElement getPrev() { 
    return prev; 
    } 
} 

Answer 2

क्या आपने Deque class पर एक नज़र डाली है? जावाडोक के अनुसार, "एक रैखिक संग्रह जो तत्व प्रविष्टि और दोनों सिरों पर हटाने का समर्थन करता है। नाम डेक" डबल एंड कतार "के लिए छोटा है और आमतौर पर" डेक "कहा जाता है।" इसे ArrayDeque, LinkedBlockingDeque और LinkedList द्वारा लागू किया गया है।

Answer 3

जावा के अर्थशास्त्र डिजाइन घुसपैठ के द्वारा हैं, वे संदर्भों का उपयोग करते हैं और प्रतिलिपि नहीं बनाते हैं। आप मूल रूप से केवल सर्वोत्तम लिंक किए गए सूची कार्यान्वयन को ढूंढना चाहते हैं, जिसमें जावा, LinkedList या जो भी हो, और यह घुसपैठ कर देगा।

import java.util.LinkedList; 

public class Foo { 

    public static void main(String[] args) { 
    String[] i = new String[1]; 
    i[0] = "FOO"; 
    String[] j = new String[1]; 
    j[0] = "BAZ"; 

    LinkedList<String[]> list = new LinkedList<String[]>(); 

    list.add(i); 
    list.add(j); 

    for (String[] x: list) { 
     System.out.println(x[0]); 
    } 

    i[0] = "ZILCH"; 

    for (String[] x: list) { 
     System.out.println(x[0]); 
    } 
    } 
} 

यहां आउटपुट है, ध्यान दें कि मैंने सूची में मूल्य को कैसे बदल दिया है।

FOO 
BAZ 
ZILCH 
BAZ 

Answer 4

अगर आप एसडीके कोड देखें आपको लगता है कि LinkedList वास्तव में, है देखेंगे, एक निजी वर्ग एंट्री जो अगले और पिछले तत्व शामिल हैं की एक सूची। इसलिए, यदि आप इस सूची में MyClass शामिल करते हैं, तो सूची का एक तत्व आपके ऑब्जेक्ट के साथ एक प्रविष्टि होगा और सूची के अगले और पिछले तत्वों के लिए लिंक होगा।

तो, मुझे लगता है कि यह घुसपैठ कर रहा है ...

private static class Entry<E> { 
    E element; 
    Entry<E> next; 
    Entry<E> previous; 

    Entry(E element, Entry<E> next, Entry<E> previous) { 
     this.element = element; 
     this.next = next; 
     this.previous = previous; 
    } 
} 

Answer 5

वहाँ किसी भी (अच्छी तरह से लागू) घुसपैठ डबल लिंक्ड सूची वर्ग (ते) जावा के लिए उपलब्ध है?

मुझे विश्वास नहीं है कि आपको एक मिल जाएगा।

"घुसपैठ" की मेरी समझ सीधे शामिल आवेदन वस्तु भीतर अगले/पिछला संकेत ("अतिक्रमण") की जरूरत है आवेदन वस्तु डेटा संरचना में संग्रहित किया जा रहा है।

यह "पॉइंटर रैपर" दृष्टिकोण के विपरीत है जहां डेटा संरचना नोड में एप्लिकेशन ऑब्जेक्ट में पॉइंटर होता है, इस प्रकार एप्लिकेशन ऑब्जेक्ट में कोई संशोधन की आवश्यकता नहीं होती है। घुसपैठ दृष्टिकोण में a number of benefits है जिसमें डबल-डीरफ्रेंसिंग (नोड के लिए एक बार और नोड के पॉइंटर के लिए ऑब्जेक्ट ऑब्जेक्ट के लिए) "पॉइंटर रैपर" दृष्टिकोण से आम है।

मुझे विश्वास नहीं है कि आपको जावा के लिए एक घुसपैठ डेटा संरचना लाइब्रेरी मिल जाएगी। जावा में सी ++ की कमी है - जैसे टेम्पलेट्स और न ही एकाधिक विरासत, और यह आसानी से किसी ऑब्जेक्ट की कॉपी-बाय-वैल्यू का समर्थन नहीं करता है। इस वजह से, मुझे नहीं लगता कि जावा ऑब्जेक्ट में अगली/पिछली आवृत्ति फ़ील्ड को सामान्य रूप से जोड़ने का कोई तरीका है।

उदाहरण के लिए

, आवेदन वस्तु दिया:

class Foo2 { 
    int bar; 
    Foo2 prev; 
    Foo2 next; 
} 

:

class Foo { 
    int bar; 
} 

किसी भी तरह आप अगले/पिछला खेतों और इसे करने के लिए सूची प्रबंधन के तरीके या इसके एक व्युत्पन्न जोड़ने के लिए सक्षम होना चाहिए इन अनुप्रयोगों के विस्तार के लिए इन क्षेत्रों के साथ बेस क्लास प्रदान करके इन क्षेत्रों को जोड़ने का एक तरीका - यह बूस्ट का दृष्टिकोण है। हालांकि, यह दृष्टिकोण जावा जैसी एकल विरासत भाषा में बहुत सीमित है।

जावा इंटरफेस अक्सर एकाधिक विरासत के लिए जावा का उत्तर होता है, उदा। एक इंटरफेस के लिए getNext() और getPrev() अनुप्रयोग वर्गों के तरीकों की आवश्यकता है। हालांकि, यदि आपको प्रदर्शन कारणों से घुसपैठ डेटा संरचनाओं की आवश्यकता है, तो किसी विधि के माध्यम से अगले/पिछली फ़ील्ड तक पहुंचने से उन लक्ष्यों पर प्रतिकूल प्रभाव पड़ सकता है।

जावा जेनरिक भी आवश्यक तरीके से कक्षाओं का विस्तार नहीं करते हैं।

या मुझे अपना खुद का करना चाहिए?

तो एक सावधानी से मूल्यांकन की जरूरत के लिए एक विशेष मामले के लिए अपने एक बार, सुनिश्चित करें - अपने खुद के रोल। यदि आप सामान्य उद्देश्य के उपयोग के लिए एक सामान्य रोल करने की कोशिश कर रहे हैं, तो मुझे यकीन नहीं है कि यह इसके लायक है।

एक वास्तव में सकल दृष्टिकोण कस्टम अनुप्रयोग वर्ग की जरूरत फ़ील्ड्स जोड़ने के लिए विस्तार करने के लिए होगा:

class Foo3 extends Foo { 
    Foo3 prev; 
    Foo3 next; 
} 

और कटौती-एन-पेस्ट पुन: उपयोग का उपयोग सूची प्रबंधन के तरीके को जोड़ने के लिए।हालांकि मैं दृढ़ता से इस दृष्टिकोण का उपयोग करके दृढ़ता से अनुशंसा करता हूं।

सोपबॉक्स

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

मैं सम्मान सुझाव है कि आप पर विचार करें:

• आप समय से पहले अनुकूलन करने के लिए कोशिश कर रहे हैं,
• आप थोड़ा लाभ के लिए अनावश्यक जटिलता जोड़ रहे हैं
• की गति और स्मृति प्रबंधन कर रहे हैं सर्वोपरि, तो आप सही उपयोग कर रहे हैं भाषा?

Answer 6

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

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

ओह, वास्तव में आपके सवाल का जवाब देना: नहीं, मैं वहाँ एक खुला स्रोत कार्यान्वयन के बारे में पता नहीं कर रहा हूँ। लेकिन फिर अगर मुझे एक लिंक्ड सूची का अपना स्वाद चाहिए, तो मुझे लगता है कि मैं सिर्फ अपना खुद का रोल करूंगा। संभवतः यदि मानक जावा आपकी आवश्यकताओं को पूरा नहीं करता है, तो इसका मतलब यह होना चाहिए कि आपके पास कुछ विशेष विशेष आवश्यकता है। इस मामले में आपकी विशेष आवश्यकता को पूरा करने के लिए होने वाले ऑफ-द-शेल्फ कार्यान्वयन की खोज बहुत सारी परेशानी की तरह होती है, और आप इसे निश्चित रूप से कार्यान्वित कर सकते हैं, क्या, एक या दो काम? आप शायद एक उपयुक्त उत्पाद की खोज करने में अधिक समय व्यतीत करेंगे, बस इसे करने के लिए। आपने शायद इस पोस्ट के जवाब पढ़ने में अधिक समय बिताया है, इससे आपको इसे लिखने के लिए ले लिया होगा।