es.davy.ai

Preguntas y respuestas de programación confiables

¿Tienes una pregunta?

Si tienes alguna pregunta, puedes hacerla a continuación o ingresar lo que estás buscando.

Obteniendo elementos aleatorios de una lista mientras otro hilo la está modificando

31 Jul, 2023 Programación

Estoy tratando de crear una estructura de datos concurrente que permita a un hilo buscar elementos aleatorios mientras otro hilo está escribiendo en ella.

public class SomeList<e> extends CopyOnWriteArrayList<e> {
    private final Random random = new Random();

    public E pollRandom() {
        if (size() == 0) {
            throw new NoSuchElementException();
        }
        return remove(random.nextInt(size()));
    }
}

Mi preocupación es: en un caso extremo, por ejemplo, después de que el hilo A llama a size() (en pollRandom()), el hilo B elimina el último elemento. Desafortunadamente, el índice aleatorio resulta ser el índice del último elemento (que ya ha sido eliminado). Por lo tanto, la llamada a remove() lanzará una excepción IndexOutOfBoundsException no detectada. Esto es lo que no espero: una llamada a pollRandom() falló, aunque aún hay elementos en esta lista.

Por lo tanto, me gustaría preguntar: ¿Mi preocupación es real? ¿Quizás comprendo mal qué hace realmente un CopyOnWriteArrayList (u otro tipo de lista concurrente)? Si mi preocupación es real, ¿hay alguna forma de resolver el problema? No quiero agregar synchronized a todos los métodos, ya que eso empeora mucho el rendimiento.

Agradecería si alguien quisiera responder la pregunta. Mi inglés está lejos de ser bueno, si mi expresión suena vaga o impolite, por favor avíseme, gracias 🙂

PD: Soy consciente de que CopyOnWriteArrayList es lento para todas las operaciones mutativas, ya que requiere una copia completa cada vez, gracias a @Boris the Spider. Puede ser cualquier tipo de lista concurrente. Aquí solo hay un ejemplo.

Tags:  , , ,

Answer

  1. Avatar for davy.ai
    davy.ai

    Tu preocupación es real. En un entorno concurrente, es posible que un hilo inicie una operación basada en un estado particular de la estructura de datos y luego otro hilo modifique ese estado antes de que la operación esté completa. En el caso de pollRandom(), esto podría resultar en una IndexOutOfBoundsException como describiste.

    CopyOnWriteArrayList crea una nueva copia de toda la lista cada vez que se modifica, lo que significa que las lecturas pueden ocurrir de manera concurrente con las escrituras sin necesidad de sincronización. Sin embargo, esto no garantiza que las lecturas verán el estado más actualizado de la lista. En otras palabras, si una escritura ocurre después de que una lectura ya haya comenzado, la lectura puede no ver los efectos de la escritura.

    Para resolver el problema que describiste, podrías usar un ReadWriteLock para proteger el acceso a la lista. Esto permitiría que múltiples hilos lean de la lista al mismo tiempo, al tiempo que garantiza que solo un hilo pueda escribir en ella a la vez. Aquí tienes un ejemplo de implementación:

    public class SomeList<e> {
    private final List<e> list = new ArrayList<>();
    private final Random random = new Random();
    private final ReadWriteLock lock = new ReentrantReadWriteLock();

    public void add(E element) {
        lock.writeLock().lock();
        try {
            list.add(element);
        } finally {
            lock.writeLock().unlock();
        }
    }

    public E pollRandom() {
        lock.readLock().lock();
        try {
            if (list.isEmpty()) {
                throw new NoSuchElementException();
            }
            return list.remove(random.nextInt(list.size()));
        } finally {
            lock.readLock().unlock();
        }
    }
}

    En esta implementación, add() utiliza el bloqueo de escritura para proteger el acceso a la lista mientras agrega un elemento. pollRandom() utiliza el bloqueo de lectura para proteger el acceso mientras elimina un elemento aleatorio de la lista. Esto garantiza que las escrituras y lecturas no puedan ocurrir al mismo tiempo, evitando la condición de carrera que describiste.

Comments are closed.