Tengo una estructura de datos, digamos un MinHeap. Tiene métodos como peek (), removeElement () y addElement (). removeElement() y addElement() pueden producir estados inconsistentes si no se hacen seguros para subprocesos (porque implican aumentar / disminuir el tamaño actual del tamaño de pila).
Ahora, quiero implementar esta estructura de datos, la forma funcional. He leído que en la programación funcional la inmutabilidad es la clave que conduce a la seguridad del hilo. ¿Cómo implemento eso aquí? ¿Debo evitar aumentar / disminuir el tamaño actual de HeapSize? ¿Si es así, cómo? Me gustaría alguna dirección con esto.


Editar # 1

@YuvalItzchakov y @Dima han señalado que debo devolver una nueva colección cada vez que hago una inserción / eliminación, lo cual tiene sentido. ¿Pero eso no obstaculizaría el desempeño de manera crítica? Mi caso de uso es que obtendré un flujo de datos y lo seguiré agregando al montón. Cuando alguien solicita datos, se devuelve la raíz del montón mínimo. Entonces aquí la inserción ocurre muy rápidamente. ¿No sería costoso crear un nuevo montón para cada inserción? Creo que si. Si es así, ¿cómo ayuda realmente la programación funcional? ¿Es solo un concepto teórico o tiene implicaciones prácticas también?

0
Ashwin 10 sep. 2018 a las 13:25

3 respuestas

La mejor respuesta

El problema del acceso paralelo a la misma estructura de datos es doble. Primero, necesitamos serializar actualizaciones paralelas. @Tim dio una respuesta integral a esto. En segundo lugar, en el caso de que haya muchos lectores, es posible que deseemos que lean en paralelo con la escritura. Y en este caso la inmutabilidad juega su papel. Sin ella, los escritores tienen que esperar a que los lectores terminen.

1
Alexei Kaigorodov 10 sep. 2018 a las 16:21

Puedes usar gatos Ref type class https://typelevel.org/cats-effect/concurrency/ref.html Pero es esa realización de referencia atómica, o escribir algún contenedor java.util.concurent.ConcurentHashMap

0
Mikhail Nemenko 13 sep. 2018 a las 20:29

Realmente no hay una forma "funcional" de tener una estructura de datos que pueda ser actualizada por múltiples hilos. De hecho, una razón por la que la programación funcional es tan buena en un entorno multiproceso es porque no hay estructuras de datos compartidas como esta.

Sin embargo, en el mundo real, este problema surge todo el tiempo, por lo que necesita alguna forma de serializar el acceso a la estructura de datos compartidos. La forma más cruda es simplemente colocar un gran candado alrededor del código completo y solo permitir que se ejecute un hilo a la vez (por ejemplo, con un Mutex). Con un diseño inteligente, esto puede hacerse razonablemente eficiente, pero puede ser difícil hacerlo bien y mantenerlo.

Un enfoque más sofisticado es tener una cola de solicitudes segura para subprocesos a su estructura de datos y un único subproceso de trabajo que procese estas solicitudes una por una. Un marco popular que admite este modelo es Akka Actors. Envuelve su estructura de datos en un Actor que luego recibe solicitudes para leer o modificar la estructura de datos. El marco de trabajo de Akka asegurará que solo se procese un mensaje a la vez.

En su caso, su actor administraría el montón y recibiría actualizaciones de la secuencia que iría al montón. Otros subprocesos pueden hacer solicitudes que serán procesos de una manera secuencial y segura para subprocesos. Es mejor si estas solicitudes realizan consultas específicas en el montón, en lugar de simplemente devolver todo el montón cada vez.

1
Tim 10 sep. 2018 a las 12:22