giáp, tự động ném bỏ, non-blocking, bộ sưu tập đồng thời

Question

Tôi đang tìm kiếm một bộ sưu tập mà:

• là một Deque/List - tức là hỗ trợ chèn các yếu tố ở "đỉnh" (mục mới nhất đi đến trên cùng) - deque.addFirst(..)/list.add(0, ..). Nó có thể là Queue, nhưng thứ tự lặp lại phải ngược lại - tức là các mục được thêm gần đây nhất sẽ đến trước.
• giáp - tức là có một giới hạn của 20 bản ghi
• tự động loại bỏ các mục lâu đời nhất (những người "ở phía dưới", thêm vào đầu tiên) khi công suất đạt
• non-blocking - nếu deque trống , retrievals không nên chặn. Nó cũng không nên chặn/trả về false/null/throw exception là deque đầy.
• đồng thời - nhiều chủ đề sẽ có thể hoạt động trên nó

tôi có thể mất LinkedBlockingDeque và quấn nó vào bộ sưu tập tùy chỉnh của tôi rằng, trên add hoạt động kiểm tra kích thước và loại bỏ các mục cuối cùng (s). Có lựa chọn nào tốt hơn không?

Answer 1

tôi đã imeplementation đơn giản này:

public class AutoDiscardingDeque<E> extends LinkedBlockingDeque<E> { 

    public AutoDiscardingDeque() { 
     super(); 
    } 

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

    @Override 
    public synchronized boolean offerFirst(E e) { 
     if (remainingCapacity() == 0) { 
      removeLast(); 
     } 
     super.offerFirst(e); 
     return true; 
    } 
} 

Đối với nhu cầu của tôi này cũng đủ, nhưng nó phải là phương pháp tốt như các tài liệu khác với addFirst/offerFirst vẫn sau ngữ nghĩa của một deque chặn.

Answer 2

Tôi tin rằng những gì bạn đang tìm kiếm là một ngăn xếp bị chặn. Không có một lớp thư viện lõi nào thực hiện điều này, vì vậy tôi nghĩ cách tốt nhất để thực hiện việc này là lấy một chồng không đồng bộ (LinkedList) và bọc nó trong một bộ sưu tập được đồng bộ hóa. pop. Một cái gì đó như thế này:

import java.util.Iterator; 
import java.util.LinkedList; 

public class BoundedStack<T> implements Iterable<T> { 
    private final LinkedList<T> ll = new LinkedList<T>(); 
    private final int bound; 

    public BoundedStack(int bound) { 
     this.bound = bound; 
    } 

    public synchronized void push(T item) { 
     ll.push(item); 
     if (ll.size() > bound) { 
      ll.removeLast();     
     } 
    } 

    public synchronized T pop() { 
     return ll.poll(); 
    } 

    public synchronized Iterator<T> iterator() { 
     return ll.iterator(); 
    } 
} 

... thêm phương thức như isEmpty theo yêu cầu, nếu bạn muốn nó thực hiện ví dụ: Danh sách.

Answer 3

Giải pháp đơn giản và cổ điển nhất là bộ đệm vòng bị chặn ghi đè các thành phần cũ nhất.

Việc triển khai khá dễ dàng. Bạn cần một AtomicInteger/Long cho chỉ mục + AtomicReferenceArray và bạn có ngăn xếp mục đích chung miễn phí với 2 phương thức chỉ offer/poll, không có size(). Hầu hết các cấu trúc đồng thời/không khóa đều có những khó khăn w/size(). Ngăn xếp không ghi đè có thể có O (1) nhưng w/phân bổ khi đặt.

cái gì đó dọc theo dòng:

package bestsss.util; 

import java.util.concurrent.atomic.AtomicLong; 
import java.util.concurrent.atomic.AtomicReferenceArray; 

public class ConcurrentArrayStack<E> extends AtomicReferenceArray<E>{ 
    //easy to extend and avoid indirections, 
    //feel free to contain the ConcurrentArrayStack if feel purist 


    final AtomicLong index = new AtomicLong(-1); 

    public ConcurrentArrayStack(int length) { 
     super(length); //returns   
    } 

    /** 
    * @param e the element to offer into the stack 
    * @return the previously evicted element 
    */ 
    public E offer(E e){ 
     for (;;){ 
      long i = index.get(); 
      //get the result, CAS expect before the claim 
      int idx = idx(i+1); 
      E result = get(idx); 

      if (!index.compareAndSet(i, i+1))//claim index spot 
       continue; 

      if (compareAndSet(idx, result, e)){ 
       return result; 
      } 
     } 
    } 

    private int idx(long idx){//can/should use golden ratio to spread the index around and reduce false sharing 
     return (int)(idx%length()); 
    } 

    public E poll(){ 
     for (;;){ 
      long i = index.get(); 
      if (i==-1) 
       return null; 

      int idx = idx(i); 
      E result = get(idx);//get before the claim 

      if (!index.compareAndSet(i, i-1))//claim index spot 
       continue; 

      if (compareAndSet(idx, result, null)){ 
       return result; 
      } 
     } 
    } 
} 

lưu ý cuối: có hoạt động mod là một tốn kém và công suất điện-of-2 là ưa thích, qua &length()-1 (còn bảo vệ vs tràn dài).

Answer 4

Dưới đây là triển khai xử lý đồng thời và không bao giờ trả về Null.

import com.google.common.base.Optional; 

import java.util.Deque; 
import java.util.concurrent.ConcurrentLinkedDeque; 
import java.util.concurrent.locks.ReentrantLock; 

import static com.google.common.base.Preconditions.checkArgument; 
import static com.google.common.base.Preconditions.checkNotNull; 

public class BoundedStack<T> { 
    private final Deque<T> list = new ConcurrentLinkedDeque<>(); 
    private final int maxEntries; 
    private final ReentrantLock lock = new ReentrantLock(); 

    public BoundedStack(final int maxEntries) { 
     checkArgument(maxEntries > 0, "maxEntries must be greater than zero"); 
     this.maxEntries = maxEntries; 
    } 

    public void push(final T item) { 
     checkNotNull(item, "item must not be null"); 

     lock.lock(); 
     try { 
     list.push(item); 
     if (list.size() > maxEntries) { 
      list.removeLast(); 
     } 
     } finally { 
     lock.unlock(); 
     } 
    } 

    public Optional<T> pop() { 
     return Optional.fromNullable(list.poll()); 
    } 

    public Optional<T> peek() { 
     return Optional.fromNullable(list.peekFirst()); 
    } 

    public boolean empty() { 
     return list.isEmpty(); 
    } 
}