Wybór najlepszej listy współbieżności w Javie [zamknięte]

Question 1

Moja pula wątków ma stałą liczbę wątków. Wątki te muszą często pisać i czytać z udostępnionej listy.

Jaka więc struktura danych (lepiej lista, musi być wolna od monitora) w java.util.concurrentpakiecie jest najlepsza w tym przypadku?

Question 2

lepiej by było List

Tylko List realizacja w java.util.concurrentto CopyOnWriteArrayList . Istnieje również opcja zsynchronizowanej listy, o której wspomina Travis Webb.

To powiedziawszy, czy na pewno potrzebujesz, aby to był List? Istnieje o wiele więcej opcji dla współbieżnych Queues i Maps (i można utworzyć Sets z Maps), a te struktury mają zwykle największy sens w przypadku wielu rodzajów rzeczy, które chcesz zrobić ze wspólną strukturą danych.

W przypadku kolejek masz ogromną liczbę opcji i to, która z nich jest najbardziej odpowiednia, zależy od tego, jak chcesz z niej skorzystać:

Question 3

Dowolną kolekcję Java można ustawić jako bezpieczną dla wątków, na przykład:

List newList = Collections.synchronizedList(oldList);

Lub utworzyć zupełnie nową listę bezpiecznych wątków:

List newList = Collections.synchronizedList(new ArrayList());

http://download.oracle.com/javase/6/docs/api/java/util/Collections.html#synchronizedList(java.util.List)

Question 4

Jeśli rozmiar listy został ustalony, możesz użyć AtomicReferenceArray . Umożliwiłoby to wykonanie indeksowanych aktualizacji slotu. W razie potrzeby możesz napisać widok listy.

Question 5

Możesz spojrzeć na ConcurrentDoublyLinkedList napisaną przez Douga Leę na podstawie „Praktycznej listy podwójnie połączonej bez blokad” Paula Martina. Nie implementuje interfejsu java.util.List, ale oferuje większość metod, których można użyć na liście.

Według javadoc:

Współbieżna implementacja listy połączonej Deque (kolejka dwustronna). Jednoczesne operacje wstawiania, usuwania i uzyskiwania dostępu są bezpiecznie wykonywane w wielu wątkach. Iteratory są słabo spójne , zwracając elementy odzwierciedlające stan deque w pewnym momencie lub od chwili utworzenia iteratora. Oni nie rzucać ConcurrentModificationException i może postępować równolegle z innymi operacjami.

Question 6

ConcurrentLinkedQueueużywa kolejki bez blokady (opartej na nowszej instrukcji CAS ).

Question 7

Jeśli set jest wystarczający, można użyć ConcurrentSkipListSet . (Jego implementacja jest oparta na ConcurrentSkipListMap, która implementuje listę pominięć ).

Oczekiwany średni koszt czasu to log (n) dla operacji zawierania, dodawania i usuwania; metoda rozmiaru nie jest operacją działającą w czasie stałym.

Answer 1 · 2018-11-21 01: 35: 14Z

98

Moja pula wątków ma stałą liczbę wątków. Wątki te muszą często pisać i czytać z udostępnionej listy.

Jaka więc struktura danych (lepiej lista, musi być wolna od monitora) w java.util.concurrentpakiecie jest najlepsza w tym przypadku?

java concurrency 象嘉道
źródło

5

To zależy, co chcesz zrobić z kolekcją. Zobacz mój wpis na blogu (chociaż dotyczy .Net, koncepcje są takie same). Jest mało prawdopodobne, abyś był w stanie napisać poprawny kod bezpieczny dla wątków z rozszerzeniem List.

SLaks

1

Teraz używam CopyOnWriteArrayList , ale wyjątek ConcurrentModificationException jest nadal czasami generowany .

象嘉道

2

Podaj więcej informacji o tym, co robisz z kolekcją, aby użytkownicy mogli lepiej odpowiedzieć, w przeciwnym razie to tylko przypuszczenie.

mattsh

2

ConcurrentModificationExceptionMoże nie pochodzić z problemem synchronizacji; pojawia się również na przykład w pętli for nad kolekcją, w której próbujesz usunąć element z kolekcji.

toto2

1

Wiem, że to nie jest część pakietu, ale czy ktoś próbował Vector?

