Archivo de Etiquetas de ‘binarysearch’

Archivo de Etiquetas de 'binarysearch'

Jugando con ArrayList en VisualBasic.NET (III).

Publicado

por

el 2 Julio 2008

. 0 Comentarios

Después de unos días de mucho volumen de trabajo que me ha mantenido algo alejado del blog, aquí pongo la tercera parte de este post sobre ArrayList en VisualBasic.NET. En la primera estuve hablando de que para que el método BinarySearch o Sort puedan funcionar adecuadamente se necesita que los objetos que llenan el ArrayList se puedan comparar. Comenté también que había dos maneras de hacer esto: mediante una clase externa que implemente un IComparer o haciendo que la clase en cuestión implemente IComparable. En la segunda parte mostré el sistema de hacer que clsPerson (mi clase ejemplo) implemente IComparable. En esta tercera parte muestro el sistema de utilizar una clase externa que implemente IComparer.

Para ello la clase clsPerson de ejemplo quedará esta vez así:

'--------------------------------------------------------------------
' Author: Albert Mata (www.albertmata.net)
' Date: 20080702
' Description: Class to show how to work with ArrayList.
'--------------------------------------------------------------------
Public Class clsPerson

    '----------------------------------------------------------------
    ' Attributes.
    '----------------------------------------------------------------
    Public Name As String
    Public Age As Integer

    '----------------------------------------------------------------
    ' Constructor method.
    '----------------------------------------------------------------
    Public Sub New(ByVal Name As String, ByVal Age As Integer)
        Me.Name = Name
        Me.Age = Age
    End Sub

End Class

O sea, extremadamente simple, sin rastro del IComparable que utilizamos en el post anterior. Pero ahora necesitaremos una clase más que actuará de comparador y que tendrá el siguiente código:

'--------------------------------------------------------------------
' Author:      Albert Mata (www.albertmata.net)
' Date:        20080702
' Description: Class to compare clsPerson objects by name.
'--------------------------------------------------------------------
Public Class clsPersonComparatorByName
    Implements IComparer

    '----------------------------------------------------------------
    ' Method to compare two clsPerson objects.
    '----------------------------------------------------------------
    Public Function Compare(ByVal x As Object, ByVal y As Object) _
    As Integer Implements IComparer.Compare
        'Converting received objects to clsPerson type.
        Dim Object1 As clsPerson = CType(x, clsPerson)
        Dim Object2 As clsPerson = CType(y, clsPerson)
        'Criterium to be used to compare.
        Dim Result As Integer
        If (Object1.Name < Object2.Name) Then
            Result = -1
        ElseIf (Object1.Name > Object2.Name) Then
            Result = 1
        Else
            Result = 0
        End If
        'Returning result.
        Return Result
    End Function

End Class

Una vez implementadas estas dos clases, podemos crearnos un ArrayList, llenarlo de objetos clsPerson y ordenarlo para posteriormente mostrar los resultados. No obstante podemos tener más de una clase comparadora para así poder comparar en cada caso utilizando criterios distintos. Por ejemplo yo he creado una clase que compara dos objetos clsPerson según el nombre, pero puedo hacer lo mismo comparándolos según la edad:

'--------------------------------------------------------------------
' Author:      Albert Mata (www.albertmata.net)
' Date:        20080702
' Description: Class to compare clsPerson objects by age.
'--------------------------------------------------------------------
Public Class clsPersonComparatorByAge
    Implements IComparer

    '----------------------------------------------------------------
    ' Method to compare two clsPerson objects.
    '----------------------------------------------------------------
    Public Function Compare(ByVal x As Object, ByVal y As Object) _
    As Integer Implements IComparer.Compare
        'Converting received objects to clsPerson.
        Dim Object1 As clsPerson = CType(x, clsPerson)
        Dim Object2 As clsPerson = CType(y, clsPerson)
        'Criterium to be used to compare.
        Dim Result As Integer
        If (Object1.Age < Object2.Age) Then
            Result = -1
        ElseIf (Object1.Age > Object2.Age) Then
            Result = 1
        Else
            Result = 0
        End If
        'Returning result.
        Return Result
    End Function

End Class

Y finalmente podemos comprobar el funcionamiento de todo ello con el siguiente código:

'Creating and filling ArrayList with people.
Dim People As New ArrayList()
People.Add(New clsPerson("Albert", 29))
People.Add(New clsPerson("Morgan", 32))
People.Add(New clsPerson("Lucas", 35))
People.Add(New clsPerson("Steven", 39))
People.Add(New clsPerson("Zoe", 17))

'Showing ArrayList's elements before sorting.
Debug.Print("-------- Before sorting ---------")
Dim IT As IEnumerator = People.GetEnumerator
Dim Person As clsPerson
While IT.MoveNext
Person = IT.Current
Debug.Print(Person.Name & " - " & Person.Age)
End While

'Sorting ArrayList by name.
People.Sort(New clsPersonComparatorByName())

'Showing ArrayList's elements after sorting by name.
Debug.Print("----- After sorting by name -----")
IT = People.GetEnumerator
While IT.MoveNext
Person = IT.Current
Debug.Print(Person.Name & " - " & Person.Age)
End While

'Sorting ArrayList by age.
People.Sort(New clsPersonComparatorByAge())

'Showing ArrayList's elements after sorting by age.
Debug.Print("----- After sorting by age ------")
IT = People.GetEnumerator
While IT.MoveNext
Person = IT.Current
Debug.Print(Person.Name & " - " & Person.Age)
End While

