Colas enlazadas mas rápidas que arrays?
4 02 2009Estaba leyendo esta nota donde dice que las colas indexadas son mas rápidas que los arrays. En este post, hay varias respuestas afirmando la valides de esta afirmacion.
El problema es que las pruebas que hice por mi cuenta arrojan exactamente lo opuesto:
Actionscript:
-
package {
-
import flash.display.Sprite;
-
import flash.utils.getTimer;
-
-
public class DeleteThisProject extends Sprite
-
{
-
public function DeleteThisProject()
-
{
-
var myArray:Array = new Array();
-
var tempSP:Sprite;
-
-
var i:int = 0;
-
trace("Populating Arrays");
-
for(i = 0; i <= 10000; i++)
-
{
-
tempSP = new Sprite();
-
tempSP.y = 100;
-
myArray.push(tempSP);
-
}
-
var lastCola:Cola = null;
-
var tempCola:Cola;
-
for(i = 0; i <= 10000; i++)
-
{
-
tempSP = new Sprite();
-
tempCola = new Cola(tempSP);
-
tempCola.next = lastCola;
-
lastCola = tempCola;
-
}
-
trace("Finished populating arrays");
-
trace("Begin Array iteration");
-
var timeStamp:int = getTimer();
-
for(i = 0; i <myArray.length; i++)
-
{
-
tempSP = Sprite(myArray[i])
-
tempSP.graphics.beginFill(0xFF0000);
-
tempSP.graphics.drawCircle(0, 0, 50);
-
addChild(tempSP);
-
}
-
trace("End Array iteration: " + (getTimer() - timeStamp) + "ms");
-
-
trace("Begin Cola iteration");
-
timeStamp = getTimer();
-
tempCola = lastCola;
-
i = 0;
-
while(tempCola)
-
{
-
tempSP = tempCola.sprite;
-
tempSP.graphics.beginFill(0x00FF00);
-
tempSP.graphics.drawCircle(0, 0, 50);
-
addChild(tempSP);
-
tempCola = tempCola.next;
-
}
-
trace("End Cola iteration: " + (getTimer() - timeStamp) + "ms " );
-
}
-
}
-
}
La clase Cola dice así:
Actionscript:
-
package
-
{
-
import flash.display.Sprite;
-
-
public class Cola
-
{
-
public var next:Cola;
-
public var sprite:Sprite;
-
public function Cola(pSprite:Sprite)
-
{
-
sprite = pSprite;
-
}
-
}
-
}
Los valores que obtuve son los siguientes:
Populating Arrays
Finished populating arrays
Begin Array iteration
End Array iteration: 737ms
Begin Cola iteration
End Cola iteration: 7124ms
Finished populating arrays
Begin Array iteration
End Array iteration: 737ms
Begin Cola iteration
End Cola iteration: 7124ms
De que esta hablando esta gente?
Acceder a un elemento determinado:
Un array es mucho mas rápido que una lista enlazada solo para acceder a un elemento en posicion x. Para hacer lo mismo en una lista enlazada hay que recorrer desde el principio hasta el elemento, básicamente es O(1) – Array contra O(n) – Lista enlazada.
Acceder a varios elementos:
En este caso la performance es similar, es constante en ambos casos – O(1)
Insertar elementos:
Acá está el tema: en una lista enlazada insertar un elemento es rapido ( basta con cambiar el next del elemento anterior y el prev del elemento siguiente), esto lleva O(1). En cambio en un array habría que mover todos los elementos al final para hacer espacio en el medio O(n) , donde N es la posicion del array donde se quiere insertar.
Remover elementos:
Acá también gana la lista enlazada, un elemento se puede eliminar en tiempo constante, mientras que en el array es necesario mover todos los elementos una posicion para atras.
Busqueda lineal:
Misma performance (igual que al acceder a varios elementos)
Busqueda binaria:
Es imposible de realizar en una lista enlazada, por lo que acá el array gana O(log n) versus O(n)
Depende del uso que necesite, conviene usar uno u otro.
gzaloprgm
Muchas gracias por la aclaración!