[argentinator]

Agregué un "if" a las comparaciones, para ver si eso hace algún "daño" al costo de procesamiento, y parece que trae mucho costo.

Ya me parecía raro que las comparaciones no consuman nada de tiempo.
Es algo ridículo.

Resulta que los "if" me dan un costo mayor que las asignaciones.

Maldición 




Midiendo costos para bucle for:

Tiempo empleado: 385

Midiendo costos para tipo float:

Comparaciones: 597
Asignaciones:  383

Midiendo costos para tipo int:

Comparaciones: 376
Asignaciones:  385

Midiendo costos para char[]:

Comparaciones: 5158
Asignaciones:  4821


Programa:

Spoiler

#include <stdio.h>
#include <float.h>
#include <time.h>
#include <string.h>

int main(void) {

  long long int maxj = 100000000, j = 0;
 
  float x1 = 0.0F,  x2 = 1.0F + FLT_EPSILON;
  int   y1 = 10000, y2 = 10001;
  char  z1[100] = "No sabía si era eficiente copiar strings largas. A Ver...",
        z2[100] = "No sabía si era eficiente copiar strings largas. Aura sí...";
   
  clock_t t1, t2, t3;
 
  t1 = clock();
  for (j = 0; j < maxj; j++)
    ;
  t2 = clock();
 
   printf(
     "Midiendo costos para bucle for:\n\n"
     "Tiempo empleado: %lli\n\n", (long long) (t2-t1)
    );
     
  t1 = clock();
  for (j = 0; j < maxj; j++) {
        if (x1 < x2)
           ;
  } 
  t2 = clock();
  for (j = 0; j < maxj; j++) {
        x1 = x2;
  }
  t3 = clock();
 
   printf(
     "Midiendo costos para tipo float:\n\n"
     "Comparaciones: %lli\n"
     "Asignaciones:  %lli\n"
     "\n", (long long)(t2-t1), (long long)(t3-t2)
  );

  t1 = clock();
  for (j = 0; j < maxj; j++) {
        if (y1 < y2)
           ;
  } 
  t2 = clock();
  for (j = 0; j < maxj; j++) {
        y1 = y2;
  }
  t3 = clock();
 
   printf(
     "Midiendo costos para tipo int:\n\n"
     "Comparaciones: %lli\n"
     "Asignaciones:  %lli\n"
     "\n", (long long)(t2-t1), (long long)(t3-t2)
  );

  t1 = clock();
  for (j = 0; j < maxj; j++) {
        if (strcmp(z1, z2))
           ;
  } 
  t2 = clock();
  for (j = 0; j < maxj; j++) {
        strcpy(z1, z2);
  }
  t3 = clock();
 
   printf(
     "Midiendo costos para char[]:\n\n"
     "Comparaciones: %lli\n"
     "Asignaciones:  %lli\n"
     "\n", (long long)(t2-t1), (long long)(t3-t2)
  );

   getchar();

   return 0;
   
}

[cerrar]

[argentinator]

Mi conclusión es que las comparaciones parecen ser más costosas que las asignaciones,
con lo cual tuerzo mi brazo en este debate a favor del camarada PabloN. 

Pero por suerte no estoy obligado a darle toda la razón, ya que el costo de las asignaciones es muy similar al de las comparaciones.
Y por lo tanto conviene evitarlas tanto como sea posible.

[pierrot]

Pero por suerte no estoy obligado a darle toda la razón, ya que el costo de las asignaciones es muy similar al de las comparaciones.
Y por lo tanto conviene evitarlas tanto como sea posible.

Yo nunca dije lo contrario. Por eso en mi programa cambié la condición if (v[i] >= v[k]) por if (v[i] > v[k]) (y de hecho estuve a punto de escribir algo al respecto), pero me limité a modificarlo solamente, pues lo consideré un detalle (no muy relevante), y además distraería al lector sobre lo que yo pretendía que fuera el foco de atención, que era pasar la longitud del vector como parámetro.

En particular, puede haber varios índices que contengan el valor máximo.
El algoritmo utilizado se queda con el último de estos índices.

En realidad, si no se exige nada al respecto, mi procedimiento es ineficiente.
Conviene elegir el primer índice k donde aparece el máximo...  

Ahí te interpreté mal porque yo creí que estabas hablando de interrumpir la recorrida en algún momento, lo cual es obviamente imposible. Uno no se puede detener en un índice confiando en que ya tiene el máximo, pues el máximo podría estar en la parte del vector que aún nos es desconocida.

También es cierto que al momento de pensar en eficiencia (que lo hice al ver la idea de xamo), automáticamente pensé en número de comparaciones. Como de inmediato me di cuenta de que no se podía hacer nada mejor, me despreocupé por completo. Uno tiende a pensar que una recorrida con un for, sin más, es algo poco inteligente. Pensé en comparaciones y no asignaciones, puesto que la mayoría de los libros de análisis de algoritmos toma como operación básica la comparación entre elementos del arreglo. Así, por ejemplo, cuando se dice que QuickSort es \( O(n\log n) \) en el peor caso, se está refiriendo al número de comparaciones. Lo mismo cuando se dice que InsertionSort es \( O(n) \) en el caso promedio, etc.

Esto no quiere decir que las asignaciones sean despreciables en la realidad. Lo son en nuestro análisis, si tomamos como operación básica a la comparación.

Las asignaciones están ahí, y consumen tiempo.

Completamente de acuerdo.

Además, una cosa es el análisis teórico de los algoritmos, y otra es la practica.
El análisis teórico sirve para no hacer algoritmos desastrosos.
Pero los resultados quedan dependiendo de ciertas constantes que no se explicitan.

En la implementación real esas constantes cuentan.

Si uno va a ordenar vectores de \( n < 100 \) elementos con un algoritmo de complejidad "eficiente" \( 1000000\; n \log(n) \), contra otro algoritmo "ineficiente" de complejidad \( 5\;n^2 \), conviene el "ineficiente". 

Sí, sí. Está claro. Cuando hacemos todas estas consideraciones nos estamos refiriendo al comportamiento asintótico del algoritmo. Por supuesto que un algoritmo que es óptimo para entradas arbitrariamente grandes, no tiene por que ser el mejor para \( n \) pequeño. Todo depende de para qué se lo va a usar.

Saludos

[argentinator]

Bueno, habría que revisar la teoría de los algoritmos de ordenación.

No sé por qué dirán esos libros que las asignaciones son despreciables.
Incluso asintóticamente, o teóricamente, o como sea, debería importar.

En el análisis del "peor caso", por lo general ocurre que hay tantas comparaciones como asignaciones.
O sea que asintóticamente tendrian costo equivalente...

Aunque hay algo claro: el número de asignaciones es siempre menor que el de comparaciones,
porque las comparaciones se hacen siempre, pero las asignaciones sólo cuando hay algún par de elementos que deben reordenarse.

O sea que asintóticamente domina el número de comparaciones.

[pierrot]

¡Me había olvidado de liberar la memoria!

int main(void) {

   int largo;

   printf("Longitud de v: "); scanf("%d",&largo);

   float *v = new float[largo];

   cargar(v,largo);

   int k = indice_maximo(v,largo);

   printf("Indice maximo:    k  == %i\n",  k);
   printf("Maximo:         v[k] == %g\n", v[k]);

   delete[] v;  

   getchar();

   return 0;

}

[argentinator]

¡Me había olvidado de liberar la memoria!

¡Ahá, conque cometiendo pecaditos de C! Jeje