współbieżne ArrayList

Question

potrzebne struktury ArrayList jak pozwalając tylko następujące operacje

• get(int index)
• add(E element)
• set(int index, E element)
• iterator()

ze względu na iteracyjnej wykorzystywane w wielu miejsc, używając Collections#synchronizedList wo być podatnym na błędy. Lista może rozwinąć się do kilku tysięcy elementów i wiele się jej używa, więc jestem prawie pewna, że ​​CopyOnWriteArrayList będzie zbyt wolny. Zacznę od tego, aby uniknąć przedwczesnych optymalizacji, ale założę się, że to nie zadziała.

Najczęściej dostępnymi odczytami są jednowątkowe. Pytam więc, jaka jest właściwa struktura danych.

---

I mimo że owijanie synchronizedList w coś zapewniając zsynchronizowane iterator zrobi, ale nie ze względu na ConcurrentModificationException. Koncentrując się na współbieżnym zachowaniu, oczywiście potrzebuję, aby wszystkie zmiany były widoczne po kolejnych odczytach i iteratorach.

Iterator nie musi wyświetlać spójnej migawki, może aktualizować się lub nie przez set(int index, E element), ponieważ ta operacja zostanie użyta tylko w celu zastąpienia elementu jego zaktualizowaną wersją (zawierającą pewne dodatkowe informacje, które są nieistotne dla użytkownik iteratora). Przedmioty są w pełni niezmienne.

---

Wyjaśniłem wyraźnie, dlaczego nie zrobiłoby to CopyOnWriteArrayList. ConcurrentLinkedQueue nie wchodzi w grę, ponieważ nie ma dostępu indeksowanego. Potrzebuję tylko kilku operacji, a nie pełnowartościowego ArrayList. Tak więc, chyba że każde pytanie związane z listą równoległą do java o numerze jest duplikatem this question, to nie jest.

Answer 1

W twoim przypadku możesz użyć ReadWriteLock, aby uzyskać dostęp do listy kopii, co pozwala wielu wątkom na odczytanie listy. Tylko jeśli jeden wątek wymaga dostępu do zapisu, cały czytnik - wątek musi czekać na zakończenie operacji. Javadoc sprawiają za to jasne:

ReadWriteLock utrzymuje parę stowarzyszonych zamków, jeden dla operacji tylko do odczytu i jeden na piśmie. Blokada odczytu może być przechowywana jednocześnie przez wiele wątków czytnika, o ile nie ma pisarzy . Blokada zapisu jest wyjątkowa.

Oto przykład:

public class ConcurrentArrayList<T> { 

    /** use this to lock for write operations like add/remove */ 
    private final Lock readLock; 
    /** use this to lock for read operations like get/iterator/contains.. */ 
    private final Lock writeLock; 
    /** the underlying list*/ 
    private final List<T> list = new ArrayList(); 

    { 
     ReentrantReadWriteLock rwLock = new ReentrantReadWriteLock(); 
     readLock = rwLock.readLock(); 
     writeLock = rwLock.writeLock(); 
    } 

    public void add(T e){ 
     writeLock.lock(); 
     try{ 
      list.add(e); 
     }finally{ 
      writeLock.unlock(); 
     } 
    } 

    public void get(int index){ 
     readLock.lock(); 
     try{ 
      list.get(index); 
     }finally{ 
      readLock.unlock(); 
     } 
    } 

    public Iterator<T> iterator(){ 
     readLock.lock(); 
     try { 
      return new ArrayList<T>(list).iterator(); 
        //^ we iterate over an snapshot of our list 
     } finally{ 
      readLock.unlock(); 
     } 
    }