¿Cuál es la estructura de datos OCaml estándar con la iteración más rápida?

Question

Estoy buscando un contenedor que proporciona iteraciones desordenadas más rápidas a través de los elementos encapsulados. En otras palabras, "agregar una vez, iterar muchas veces".

¿Hay alguno entre los módulos estándar de OCaml que sea lo suficientemente rápido (de modo que su posterior optimización sería inútil)? ¿O algún tipo de terceros preparados para GPL?

yo sepa sólo hay un compilador de OCaml, por lo que el concepto de ser es más o menos clara rápido ...

... Pero después vi un par de respuestas, parece, no lo es. Por supuesto, hay muchas estructuras de datos que permiten la iteración O (n) a través del contenedor de tamaño n. Pero la tarea que estoy resolviendo es una de ellas, donde importa la diferencia entre O (n) y O (2n) ;-).

También veo que matrices y listas proporcionan información innecesaria sobre el orden de los elementos añadidos, que no es necesario. Quizás en el "mundo funcional" existen estructuras de datos que pueden intercambiar esta información por un poco de velocidad de iteración.

En C elegiría directamente una matriz simple. La pregunta es, ¿qué debería elegir en OCaml?

Answer 1

Es poco probable que lo haga mejor que las matrices y listas incorporadas, ya que están codificadas manualmente en C, a menos que se vincule a su propia implementación nativa de un iterador. Una matriz se comportará casi exactamente como una matriz en C (un bloque de memoria asignado contiguamente que contiene una secuencia de valores de elementos), posiblemente con algunas indirecciones de puntero adicionales debido al boxeo. La lista se implementa exactamente como se esperaría: como celdas con un valor y un puntero "siguiente". Las matrices le proporcionarán la mejor localidad para los tipos sin casilla (especialmente float s, que tienen una implementación unboxed super especial).

Para obtener información acerca de la aplicación de matrices y listas, ver Section 18.3 of the OCaml manual y los archivos byterun/mlvalues.h, byterun/array.c y byterun/alloc.c en el código fuente OCaml.

Del interrogador: de hecho, Array parece ser la solución más rápida. Sin embargo, solo superó List en un 7%. Tal vez fue porque el tipo de elemento de una matriz no era lo suficientemente claro: era un tipo algebraico. Hashtbl realizado 4 veces peor, como se esperaba.

Así que elegiré Array y estoy aceptando esta. bueno.

Answer 2

Todas las estructuras de datos comunes son iterables en el tiempo O (n), por lo que las diferencias entre estructuras de datos solo serán constantes (y muy probablemente no significativas).

Al menos las listas y matrices permiten la iteración sin gastos indirectos significativos. No puedo pensar en una situación en la que eso no sea lo suficientemente rápido.

Answer 3

La matriz - una pieza lineal de memoria con los elementos visitados en orden secuencial - utiliza mejor la memoria caché de datos L1 de la CPU.

Answer 4

Para estar seguro, tendrá que medir. De acuerdo con las instrucciones de la máquina que es probable que el compilador genere, probaría una matriz y luego una lista.

• El acceso a un elemento de matriz requiere una verificación de los límites, la aritmética de direcciones, y una carga

• acceso a la cabeza de una lista requiere una carga, una prueba para la lista vacía, y una carga en una conocido tiempo de compilación en offset.

Los detalles de los cuales es más rápido probablemente dependan de su aplicación y de qué más está sucediendo en su máquina. También dependen del tipo de elementos; por ejemplo, si son números de coma flotante, ocamlopt puede ser lo suficientemente inteligente como para hacer una matriz sin caja, lo que le ahorrará un nivel de indirección.

Otras estructuras de datos comunes como tablas hash o árboles balanceados generalmente requieren que se asigne algún contexto en algún lugar para realizar un seguimiento de dónde se encuentra. Con una matriz, hacer un seguimiento requiere solo un índice entero; con una lista, hacer un seguimiento requiere un solo puntero. Creo que esto será difícil de superar en otra estructura de datos.

Finalmente, tenga en cuenta que puede haber solo un compilador OCaml, pero tiene dos extremos: código de bytes y código nativo. Naturalmente, si le importa este nivel de rendimiento, está utilizando la versión de código nativo ocamlopt. ¿Derecha?

Por favor tome medidas y edite los resultados en su pregunta.

Answer 5

No se olvide de Bigarray s, están más cerca de las matrices en C (solo una pieza plana de memoria), pero no pueden contener valores OCaml arbitrarios. También considere desactivar la verificación de límites (unsafe_set/get). Y, por supuesto, deberías hacer un perfil primero.