Que nos devuelve un resultado en la ventana Inmediato (CTRL+G para visualizarla) como el que sigue:

-------- Before sorting ---------
Albert - 29
Morgan - 32
Lucas - 35
Steven - 39
Zoe - 17
----- After sorting by name -----
Albert - 29
Lucas - 35
Morgan - 32
Steven - 39
Zoe - 17
----- After sorting by age ------
Zoe - 17
Albert - 29
Morgan - 32
Lucas - 35
Steven - 39

O sea, exactamente lo que pretendíamos. Quedan pues vistos los dos sistemas para hacer que una clase sea comparable.

Jugando con ArrayList en VisualBasic.NET (II).

Publicado

por

Albert Mata

el 22 Junio 2008

en .NET

. 0 Comentarios

En el anterior post estuve hablando de los ArrayList en VisualBasic.NET y comenté que para que el método BinarySearch funcione es necesario que los objetos dentro del ArrayList estén ordenados. Al menos para que funcione correctamente, claro.

Una de las maneras de ordenarlos era utilizando el método Sort. Otra consistía en añadir los objetos mediante el método Insert y hacerlo en la posición adecuada para que el ArrayList estuviera siempre ordenado. Así que en cualquier caso necesitaremos que los objetos que llenan el ArrayList se puedan comparar. Si lo hacemos tirando de método Sort porque tendrán que poder ordenarse. Si no, porque BinarySearch necesita poder comparar dos objetos para determinar si son el mismo en función de los criterios que le digamos.

En mi ejemplo teníamos un ArrayList lleno de personas que eran instancias de la clase clsPerson. Así que vamos a ver cómo hacer que dos objetos clsPerson se puedan comparar. Para ello ya dije que tenemos dos alternativas: mediante una clase externa que implemente un IComparer, o haciendo que clsPerson implemente IComparable.

En este post explico el segundo sistema: hacer que clsPerson implemente IComparable. En realidad es muy sencillo, puesto que sólo tenemos que crear la clase como lo haríamos en circunstancias normales y tener en cuenta que tenemos que hacerle dos pequeñas modificaciones:

1) Tras la definición de la clase (Public Class clsPerson) informarle que va a ser una clase que implementará IComparable (Implements IComparable).

2) Crearle un método CompareTo para poder comparar la instancia actual con otra instancia de clsPerson. De hecho al pulsar Enter después de añadir el Implements IComparable ya se nos creará el método CompareTo automáticamente.

Adjunto código básico:

'--------------------------------------------------------------------
' Author:      Albert Mata (www.albertmata.net)
' Date:        20080622
' Description: Class to show how to work with ArrayList.
'--------------------------------------------------------------------
Public Class clsPerson
    Implements IComparable 'in order to be able to be compared

    '----------------------------------------------------------------
    ' Comparator method. Returns:
    '  -1 if current instance is "smaller" than parameter object.
    '   0 if current instance is "equal to" parameter object.
    '  +1 if current instance is "bigger" than parameter object.
    '----------------------------------------------------------------
    Public Function CompareTo(ByVal obj As Object) As Integer _
    Implements System.IComparable.CompareTo
        'Converting parameter object to clsPerson type.
        Dim Compare As clsPerson = CType(obj, clsPerson)
        'First criterium to be used to compare.
        Dim Result As Integer = Me.Name.CompareTo(Compare.Name)
        'When draw happens, next criterium to be used to compare.
        If Result = 0 Then
            Result = Me.Age.CompareTo(Compare.Age)
        End If
        'Returning result.
        Return Result
    End Function

End Class

Como se puede ver, el método CompareTo no entraña dificultad. Simplemente hay que ir dándole criterios con los que poder comparar la instancia sobre la que trabajamos con otra instancia que la función recibirá como argumento. En principio en nuestro código no necesitaremos invocar directamente esta función, ya que es algo que hará de manera interna el método Sort o BinarySearch del ArrayList que contiene los objetos de tipo clsPerson. No obstante como método normal y corriente que es nada nos impide utilizarlo también de manera directa. Para ella creamos por ejemplo 5 objetos con las instrucciones:

Dim P1 As New clsPerson("Albert", 29)
Dim P2 As New clsPerson("Morgan", 32)
Dim P3 As New clsPerson("Albert", 35)
Dim P4 As New clsPerson("Morgan", 32)
Dim P5 As New clsPerson("Zoe", 17)

Y a continuación podemos realizar llamadas y obtener estos resultados:

P1.CompareTo(P2) returns... -1
P5.CompareTo(P1) returns...  1
P3.CompareTo(P1) returns...  1
P2.CompareTo(P4) returns...  0

Lo que nos dice que Albert-29 es más “pequeño” que Morgan-32 (ojo, la ordenación va por nombre, no por edad), Zoe-17 es más “grande” que Albert-29, Albert-35 es más “grande” que Albert-29 (si la ordenación por nombre no puede discernir, pasa a las edades) y finalmente Morgan-32-P2 es igual a Morgan-32-P4, lo cual es correcto porque ambos objetos son iguales (es sólo un ejercicio teórico, en realidad no existirían los dos objetos porque de hecho sería un objeto duplicado).

Jugando con ArrayList en VisualBasic.NET (I).

Publicado

por

Albert Mata

el 18 Junio 2008

en .NET

. 0 Comentarios

¿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:

Private ListOfPersons As ArrayList
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:

Dim TempPerson As clsPerson
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:

Dim TempPerson As clsPerson
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:

Public Function PersonExist(ByVal Name As String) As Boolean
    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 TempPerson As clsPerson
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:

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.

El Blog de Albert Mata