Jugando con ArrayList en VisualBasic.NET (I).
¿Quién no hizo sus primeros pinitos en su día con simples arrays -o matrices o vectores- gozando de esa manera ordenada de acumular valores? Primero los unidimensionales... después sufriendo un poquito más con los multidimensionales... ¡qué tiempos! Ahora VisualStudio.NET (como también hace Java e imagino que cualquier lenguaje orientado a objetos) nos ofrece el ArrayList, esto es... una clase contenedora que vendría a ser el array de toda la vida pero MUY mejorado, ya que incluye multitud de métodos que nos ayudan a hacer fácilmente lo que antes con arrays teníamos que programar nosotros. El caso es que los ArrayList son precisamente lo último con lo que me he peleado seriamente, ya que necesito crear listas de objetos propios con muchísimos elementos (varios cientos de miles) y quería ver bajo qué circunstancias ofrece un mejor rendimiento.
Vamos al grano. He estado haciendo simulaciones de rendimiento con dos sistemas distintos. A nivel general tengo:
Me.ListOfPersons = New ArrayList()
Y una clase clsPerson de la que crearé numerosísimas instancias (objetos) para ver qué tal funciona el ArrayList.
En el sistema 1 tendremos algo del estilo de:
For i As Integer = 1 To OBJETOS_POTENCIALES
TempPerson = New clsPerson(Mid(Rnd.Next.ToString, 1, _
LONGITUD_NOMBRE))
If Me.ListOfPersons.BinarySearch(TempPerson) < 0 Then
Me.ListOfPersons.Add(TempPerson)
Me.ListOfPersons.Sort()
End If
Next
Mientras que en el sistema 2 tendremos:
For i As Integer = 1 To OBJETOS_POTENCIALES
TempPerson = New clsPerson(Mid(Rnd.Next.ToString, 1, _
LONGITUD_NOMBRE))
If Not Me.PersonExist(TempPerson.Name) Then
Me.ListOfPersons.Add(TempPerson)
End If
Next
Donde PersonExist es una función para determinar si el objeto clsPerson en cuestión existe ya o no (el único criterio que pongo para discernir si dos personas son o no la misma es el nombre -o el código al azar que genero a modo de nombre-). Para ello utiliza un enumerador de la siguiente forma:
Dim IT As IEnumerator = Me.ListOfPersons.GetEnumerator()
Dim CurrentPerson As clsPerson
Dim Found As Boolean = False
While IT.MoveNext And Not Found
CurrentPerson = IT.Current
'Two persons are the same when names are equal.
If CurrentPerson.Name = Name Then
Found = True
End If
End While
Return Found
End Function
Tanto en un escenario como en el otro, OBJETOS_POSIBLES será el número de objetos que crearemos para añadir al ArrayList, aunque algunos de ellos no se añadirán si ya están en el ArrayList, puesto que no queremos crear dos objetos para una misma persona. Por su parte, LONGITUD_NOMBRE marcará de alguna manera el número máximo de objetos distintos que podremos tener, ya que con un valor 1 admitirá máximo 9, con un valor 2 admitirá 99, con 3 admitirá 999 y así sucesivamente. De este modo, jugando con ambos valores podremos evaluar los dos métodos bajo distintos escenarios.
| OBJETOS_POTENCIALES = 100.000 |
| LONGITUD_NOMBRE = 3 |
+----------------------------------------+
| Sistema 1 tarda... 1368 milisegundos |
| Sistema 2 tarda... 1682 milisegundos |
+----------------------------------------+
+----------------------------------------+
| OBJETOS_POTENCIALES = 500.000 |
| LONGITUD_NOMBRE = 3 |
+----------------------------------------+
| Sistema 1 tarda... 2606 milisegundos |
| Sistema 2 tarda... 8705 milisegundos |
+----------------------------------------+
+----------------------------------------+
| OBJETOS_POTENCIALES = 50.000 |
| LONGITUD_NOMBRE = 4 |
+----------------------------------------+
| Sistema 1 tarda... 130602 milisegundos |
| Sistema 2 tarda... 7354 milisegundos |
+----------------------------------------+
Vemos pues que cuando trabajamos con pocos objetos (LONGITUD_NOMBRE = 3, por tanto máximo 999 objetos), el sistema con el BinarySearch se muestra más rápido. Sin embargo a la que crece el número de objetos (LONGITUD_NOMBRE = 4, por tanto máximo 9.999 objetos) el sistema del BinarySearch es terriblemente más lento que el sistema más manual.
Esto es así porque aunque el sistema que utiliza el BinarySearch es en principio más elegante (al fin y al cabo se trata de un método propio del ArrayList en lugar de un método nuevo creado a mano), para funcionar necesita que el ArrayList esté siempre ordenado, de lo contrario no funciona. Para ello en principio tenemos que recurrir a efectuar un Sort tras cada nuevo objeto añadido al ArrayList, pero como hemos visto, cuando estamos trabajando con muchos objetos este proceso se vuelve lentísimo y el método manual tirando de iterador resulta más eficiente.
Ahora bien, en realidad no es necesario hacer esto -ordenar el ArrayList tras cada incorporación- ya que el ArrayList nos ofrece un método ideal para solventar esta situación: el Insert. Con el Insert podemos añadir nuevos objetos al ArrayList igual que hacemos con el Add, sólo que en este caso le decimos en qué posición queremos que nos lo añada, corriendo un lugar hacia delante el resto de objetos desde esa posición hasta el final. ¿Qué conseguimos con esto? No necesitar ya el Sort para nada, puesto que el ArrayList estará siempre ordenado -si tenemos la precaución de situar cada nuevo objeto donde le corresponde- y por tanto podremos utilizar el BinarySearch. Llegamos así al sistema 3 y mejor de todos los expuestos:
Dim Index As Integer
For i As Integer = 1 To OBJETOS_POTENCIALES
TempPerson = New clsPerson(Mid(Rnd.Next.ToString, 1, _
LONGITUD_NOMBRE))
Index = Me.ListOfPersons.BinarySearch(TempPerson)
If Index < 0 Then
Me.ListOfPersons.Insert((Index * (-1)) - 1, TempPerson)
End If
Next
¿Pero cómo sabemos en qué posición debemos añadir el objeto? Debemos jugar con que BinarySearch además de devolvernos el valor de la posición (en base cero) del objeto coincidente cuando existe, también nos devuelve en negativo el valor de la posición (en base uno) del primer objeto mayor que el nuestro. Así pues, aplicamos eso de (Index * (-1)) - 1 y obtenemos la posición en la que queremos insertar el nuevo registro.
Analizando los resultados con el nuevo sistema vemos que no hay color:
| OBJETOS_POTENCIALES = 100.000 |
| LONGITUD_NOMBRE = 3 |
+----------------------------------------+
| Sistema 1 tarda... 1368 milisegundos |
| Sistema 2 tarda... 1682 milisegundos |
| Sistema 3 tarda... 319 milisegundos |
+----------------------------------------+
+----------------------------------------+
| OBJETOS_POTENCIALES = 500.000 |
| LONGITUD_NOMBRE = 3 |
+----------------------------------------+
| Sistema 1 tarda... 2606 milisegundos |
| Sistema 2 tarda... 8705 milisegundos |
| Sistema 3 tarda... 1547 milisegundos |
+----------------------------------------+
+----------------------------------------+
| OBJETOS_POTENCIALES = 50.000 |
| LONGITUD_NOMBRE = 4 |
+----------------------------------------+
| Sistema 1 tarda... 130602 milisegundos |
| Sistema 2 tarda... 7354 milisegundos |
| Sistema 3 tarda... 238 milisegundos |
+----------------------------------------+
Hay que tener en cuenta que para que BinarySearch funcione, los objetos clsPerson se tienen que poder comparar. Para ello habrá que implementar de una manera u otra algún comparador, ya sea mediante una clase externa que implemente un IComparer, ya sea haciendo que clsPerson implemente IComparable. En los dos próximos posts (siguiente y siguiente) mostraré estas dos alternativas con ejemplos de código minimalista para que funcione.
Tags: .NET, arraylist, binarysearch, icomparable, icomparer, sort, visual basic