सीधे सुलभ डेटा संरचना जावा

Question

मैं निम्नलिखित स्थिति है:

1. एक डेटा संरचना है जो केवल कभी बढ़ाया जा सकता है (मैं ही कभी पूंछ में चीजों को जोड़ने)
2. मैं रखने के लिए सक्षम होना चाहिए ट्रैक करें कि मेरे पास पहले से देखा गया है (मेरे पास एक इंडेक्स है, और आदर्श रूप से मैं इस विशेष तत्व से सूची को फिर से घुमाने में सक्षम होना चाहता हूं)
3. मैं पढ़ना चाहता हूं कि कभी भी अवरुद्ध न हो और अतिरिक्त का नया तत्व केवल कभी भी लो की कतार की पूंछ पूरी कतार

यह एक संरचना है जिसे कई धागे द्वारा भारी रूप से संशोधित किया जाता है।

इसके लिए सबसे अच्छी डेटा संरचना क्या होगी?

ArrayList। इंडेक्स का उपयोग करके देखे गए अंतिम तत्व को सीधे एक्सेस करने में सक्षम होने के लिए यह आदर्श होगा, लेकिन यह समवर्ती संशोधन अपवादों की ओर जाता है। (के रूप में यह केवल एक ही जहां नए तत्वों को जोड़ने के समवर्ती राईट हो सकता है या किसी बहुत पिछले तत्व से अलग ताला लगा,) मैं इसे सिंक्रनाइज़ कर सकता है, लेकिन ताला लगा से बचने के लिए चाहते हैं

ConcurrentLinkedQueue। यह मेरी समवर्ती समस्या को हल करेगा, लेकिन समस्या है कि मुझे एक पूर्णांक सूचकांक की बजाय पुनरावृत्ति की वर्तमान स्थिति को स्टोर करना होगा। कुंजी के रूप में सूचकांक के साथ

ConcurrentHashMap: इस समस्या यह है कि यह एक कमजोर संगत iterator जो नई वस्तुओं है कि सूची में जोड़ा गया है के बाद से इटरेटर (जावाडोक स्रोत) बनाया गया था वापस करने के लिए गारंटी नहीं है देता है। इसका लाभ यह है कि मैं सीधे सही इंडेक्स से संबंधित डेटा तक पहुंच सकता हूं, लेकिन यह मुद्दा है कि "getNext" ऑपरेटर नहीं है जो मुझे इंडेक्स से सूचकांक, सूचकांक + 1, आदि

पर कुशलता से पार करने की अनुमति देगा

वेक्टर यह कुछ ऐसी समस्याओं को हल करने में मेरी समस्याओं का समाधान करेगा जो समवर्ती संशोधन अपवाद फेंक नहीं देंगे और सीधे पहुंच के लिए अनुमति देंगे। हालांकि, सभी विधियों को सिंक्रनाइज़ किया गया है, प्रदर्शन सरणीसूची की तुलना में खराब है। यह देखते हुए कि मैं केवल संरचना का विस्तार करना चाहता हूं, और बीच में रिकॉर्ड सम्मिलित नहीं करना चाहता, मैं इस भारी वजन समाधान के लिए जाने के लिए अनिच्छुक हूं, जहां पढ़ना भी एक प्रदर्शन हिट का सामना करना पड़ता है (जबकि, मेरे उपयोगकेस को देखते हुए, तत्व की अनुक्रमणिका वास्तव में कभी बदलता है, तो सिंक्रनाइज़ करने के लिए पढ़ता है कि पूंछ नहीं हैं)

कस्टम डेटा संरचना कोई आवश्यकता नहीं है: इस सरणी की पूंछ (पिछले तत्व के लिए वस्तुओं मैं संग्रहीत करना चाहते हैं की एक सरणी और एक सूचक रखने सेट करें), जब कोई नई ऑब्जेक्ट डालें, पूंछ को इंगित करें पूंछ और ऑब्जेक्ट को पूंछ से इंगित करें। जब ऑब्जेक्ट लॉकिंग आकार बदलने के लिए, अपने वर्तमान आकार से अधिक हो जाता है।

सबसे अच्छी रणनीति/कोई और अधिक कुशल कार्यान्वयन क्या होगा?

Answer 1

CopyOnWriteArrayList संरचना आपकी समस्या (java.util.concurrent) को हल कर सकती है।

• CopyOnWriteArrayList रों धागा सुरक्षित है क्योंकि सभी mutative संचालन सूची की एक प्रति बनाकर लागू किया जाता है है।

• ConcurrentModificationException की समस्या से बचा जाता है क्योंकि सरणी फिर से परिवर्तित नहीं होती है। तथाकथित snapshot style iterator इटरेटर बनाया गया था जब सरणी की स्थिति के संदर्भ का उपयोग करता है।

• यदि आपके पास लिखने से कहीं अधिक पढ़ा गया है, तो CopyOnWriteArrayList का उपयोग करें, अन्यथा Vector का उपयोग करें।

• Vector प्रत्येक ऑपरेशन के लिए एक छोटी सिंक्रनाइज़ेशन देरी पेश करता है, जब CopyOnWriteArrayList लिखने के लिए अधिक देरी होती है (प्रतिलिपि के कारण) लेकिन पढ़ने के लिए कोई देरी नहीं होती है।

• Vector जब आप इसे पुन: सक्रिय कर रहे हैं तो स्पष्ट सिंक्रनाइज़ेशन की आवश्यकता होती है (इसलिए लिखना संचालन एक ही समय में निष्पादित नहीं किया जा सकता है), CopyOnWriteArrayList नहीं है।

Answer 2

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

