¿Cómo se implementan las matrices ruby de forma interna (principalmente en CRuby, pero se recibe cualquier otra información)?ruby array internal
¿Son arreglos creíbles como un vector C++ o están basados en listas? ¿Cuál es la complejidad de cambiar/desviar y acceder a un elemento por índice?
Son arrays cultivables que "crecen al final".
shift es O(1), unshift es O(n) y el acceso por el índice es O(1). Según mi leal saber y entender, esto es válido para todas las implementaciones de ruby, pero definitivamente lo es para MRI.
No estoy seguro de que el cambio sea siempre O (N). Si recuerdo correctamente, el inicio del bloque de memoria y el índice del primer elemento se rastrean por separado, por lo que puede hacer un cambio O (1) al incrementar el índice del primer índice. Unshift es solo O (N) si no has realizado ningún turno. – AShelly
@AShelly: Parece tener razón acerca de 'shift' (aunque en realidad no realiza un seguimiento del índice inicial, sino que hace que la matriz se comparta), pero' unshift' definitivamente es 'O (n)' - llama ' memmove' en la matriz pase lo que pase. – sepp2k
Alguien debería hacer algunos puntos de referencia para ver. –
unshift es O (N^2) en mi ruby1.9.
$ /usr/bin/time ruby -e 'n=100000;l=[];(1..n).each{|i| l.push(i);}'
0.03 real 0.02 user 0.00 sys
$ /usr/bin/time ruby -e 'n=100000;l=[];(1..n).each{|i| l.unshift(i);}'
3.15 real 3.11 user 0.01 sys
$ /usr/bin/time ruby -e 'n=200000;l=[];(1..n).each{|i| l.unshift(i);}'
12.96 real 12.85 user 0.03 sys
$ ruby -v
ruby 1.9.3p194 (2012-04-20 revision 35410) [x86_64-darwin11.3.0]
Corrígeme si me equivoco, pero ¿no muestra esto que el desvío tiene una complejidad de tiempo cuadrática? Si el desplazamiento fuera lineal, al aumentar n de 100,000 a 200,000, no esperaría que se duplicara el tiempo. Como n aumenta en un factor de 2, el tiempo necesario para completar el algoritmo aumenta en un factor de 4. El número de operaciones es proporcional al tamaño del conjunto de datos al cuadrado. – louism2
@ louism2 derecho ... Lo arreglé en O (N^2), y noté que unshift() es O (N) en Ruby2 y O (N^2) en Ruby1.9. –
Si unshift es O (n) y lo llamas n veces, tardará O (n^2) tiempo ... también imagino que quieres más de dos puntos de datos para una tendencia .. – olleicua
Simplemente descargue el depo de SVN y lea el código fuente. La implementación no es realmente difícil para un programador en C. – texasbruce