समवर्ती सेट कतार

Question

शायद यह एक मूर्ख सवाल है, लेकिन मुझे एक स्पष्ट उत्तर नहीं मिल रहा है।

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

Answer 1

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

public final class ConcurrentHashSet<E> extends ForwardingSet<E> 
    implements Set<E>, Queue<E> { 
    private enum Dummy { VALUE } 

    private final ConcurrentMap<E, Dummy> map; 

    ConcurrentHashSet(ConcurrentMap<E, Dummy> map) { 
    super(map.keySet()); 
    this.map = Preconditions.checkNotNull(map); 
    } 

    @Override public boolean add(E element) { 
    return map.put(element, Dummy.VALUE) == null; 
    } 

    @Override public boolean addAll(Collection<? extends E> newElements) { 
    // just the standard implementation 
    boolean modified = false; 
    for (E element : newElements) { 
     modified |= add(element); 
    } 
    return modified; 
    } 

    @Override public boolean offer(E element) { 
    return add(element); 
    } 

    @Override public E remove() { 
    E polled = poll(); 
    if (polled == null) { 
     throw new NoSuchElementException(); 
    } 
    return polled; 
    } 

    @Override public E poll() { 
    for (E element : this) { 
     // Not convinced that removing via iterator is viable (check this?) 
     if (map.remove(element) != null) { 
     return element; 
     } 
    } 
    return null; 
    } 

    @Override public E element() { 
    return iterator().next(); 
    } 

    @Override public E peek() { 
    Iterator<E> iterator = iterator(); 
    return iterator.hasNext() ? iterator.next() : null; 
    } 
} 

सभी इस दृष्टिकोण के साथ धूप नहीं है। बैकिंग मैप के entrySet().iterator().next() का उपयोग करने के अलावा हमारे पास कोई मुख्य तत्व चुनने का कोई अच्छा तरीका नहीं है, नतीजा यह है कि समय चलने पर नक्शा अधिक से अधिक असंतुलित हो जाता है। यह असंतुलन दोनों बाल्टी टकराव और अधिक सेगमेंट विवाद के कारण एक समस्या है।

नोट: यह कोड कुछ स्थानों पर Guava का उपयोग करता है।

Answer 2

कोई अंतर्निहित संग्रह नहीं है जो ऐसा करता है। कुछ समवर्ती Set कार्यान्वयन हैं जिनका उपयोग एक समवर्ती Queue के साथ किया जा सकता है।

उदाहरण के लिए, सेट में सफलतापूर्वक जोड़े जाने के बाद ही कतार में एक आइटम जोड़ा जाता है, और कतार से हटाई गई प्रत्येक आइटम सेट से हटा दी जाती है। इस मामले में, कतार की सामग्री, तर्कसंगत रूप से, सेट में जो कुछ भी है, और कतार का उपयोग केवल आदेश को ट्रैक करने के लिए किया जाता है और कुशल take() और poll() संचालन केवल BlockingQueue पर पाया जाता है।

Answer 3

ए java.util.concurrent.ConcurrentLinkedQueue आपको वहां से अधिकतर तरीके से प्राप्त करता है।

अपने स्वयं के वर्ग के साथ ConcurrentLinkedQueue लपेटें जो एक जोड़ की विशिष्टता की जांच करता है। आपका कोड थ्रेड सुरक्षित होना चाहिए।

Answer 4

मैं सिंक्रनाइज़ लिंक्ड हैशसेट का उपयोग तब तक करता हूं जब तक विकल्पों पर विचार करने के लिए पर्याप्त औचित्य न हो। प्राथमिक लाभ जो अधिक समवर्ती समाधान प्रदान कर सकता है वह लॉक विभाजन है।

सबसे सरल समवर्ती दृष्टिकोण एक समवर्ती हैश मैप (एक सेट के रूप में कार्य करना) और एक समवर्ती लिंक्ड क्यूयू होगा। संचालन के आदेश वांछित बाधा प्रदान करेगा। एक प्रस्ताव() पहले सीएचएम # putIfAbsent() करेगा और यदि CLQ में सफल डालें। एक मतदान() सीएलक्यू से लिया जाएगा और फिर इसे सीएचएम से हटा देगा। इसका मतलब यह है कि अगर हम मानचित्र में हैं और सीएलक्यू ऑर्डर प्रदान करता है तो हम अपनी कतार में एक प्रविष्टि पर विचार करते हैं। प्रदर्शन को मानचित्र की समवर्तीता को बढ़ाकर समायोजित किया जा सकता है। यदि आप अतिरिक्त रेसी-नेस के प्रति सहिष्णु हैं, तो एक सस्ता सीएचएम # मिलता है() एक उचित पूर्व शर्त के रूप में कार्य कर सकता है (लेकिन यह थोड़ा सा दृश्य होने से पीड़ित हो सकता है)।

Answer 5

सेट अर्थशास्त्र के साथ एक समवर्ती कतार द्वारा आपका क्या मतलब है? यदि आपका मतलब वास्तव में एक समवर्ती संरचना है (जैसा कि थ्रेड-सुरक्षित संरचना के विपरीत) तो मैं दलील दूंगा कि आप एक टट्टू मांग रहे हैं।