WesternGun

Answer 2

5

To zależy, co chcesz zrobić z kolekcją. Zobacz mój wpis na blogu (chociaż dotyczy .Net, koncepcje są takie same). Jest mało prawdopodobne, abyś był w stanie napisać poprawny kod bezpieczny dla wątków z rozszerzeniem List.

SLaks

Answer 3

1

Teraz używam CopyOnWriteArrayList , ale wyjątek ConcurrentModificationException jest nadal czasami generowany .

象嘉道

Answer 4

2

Podaj więcej informacji o tym, co robisz z kolekcją, aby użytkownicy mogli lepiej odpowiedzieć, w przeciwnym razie to tylko przypuszczenie.

mattsh

Answer 5

2

ConcurrentModificationExceptionMoże nie pochodzić z problemem synchronizacji; pojawia się również na przykład w pętli for nad kolekcją, w której próbujesz usunąć element z kolekcji.

toto2

Answer 6

1

Wiem, że to nie jest część pakietu, ale czy ktoś próbował Vector?

WesternGun

Answer 7

lepiej by było List

Tylko List realizacja w java.util.concurrentto CopyOnWriteArrayList . Istnieje również opcja zsynchronizowanej listy, o której wspomina Travis Webb.

To powiedziawszy, czy na pewno potrzebujesz, aby to był List? Istnieje o wiele więcej opcji dla współbieżnych Queues i Maps (i można utworzyć Sets z Maps), a te struktury mają zwykle największy sens w przypadku wielu rodzajów rzeczy, które chcesz zrobić ze wspólną strukturą danych.

W przypadku kolejek masz ogromną liczbę opcji i to, która z nich jest najbardziej odpowiednia, zależy od tego, jak chcesz z niej skorzystać:

Answer 8

14

CopyOnWriteArrayListma tę wadę, że jest bardzo kosztowny przy zapisie (ale tani jak na odczyt). Jeśli robisz dużo zapisów, lepiej będzie mieć zsynchronizowaną listę lub kolejkę.

Peter Lawrey,

Answer 9

69

Dowolną kolekcję Java można ustawić jako bezpieczną dla wątków, na przykład:

List newList = Collections.synchronizedList(oldList);

Lub utworzyć zupełnie nową listę bezpiecznych wątków:

List newList = Collections.synchronizedList(new ArrayList());

http://download.oracle.com/javase/6/docs/api/java/util/Collections.html#synchronizedList(java.util.List)

Travis Webb
źródło

7

Z tego powodu nie znajdziesz implementacji list w java.util.concurrent - Uhm, jest ConcurrentHashMapchociaż Collections.synchronizedMapmetoda.

aioobe

7

Przeczytaj Javadocs dalej ConcurrentHashMap. Szczegóły implementacji synchronizacji są różne. używanie tych synchronizedmetod w Collectionszasadzie po prostu opakowuje klasę w monitorze Java. ConcurrentHashMapwykorzystuje bardziej inteligentne funkcje współbieżności.

Travis Webb

1

Tak. Mimo to sprawia, że twoje ostatnie zdanie jest trochę nieważne.

aioobe

1

