समवर्ती रूप से संशोधित ConcurrentSkipListSet

Question

से ट्रीसेट बनाने का अपवाद आम तौर पर, समवर्ती संग्रह फिर से सुरक्षित होते हैं; जावाडोक के मुताबिक: 'इटरेटर कमजोर रूप से सुसंगत हैं, सेटर की स्थिति को प्रतिबिंबित करने वाले तत्वों को किसी बिंदु पर या फिर इटरेटर के निर्माण के बाद दर्शाते हैं। वे ConcurrentModificationException फेंक नहीं देते हैं, और अन्य परिचालनों के साथ एक साथ आगे बढ़ सकते हैं। ' हालांकि, इस पर विचार करें:

import java.util.Random; 
import java.util.TreeSet; 
import java.util.concurrent.ConcurrentSkipListSet; 

public class ConcurrencyProblem { 
    private static volatile boolean modifierIsAlive = true; 

    public static void main(String[] args) { 
     final ConcurrentSkipListSet<Integer> concurrentSet = new ConcurrentSkipListSet<>(); 
     Thread modifier = new Thread() { 
      private final Random randomGenerator = new Random(); 

      public void run() { 

       while (modifierIsAlive) { 
        concurrentSet.add(randomGenerator.nextInt(1000)); 
        concurrentSet.remove(randomGenerator.nextInt(1000)); 
       } 
      }; 
     }; 
     modifier.start(); 
     int sum = 0; 
     while (modifierIsAlive) { 
      try { 
       TreeSet<Integer> sortedCopy = new TreeSet<>(concurrentSet); 
       // make sure the copy operation is not eliminated by the compiler 
       sum += sortedCopy.size(); 
      } catch (RuntimeException rte) { 
       modifierIsAlive = false; 
       rte.printStackTrace(); 
      } 
     } 
     System.out.println("Dummy output: " + sum); 
    } 
} 

उत्पादन

java.util.NoSuchElementException 
at java.util.concurrent.ConcurrentSkipListMap$Iter.advance(ConcurrentSkipListMap.java:2299) 
at java.util.concurrent.ConcurrentSkipListMap$KeyIterator.next(ConcurrentSkipListMap.java:2334) 
at java.util.TreeMap.buildFromSorted(TreeMap.java:2559) 
at java.util.TreeMap.buildFromSorted(TreeMap.java:2547) 
at java.util.TreeMap.buildFromSorted(TreeMap.java:2579) 
at java.util.TreeMap.buildFromSorted(TreeMap.java:2579) 
at java.util.TreeMap.buildFromSorted(TreeMap.java:2579) 
at java.util.TreeMap.buildFromSorted(TreeMap.java:2579) 
at java.util.TreeMap.buildFromSorted(TreeMap.java:2579) 
at java.util.TreeMap.buildFromSorted(TreeMap.java:2579) 
at java.util.TreeMap.buildFromSorted(TreeMap.java:2579) 
at java.util.TreeMap.buildFromSorted(TreeMap.java:2504) 
at java.util.TreeMap.addAllForTreeSet(TreeMap.java:2462) 
at java.util.TreeSet.addAll(TreeSet.java:308) 
at java.util.TreeSet.<init>(TreeSet.java:172) 
at mtbug.ConcurrencyProblem.main(ConcurrencyProblem.java:27) 
Dummy output: 44910 

अगर यह एक बग या एक विशेषता है मैं सोच रहा हूँ है; हमें एक ConcurrentModificationException नहीं मिला, लेकिन फिर भी, पुनरावृत्ति के बारे में ध्यान रखना (सिंक्रनाइज़ किए गए ब्लॉक या अन्यथा वापस गिरना) ConcurrentSkipListSet/Map के उद्देश्य को हरा देता है। मैं जावा 7 और 8 दोनों के साथ इसे पुन: पेश करने में सक्षम हूं (वर्तमान में, मेरे लिनक्स बॉक्स पर 8u72)।

Answer 1

जहां तक ​​मेरा सूत्रों ब्राउज़िंग से समझ सकते हैं, TreeSet के साथ समस्या यह hasNext() कॉल करने के बजाय इसे इस्तेमाल करता है कि यह पुनरावृत्ति से पहले size() कहता है और उसके बाद। यह एक बग हो सकता है, लेकिन मुझे लगता है कि यह लाल-काले पेड़ों का जटिल परिणाम है जो जटिल संरचनाओं को सावधानीपूर्वक संतुलित करने की आवश्यकता है, और इसलिए सृजन के दौरान रैखिक समय में इसे सही तरीके से संतुलित करने के लिए पहले से ही आकार को जानना आवश्यक है।