(के रूप में यह केवल एक ही जहां नए तत्वों को जोड़ने के समवर्ती राईट हो सकता है या किसी बहुत पिछले तत्व से अलग ताला लगा,) मैं इसे सिंक्रनाइज़ कर सकता है, लेकिन ताला लगा से बचने के लिए चाहते हैं ऑब्जेक्ट को जोड़ने के लिए अस्थायी सूची और जब पढ़ने की चीज़ अनब्लॉक होती है, तो आप ArrayList को tmpList की सामग्री जोड़ते हैं।

Answer 3

sk2212 ने कहा, मुझे लगता है कि java.util.Vector आपके तीन अंकों को पूरा करता है।

1. वेक्टर विधि add, जो सूची के अंत में तत्वों कहते हैं का उपयोग करके बढ़ाया जा सकता है।
2. विशिष्ट सूचकांक पर एक ठोस तत्व पुनर्प्राप्त करने के लिए वेक्टर के पास get(index) विधि है। java Vector and thread safetyhttp://docs.oracle.com/javase/7/docs/api/java/util/Vector.html

Answer 4

यह आप की तरह बहुत ज्यादा लगता है एक distruptor या सरल शब्दों में बंद कर मुक्त कतार की आवश्यकता होगी:

वेक्टर धागा सुरक्षित हैं। काश मैं यहां एक उदाहरण जोड़ सकता हूं, लेकिन मैंने कल ही काम करना शुरू कर दिया था। मैं आपको यह भी बता सकता हूं कि यह कैसे काम करता है, या आप यहां एक बेहतर बेहतर स्पष्टीकरण पढ़ सकते हैं:

सामान्य विचार यह है कि यह पूरी तरह से मुक्त है, यह केवल सीएएस रजिस्ट्रार (जावा परमाणु XXX में) का उपयोग करता है। मैं बस इस विचार से प्यार में गिर गया।

LMAX

Answer 5

सूचकांक कुंजी आपकी समस्या का समाधान हो सकता है के रूप में है, लेकिन आप ऐसा करने के लिए litte अधिक काम करने की जरूरत है साथ ConcurrentHashMap ..

छद्म संहिता निम्नलिखित की तरह।

Map<Integer , ConfiguredObject > myMap = new ConcurrentHashMap<Integer,ConfiguredObject >(); 

class ConfiguredObject 
{ 
    YourObject Object;// the object which you want to map for map[key]; 
    ConfiguredObject Next;//the object which you want to map for map[key+1]; 
    ConfiguredObject Previous;//the object which you want to map for map[key-1]; 
    YourObject NextObject; 
    YourObject PrevObject; 
} 

तो यह आपकी सभी समस्याओं को हल करना चाहिए।

Concurrency फ्रेमवर्क परवाह है।

इंडेक्सिंग कुंजी आपकी अनुक्रमणिका हैं।

पुनरावृत्ति, इस कोड के साथ अगर आप सूचकांक आप

myMap.get(key).Next ; 
myMap.get(key).Previous ; 

उपयोग कर सकते हैं आपको बस इतना करना की जरूरत विन्यास वस्तु को परिभाषित करने और देखभाल के साथ तदनुसार निर्माता बारे में है।

आशा है कि यह आपकी मदद करेगा।

Answer 6

मैं, ConcurrentSkipListSet तक की पेशकश करने जा रहा हूँ क्योंकि:

1) यह समवर्ती है।

2) यह Set है।

3) यह भी NavigableSet है, इस प्रकार SortedSet भी है।

यह आपको बहुत लचीलापन देता है, जिनमें से अधिकतर आपको शायद इसकी आवश्यकता नहीं होगी। लेकिन "आप पहले से मौजूद वस्तुओं को जोड़ नहीं सकते हैं" (जो मुझे नहीं पता कि कोई समस्या है या वरदान है) ऐसा लगता है कि यह आपकी सभी आवश्यकताओं को पूरा करता है।

Answer 7

इसमें देखकर मैं @MissingNumber के समान समाधान में आया था।

समर्थन डेटा संरचना के रूप में एक ConcurrentHashMap का उपयोग करें:

• गैर अवरुद्ध-पढ़ता
• धागा सुरक्षित

सूचकांक द्वारा रैंडम एक्सेस को जोड़ने के लिए एक AtomicInteger का उपयोग सूचकांक बनाए रखने के लिए जोड़कर और इसे मानचित्र मानों को पुनर्प्राप्त करने के लिए कुंजी के रूप में रखें।

public class ConcurrentListMap { 

    private final ConcurrentHashMap<Integer, Object> backingMap; 
    private final AtomicInteger index; 

    public ConcurrentListMap() { 
    backingMap = new ConcurrentHashMap(); 
    index = new AtomicInteger(0); 
    } 

    public int append(final Object value) { 
    final int newIndex = index.incrementAndGet(); 
    backingMap.put(newIndex, value); 
    return newIndex; 
    } 

    public Object get(final int entry) { 
    return backingMap.get(entry); 
    } 

    public int getTailIndex() { 
    return index.get(); 
    } 
} 

Answer 8

क्या आपको एक डेटा संरचना का उपयोग करना है? क्या होगा यदि आपने सूची के "सक्रिय" हिस्से के लिए दो और एक "आपके द्वारा देखी गई वस्तुओं" सूची के लिए दो का उपयोग किया था? आप "सक्रिय" भाग और किसी प्रकार के प्रबंधक के लिए वेक्टर का उपयोग कर सकते हैं जो समय-समय पर आइटम को "आपके द्वारा देखी गई वस्तुओं" सूची में ले जाता है।