0

Tengo dos métodos de busqueda lineal y binaria ¿Cómo se puede contar el número de comparaciones en cada caso?

void linear_search(int* mas, int n, int element) 
{
    int comparisons = 0;
    for (int i = 0; i < n; i++) {
        if (element == mas[i])
            cout << "\nThe number of element is: " << i + 1 << "\n" << endl;
    }
}

int binary_search(int* mas, int n, int element)
{
    int first = 0;
    int middle;
    int last = n-1;

    while (first <= last) {
        middle = (first + last) / 2;

        if (element == mas[middle]) {
            cout << "\nThe number of element is: " << middle + 1 << "\n" << endl;
            return mas[middle];
        }
        else  {
            if (mas[middle] > element) {
                last = middle - 1;
            }
            else  first = middle + 1;
        }
    }
    return -1;
}
1
  • ¿A que te refieres con el número de comparaciones? Si quieres sacar el número de veces que intenta hacer la comparación puedes sacar el número n directamente. el 29 nov. 2016 a las 9:51

1 respuesta 1

1

Estás haciendo dos comparaciones diferentes (igualdad y mayor que). Ignoro si deseas contabilizarlas por separado o juntas así que asumo que no quieres distinguirlas.

En C++ únicamente se puede sobrecargar el operador de comparación para tipos propios (clases o estructuras), no es posible sobrecargar el operador para tipos nativos (int, float, double).

Una posible solución sería crear un wrapper para el tipo int y sobrecargar sus operadores para que realicen la comparación:

struct IntWrapper
{
  IntWrapper(int value)
    : value(value)
  { }

  int value;

  static size_t contador;
};

size_t IntWrapper::contador = 0;

bool operator==(IntWrapper a, IntWrapper b)
{
  IntWrapper::contador++;
  return a.value == b.value;
}

bool operator>(IntWrapper a, IntWrapper b)
{
  IntWrapper::contador++;
  return a.value > b.value;
}

Ahora, para aprovechar esta funcionalidad se puede hacer de dos formas:

  • Se modifica la firma de las funciones para que element sea del tipo Wrapper.

    void linear_search(int* mas, int n, IntWrapper element)
    {
      for (int i = 0; i < n; i++) {
        if ( element == mas[i] )
          cout << "\nThe number of element is: " << i + 1 << "\n" << endl;
      }
    }
    
    int binary_search(int* mas, int n, IntWrapper element)
    {
      int first = 0;
      int middle;
      int last = n-1;
    
      while (first <= last) {
        middle = (first + last) / 2;
    
        if ( element == mas[middle]) {
          cout << "\nThe number of element is: " << middle + 1 << "\n" << endl;
          return mas[middle];
        }
        else  {
          if (mas[middle] > element ) {
            last = middle - 1;
          }
          else  first = middle + 1;
        }
      }
      return -1;
    }
    
  • Se realiza la conversión dentro de la clase

    void linear_search(int* mas, int n, IntWrapper element)
    {
      IntWrapper elem(element)
      for (int i = 0; i < n; i++) {
        if ( elem == mas[i] )
          cout << "\nThe number of element is: " << i + 1 << "\n" << endl;
      }
    }
    
    int binary_search(int* mas, int n, int element)
    {
      IntWrapper elem(element);
    
      int first = 0;
      int middle;
      int last = n-1;
    
      while (first <= last) {
        middle = (first + last) / 2;
    
        if ( elem== mas[middle]) {
          cout << "\nThe number of element is: " << middle + 1 << "\n" << endl;
          return mas[middle];
        }
        else  {
          if (mas[middle] > elem) {
            last = middle - 1;
          }
          else  first = middle + 1;
        }
      }
      return -1;
    }
    

Y ahora el main para probar:

int main()
{
  int datos[] = {0,1,2,3,4,5,6,7,8,9};

  linear_search(datos,10,5);

  std::cout << IntWrapper::contador << '\n';
  IntWrapper::contador = 0;

  binary_search(datos,10,5);

  std::cout << IntWrapper::contador << '\n';
}

Esta solución funciona porque el constructor del wrapper no se ha etiquetado como explicit y, en consecuencia, el compilador realiza una conversión de int a IntWrapper. Si la operación se hiciese de forma explícita las comparaciones quedarían así:

if ( element == IntWrapper(mas[middle])) {

if ( IntWrapper(mas[middle]) > element ) {

Yo he optado por no etiquetar el constructor como explicit para simplificar el código, pero lo cierto es que lo recomendable es que este tipo de constructores se marquen como explicit para evitar conversiones no deseadas:

struct IntWrapper
{
  explicit IntWrapper(int value);
};

Otra opción pasa por crear una clase que realice las comparaciones por nosotros y realice el conteo:

struct Comparador
{
  Comparador()
    : contador(0)
  { }

  bool AreEqual(int a, int b)
  {
    ++contador;
    return a == b;
  }

  bool AreGreater(int a, int b)
  {
    ++contador;
    return a > b;
  }

  size_t contador;
};

Y ahora solo falta inyectarla en las funciones:

void linear_search(int* mas, int n, int element, Comparador& comp)
{
    for (int i = 0; i < n; i++) {
        if (comp.AreEqual(element,mas[i]))
            cout << "\nThe number of element is: " << i + 1 << "\n" << endl;
    }
}

int binary_search(int* mas, int n, int element, Comparador& comp)
{
    int first = 0;
    int middle;
    int last = n-1;

    while (first <= last) {
        middle = (first + last) / 2;

        if (comp.AreEqual(element,mas[middle])) {
            cout << "\nThe number of element is: " << middle + 1 << "\n" << endl;
            return mas[middle];
        }
        else  {
            if (comp.AreGreater(mas[middle],element)) {
                last = middle - 1;
            }
            else  first = middle + 1;
        }
    }
    return -1;
}

int main()
{
  int datos[] = {0,1,2,3,4,5,6,7,8,9};
  Comparador comp1;

  linear_search(datos,10,5,comp1);

  Comparador comp2;
  binary_search(datos,10,5,comp2);

  std::cout << comp1.contador << '\n'
            << comp2.contador << '\n';
}

Las ventajas de cada sistema son las siguientes:

Con wrapper:

  • Las funciones sufren menos cambios
  • Se pueden seguir usando los operadores

Con clase para las comparaciones:

  • Es más sencillo gestionar el contador (basta con crear un objeto nuevo)

EDITO:

Un detalle que se me había olvidado comentar es que la opción de usar el wrapper se puede complementar con un template de la función, de tal forma que podamos decidir si queremos usar el wrapper o no:

template<class Wrapper, class Tipo>
void linear_search(Tipo* mas, int n, Wrapper element)
{
  for (int i = 0; i < n; i++) {
    if ( element == mas[i] )
      cout << "\nThe number of element is: " << i + 1 << "\n" << endl;
  }
}

Así, si queremos realizar el conteo para pruebas podemos realizar la llamada:

linear_search<IntWrapper>(datos,10,5);     // opcion 1
linear_search<IntWrapper,int>(datos,10,5); // opcion 2

Y cuando no queramos las estadísticas podemos hacer:

linear_search<int,int>(datos,10,5); // opcion 1
linear_search<int>(datos,10,5);     // opcion 2
linear_search(datos,10,5);          // opcion 3

Por supuesto si ya metemos templates en escena el abanico de posibilidades se amplía hasta límites insospechados. Todo depende de lo que te guste investigar.

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.