आप मैन्युअल रूप से पुनरावृत्ति और TreeSet के तत्व जोड़कर इस दरकिनार सकता है, लेकिन इस n log n जटिलता है, जो कारण है कि TreeSet के निर्माता इसे उस तरह से नहीं करता है हो सकता है के लिए नेतृत्व करेंगे (अपनी API कल्पना रैखिक समय की गारंटी देता है)। बेशक यह अभी भी hasNext() पर कॉल कर सकता है क्योंकि यह पेड़ बनाता है, लेकिन फिर पेड़ को पुनर्व्यवस्थित करने के लिए निर्माण समाप्त होने के बाद कुछ अतिरिक्त कार्यों की आवश्यकता हो सकती है, जिससे अमूर्त रैखिक जटिलता हो सकती है। लेकिन लाल-काले पेड़ एक गड़बड़ हैं जैसे वे हैं, और उस तरह की हैक कार्यान्वयन को भी गड़बड़ कर देगा।

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

Answer 2

मैं वास्तव में TreeSet/TreeMap (अद्यतन, it is) में एक बग होने की दिशा में दुबला होना शुरू कर रहा हूं। सर्गेई संकेतों के रूप में यह मुद्दा है कि TreeMap अपने तत्वों को पढ़ने से पहले ConcurrentSkipListSet.size() के परिणाम कैश करता है।

• TreeSet.addAll()
• TreeMap.addAllForTreeSet() कॉल करता है और संग्रह के वर्तमान आकार और संभावित समवर्ती Iterator
• TreeMap.buildFromSorted() जो अंततः Iterator.next()size -times कॉल करने के लिए गुजरता है।

दूसरे शब्दों में, यह Collection मानता है कि इसे पारित किया जाएगा निर्माण के दौरान संशोधित नहीं किया जाएगा, जो एक गलत धारणा है।

ध्यान दें कि buildFromSorted() ने Iterator.hasNext() पर कॉल किया था, उस बिंदु पर इसका एकमात्र विकल्प असफल हो जाएगा, क्योंकि बैकिंग डेटा संरचना को मध्य-निर्माण में संशोधित किया गया था।

अन्य संग्रह को देखते हुए है कि संभावित कुछ मुद्दा हो सकता था ArrayList, LinkedList, और CopyOnWriteArrayList (सबसे अन्य संग्रह मैं बस for-each over the elements को देखा) सहित समवर्ती संरचनाओं, कॉपी करने, स्पष्ट रूप में किसी भी वास्तविक काम करने से पहले एक सरणी के लिए प्रदान संग्रह कॉपी इस सटीक मुद्दे से बचने के लिए आदेश। मुझे लगता है कि TreeSet और TreeMap एक ही काम कर रहे हैं।

हमें वास्तव में इस बग के कारण ओ (एन लॉग एन) प्रदर्शन स्वीकार करने की आवश्यकता नहीं है, लेकिन यह एक हैक होने जा रहा है। हम मूल्यों को केवल सरणी या अन्य डेटा संरचना में कॉपी नहीं कर सकते हैं, क्योंकि TreeSet में डालने से रैखिक समय नहीं होगा। लेकिन हम TreeSet पर झूठ बोल सकते हैं कि प्रतिलिपि SortedSet है।

public static class IterateOnlySortedSet<E> 
    extends AbstractSet<E> implements SortedSet<E> { 
    private final ArrayList<E> elements; 
    private final Comparator<? super E> comparator; 

    public IterateOnlySortedSet(SortedSet<E> source) { 
    elements = new ArrayList<>(source); 
    comparator = source.comparator(); 
    } 

    @Override 
    public Iterator<E> iterator() { 
    return elements.iterator(); 
    } 

    @Override 
    public int size() { 
    return elements.size(); 
    } 

    @Override 
    public Comparator<? super E> comparator() { 
    return comparator; 
    } 

    // remaining methods simply throw UnsupportedOperationException 
} 

करने के लिए अपने TreeSet निर्माण लाइन बदलने:

TreeSet<Integer> sortedCopy = new TreeSet<>(new IterateOnlySortedSet<>(concurrentSet)); 

अब सफल होता है।

अच्छा खोजने :)