He estado buscando un tipo de matriz con las siguientes características en Erlang.¿Hay algún módulo que implemente un tipo de matriz eficiente en Erlang?
append(vector(), term()) O(1)
nth(Idx, vector()) O(1)
set(Idx, vector(), term()) O(1)
insert(Idx, vector(), term()) O(N)
remove(Idx, vector()) O(N)
normalmente utilizo una tupla para este fin, pero las características de rendimiento no son lo que yo quiero para la gran N. Mi pruebas muestran las siguientes características de rendimiento ...
erlang:append_element/2 O(N).
erlang:setelement/3 O(N).
he empezado en un módulo basado en la implementación de clojure.lang.PersistentVector, pero si ya se ha hecho, no reinventaré la rueda.
Editar:
Para los interesados, he terminado la implementación vector.erl ... usando el mismo algoritmo que clojure.lang.PersistentVector. Tiene características de rendimiento similares al módulo de matriz, pero tiene factores constantes levemente mejores en append.
La siguiente prueba agrega 10000 elementos por intervalo y luego realiza 10000 búsquedas y 10000 actualizaciones en un índice aleatorio. Todas las operaciones están cerca de O (1). Los tiempos en la tupla interna están en microsegundos.
3> seq_perf:test(vector, 100000, 10).
{2685854,
{ok,[{100000,{66966,88437,124376}},
{200000,{66928,76882,125677}},
{300000,{68030,76506,116753}},
{400000,{72429,76852,118263}},
{500000,{66296,84967,119828}},
{600000,{66953,78155,116984}},
{700000,{65996,77815,138046}},
{800000,{67801,78455,118191}},
{900000,{69489,77882,114886}},
{1000000,{67444,80079,118428}}]}}
4> seq_perf:test(array, 100000, 10).
{2948361,
{ok,[{100000,{105482,72841,108828}},
{200000,{123655,78898,124092}},
{300000,{110023,76130,106806}},
{400000,{104126,73830,119640}},
{500000,{104771,72593,110157}},
{600000,{107306,72543,109713}},
{700000,{122066,73340,110662}},
{800000,{105853,72841,110618}},
{900000,{105267,73090,106529}},
{1000000,{103445,73206,109939}}]}}
Parece haber un par de trucos útiles en la implementación de PersistentVector que podrían aplicarse al módulo de matriz de Erlang, como el retraso de las inserciones de cola. – RichardC
De hecho. El módulo de matriz utiliza algunos trucos para extender la matriz con índices no definidos 'no definidos'. También parece comprimir grandes extensiones de elementos "indefinidos". – dsmith