उदाहरण के लिए क्या होता है यदि आप put(element) पर कॉल करते हैं और पता लगाते हैं कि कुछ पहले से ही हटा दिया गया है? उदाहरण के लिए, आपके मामले में इसका क्या अर्थ है यदि offer(element) || queue.contains(element)false देता है?

इस तरह की चीजों को अक्सर एक समवर्ती दुनिया में थोड़ा अलग तरीके से सोचना पड़ता है क्योंकि अक्सर ऐसा नहीं लगता है जब तक कि आप दुनिया को रोक नहीं देते (इसे बंद कर दें)। अन्यथा आप आमतौर पर अतीत में कुछ देख रहे हैं। तो, आप वास्तव में क्या करने की कोशिश कर रहे हैं?

Answer 6

शायद ArrayBlockingQueue का विस्तार करें। (पैकेज-एक्सेस) लॉक तक पहुंच प्राप्त करने के लिए, मुझे अपने उप-वर्ग को उसी पैकेज में रखना पड़ा। चेतावनी: मैंने इसका परीक्षण नहीं किया है।

package java.util.concurrent; 

import java.util.Collection; 
import java.util.concurrent.locks.ReentrantLock; 

public class DeDupingBlockingQueue<E> extends ArrayBlockingQueue<E> { 

    public DeDupingBlockingQueue(int capacity) { 
     super(capacity); 
    } 

    public DeDupingBlockingQueue(int capacity, boolean fair) { 
     super(capacity, fair); 
    } 

    public DeDupingBlockingQueue(int capacity, boolean fair, Collection<? extends E> c) { 
     super(capacity, fair, c); 
    } 

    @Override 
    public boolean add(E e) { 
     final ReentrantLock lock = this.lock; 
     lock.lock(); 
     try { 
      if (contains(e)) return false; 
      return super.add(e); 
     } finally { 
      lock.unlock(); 
     } 
    } 

    @Override 
    public boolean offer(E e) { 
     final ReentrantLock lock = this.lock; 
     lock.lock(); 
     try { 
      if (contains(e)) return true; 
      return super.offer(e); 
     } finally { 
      lock.unlock(); 
     } 
    } 

    @Override 
    public void put(E e) throws InterruptedException { 
     final ReentrantLock lock = this.lock; 
     lock.lockInterruptibly(); //Should this be lock.lock() instead? 
     try { 
      if (contains(e)) return; 
      super.put(e); //if it blocks, it does so without holding the lock. 
     } finally { 
      lock.unlock(); 
     } 
    } 

    @Override 
    public boolean offer(E e, long timeout, TimeUnit unit) throws InterruptedException { 
     final ReentrantLock lock = this.lock; 
     lock.lock(); 
     try { 
      if (contains(e)) return true; 
      return super.offer(e, timeout, unit); //if it blocks, it does so without holding the lock. 
     } finally { 
      lock.unlock(); 
     } 
    } 
} 

Answer 7

अद्वितीय वस्तुओं की एक पंक्ति के लिए एक सरल जवाब के रूप में पालन किया जा सकता है:

import java.util.concurrent.ConcurrentLinkedQueue; 

public class FinalQueue { 

    class Bin { 
     private int a; 
     private int b; 

     public Bin(int a, int b) { 
      this.a = a; 
      this.b = b; 
     } 

     @Override 
     public int hashCode() { 
      return a * b; 
     } 

     public String toString() { 
      return a + ":" + b; 
     } 

     @Override 
     public boolean equals(Object obj) { 
      if (this == obj) 
       return true; 
      if (obj == null) 
       return false; 
      if (getClass() != obj.getClass()) 
       return false; 
      Bin other = (Bin) obj; 
      if ((a != other.a) || (b != other.b)) 
       return false; 
      return true; 
     } 
    } 

    private ConcurrentLinkedQueue<Bin> queue; 

    public FinalQueue() { 
     queue = new ConcurrentLinkedQueue<Bin>(); 
    } 

    public synchronized void enqueue(Bin ipAddress) { 
     if (!queue.contains(ipAddress)) 
      queue.add(ipAddress); 
    } 

    public Bin dequeue() { 
     return queue.poll(); 
    } 

    public String toString() { 
     return "" + queue; 
    } 

    /** 
    * @param args 
    */ 
    public static void main(String[] args) { 
     FinalQueue queue = new FinalQueue(); 
     Bin a = queue.new Bin(2,6); 

     queue.enqueue(a); 
     queue.enqueue(queue.new Bin(13, 3)); 
     queue.enqueue(queue.new Bin(13, 3)); 
     queue.enqueue(queue.new Bin(14, 3)); 
     queue.enqueue(queue.new Bin(13, 9)); 
     queue.enqueue(queue.new Bin(18, 3)); 
     queue.enqueue(queue.new Bin(14, 7)); 
     Bin x= queue.dequeue(); 
     System.out.println(x.a); 
     System.out.println(queue.toString()); 
     System.out.println("Dequeue..." + queue.dequeue()); 
     System.out.println("Dequeue..." + queue.dequeue()); 
     System.out.println(queue.toString()); 
    } 
}