Параллельное ArrayList

Question

мне нужен ArrayList-подобную структуру, позволяющую только следующие операции

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

Из итератора используется во многих мест, используя Collections#synchronizedList wo uld слишком подвержен ошибкам. Список может вырасти до нескольких тысяч элементов и будет использоваться много, поэтому я уверен, что CopyOnWriteArrayList будет слишком медленным. Я начну с этого, чтобы избежать преждевременных оптимизаций, но я бы поспорил, что это не сработает.

Большинство доступов будут однопоточными. Поэтому я спрашиваю, какова правильная структура данных для этого.

---

я хоть что обертывание synchronizedList в чем-то обеспечивая синхронизированный итератор будет делать, но он не будет из-за ConcurrentModificationException. Конкретизируя одновременное поведение, я, очевидно, нуждаюсь в том, чтобы все изменения были видны после последующих чтений и итераторов.

Итератору не нужно показывать согласованный снимок, он может или не может видеть обновления через set(int index, E element), так как эта операция используется только для замены элемента своей обновленной версией (содержащей некоторую дополнительную информацию, которая не имеет значения для пользователь итератора). Элементы полностью неизменяемы.

---

Я четко заявил, почему CopyOnWriteArrayList не сделал. ConcurrentLinkedQueue не может быть отказано в индексированном доступе. Мне нужно всего несколько операций, а не полноценный ArrayList. Таким образом, если любой связанный со списком java вопрос является дубликатом this question, этого нет.

Answer 1

В вашем случае вы можете использовать ReadWriteLock для доступа к списку с поддержкой, это позволяет просматривать несколько ваших потоков. Только если один поток нуждается в доступе на запись, все считыватели-Thread должны дождаться завершения операции. это ясно, что JavaDoc сделать в:

ReadWriteLock поддерживает пару связанных замков, один для операции только для чтения, другой для записи. Блокировка чтения может быть проведена одновременно несколькими потоками считывателей, если нет авторов. Блокировка записи является исключительной.

Вот пример:

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(); 
     } 
    }