Jeśli używasz monitora, wydajność programu jest naprawdę zła :-(

象嘉道

5

Dodam, że iteracja po newList nie jest bezpieczna wątkowo. !!

bluelurker

Answer 10

7

Z tego powodu nie znajdziesz implementacji list w java.util.concurrent - Uhm, jest ConcurrentHashMapchociaż Collections.synchronizedMapmetoda.

aioobe

Answer 11

7

Przeczytaj Javadocs dalej ConcurrentHashMap. Szczegóły implementacji synchronizacji są różne. używanie tych synchronizedmetod w Collectionszasadzie po prostu opakowuje klasę w monitorze Java. ConcurrentHashMapwykorzystuje bardziej inteligentne funkcje współbieżności.

Travis Webb

Answer 12

1

Tak. Mimo to sprawia, że twoje ostatnie zdanie jest trochę nieważne.

aioobe

Answer 13

1

Jeśli używasz monitora, wydajność programu jest naprawdę zła :-(

象嘉道

Answer 14

5

Dodam, że iteracja po newList nie jest bezpieczna wątkowo. !!

bluelurker

Answer 15

Jeśli rozmiar listy został ustalony, możesz użyć AtomicReferenceArray . Umożliwiłoby to wykonanie indeksowanych aktualizacji slotu. W razie potrzeby możesz napisać widok listy.

Answer 16

Możesz spojrzeć na ConcurrentDoublyLinkedList napisaną przez Douga Leę na podstawie „Praktycznej listy podwójnie połączonej bez blokad” Paula Martina. Nie implementuje interfejsu java.util.List, ale oferuje większość metod, których można użyć na liście.

Według javadoc:

Współbieżna implementacja listy połączonej Deque (kolejka dwustronna). Jednoczesne operacje wstawiania, usuwania i uzyskiwania dostępu są bezpiecznie wykonywane w wielu wątkach. Iteratory są słabo spójne , zwracając elementy odzwierciedlające stan deque w pewnym momencie lub od chwili utworzenia iteratora. Oni nie rzucać ConcurrentModificationException i może postępować równolegle z innymi operacjami.

Answer 17

5

ConcurrentLinkedQueueużywa kolejki bez blokady (opartej na nowszej instrukcji CAS ).

eSniff
źródło

7

... który nie implementuje Listinterfejsu.

aioobe

1

eSniff, jak zabrałbyś się za wdrożenie List.set(int index, Object element)z ConcurrentLinkedQueue?

John Vint,

4

Większość Listmetod specyficznych albo nie będzie możliwa do zaimplementowania przy użyciu Queue(na przykład dodawania / ustawiania w określonym indeksie) lub może zostać zaimplementowana, ale będzie nieefektywna (pobierz z indeksu). Więc nie sądzę, żebyś naprawdę mógł to opakować. To powiedziawszy, myślę, że sugestia a Queuejest w porządku, ponieważ OP tak naprawdę nie wyjaśnił, dlaczego potrzebują List.

ColinD,

1

@ColinD to odpowiedź, do której dążyłem. Istnieją dobre powody, dla których CLQ nie może zostać umieszczony na liście. Chociaż zgadzam się, nie mogę wykluczyć interfejsu kolejki.

John Vint,

1

❗️ Warto zauważyć, że: „Uważaj, w przeciwieństwie do większości kolekcji metoda size NIE jest operacją działającą w czasie stałym. Ze względu na asynchroniczny charakter tych kolejek, określenie bieżącej liczby elementów wymaga przejścia przez elementy”.

Behrang Saeedzadeh

Answer 18

7

... który nie implementuje Listinterfejsu.

aioobe

Answer 19

1

eSniff, jak zabrałbyś się za wdrożenie List.set(int index, Object element)z ConcurrentLinkedQueue?

John Vint,

Answer 20

4

Większość Listmetod specyficznych albo nie będzie możliwa do zaimplementowania przy użyciu Queue(na przykład dodawania / ustawiania w określonym indeksie) lub może zostać zaimplementowana, ale będzie nieefektywna (pobierz z indeksu). Więc nie sądzę, żebyś naprawdę mógł to opakować. To powiedziawszy, myślę, że sugestia a Queuejest w porządku, ponieważ OP tak naprawdę nie wyjaśnił, dlaczego potrzebują List.

ColinD,

Answer 21

1

@ColinD to odpowiedź, do której dążyłem. Istnieją dobre powody, dla których CLQ nie może zostać umieszczony na liście. Chociaż zgadzam się, nie mogę wykluczyć interfejsu kolejki.

John Vint,

Answer 22

1

❗️ Warto zauważyć, że: „Uważaj, w przeciwieństwie do większości kolekcji metoda size NIE jest operacją działającą w czasie stałym. Ze względu na asynchroniczny charakter tych kolejek, określenie bieżącej liczby elementów wymaga przejścia przez elementy”.

Behrang Saeedzadeh

Answer 23

Jeśli set jest wystarczający, można użyć ConcurrentSkipListSet . (Jego implementacja jest oparta na ConcurrentSkipListMap, która implementuje listę pominięć ).

Oczekiwany średni koszt czasu to log (n) dla operacji zawierania, dodawania i usuwania; metoda rozmiaru nie jest operacją działającą w czasie stałym.

Wybór najlepszej listy współbieżności w Javie [zamknięte]

Odpowiedzi: