[pierrot]

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...  

¿Es posible hacer eso?  

Spoiler

En general dado un problema hay muchos algoritmos que lo resuelven. Uno puede buscar algoritmos más eficientes, pero llega un cierto momento que no es posible encontrar ninguno mejor. ¿Cómo darse cuenta de que hemos llegado a este punto? De eso se encarga la ciencia que se llama Análisis de algoritmos. Cada problema tiene una complejidad mínima asociada, que en algunos casos, se puede determinar en forma teórica, de antemano, o sea, antes de buscar un método para solucionarlo. Si además se encuentra un algoritmo para ese problema que tiene la complejidad mínima, dicho algoritmo es óptimo.

En este caso, es fácil ver que no se puede hacer nada mejor que lo que hemos hecho. Fíjate que encontrar el máximo de una secuencia no ordenada de \( n \) enteros mediante comparaciones dos a dos, es equivalente a encontrar los \( n-1 \) que no son el máximo.

• Para "descartar" un elemento, debemos hacer al menos una comparación (para corroborar que dicho elemento es menor que algún otro).
• Si un elemento no es comparado nunca, dicho elemento podría ser el máximo.

De las premisas anteriores uno puede concluir que si cada uno de los \( n-1 \) elementos que no son el mínimo tiene que ser comparados al menos una vez para ser descartado, entonces deben realizarse al menos \( n-1 \) comparaciones para descartarlos a todos. En otras palabras, cualquier algoritmo para este problema si llama \( T(n) \) a su función de costo (número de comparaciones dependiendo de \( \red n \)), verifica \( T(n)\geq n-1 \).

Corregido es lo que está en rojo.

[cerrar]

[argentinator]

Normalmente yo hago los programas como PabloN, le pido al usuario el tamaño y los elementos del vector con el que quiera trabajar. 

Es que esto es lo correcto.

Lo que yo hacía estaba mal.

Me confié por esta razón: el nuevo estándar de C permite declarar vectores de tamaño variable.
Quise creer que esto implicaba que a partir del nuevo estándar es posible saber la longitud de un vector dentro de una función.

Incluso he visto que lo usan en algunos programas por internet.

Pero esto no funciona.
Si funciona, ha de ser por el uso de un compilador muy concreto.

[argentinator]

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...  

¿Es posible hacer eso?  

Spoiler

En general dado un problema hay muchos algoritmos que lo resuelven. Uno puede buscar algoritmos más eficientes, pero llega un cierto momento que no es posible encontrar ninguno mejor. ¿Cómo darse cuenta de que hemos llegado a este punto? De eso se encarga la ciencia que se llama Análisis de algoritmos. Cada problema tiene una complejidad mínima asociada, que en algunos casos, se puede determinar en forma teórica, de antemano, o sea, antes de buscar un método para solucionarlo. Si además se encuentra un algoritmo para ese problema que tiene la complejidad mínima, dicho algoritmo es óptimo.

En este caso, es fácil ver que no se puede hacer nada mejor que lo que hemos hecho. Fíjate que encontrar el máximo de una secuencia no ordenada de \( n \) enteros mediante comparaciones dos a dos, es equivalente a encontrar los \( n-1 \) que no son el máximo.

• Para "descartar" un elemento, debemos hacer al menos una comparación (para corroborar que dicho elemento es menor que algún otro).
• Si un elemento no es comparado nunca, dicho elemento podría ser el máximo.

De las premisas anteriores uno puede concluir que si cada uno de los \( n-1 \) elementos que no son el mínimo tiene que ser comparados al menos una vez para ser descartado, entonces deben realizarse al menos \( n-1 \) comparaciones para descartarlos a todos. En otras palabras, cualquier algoritmo para este problema si llama \( T(n) \) a su tiempo de ejecución (depende de \( n \): el número de enteros en la secuencia), verifica \( T(n)\geq n-1 \).

[cerrar]

Jejeje.

Es muy sutil, esperaba que lo vieras.

Fijate que la comparación que hice es: v[i] >= v[k].
Así, en los casos en que  v[i] == v[k] la comparación da "verdadero", y se realiza una operación de asignación: k = i.

Esto consume tiempo innecesario.

Si hacemos la comparación:  v[i] >  v[k],
nos ahorramos todas las asignaciones que surgirían de los casos  v[i] == v[k].

El programa seguiría siendo válido, porque el valor de retorno k nos da todavía un índide del vector donde está alojado el máximo del vector.

De hecho, si el máximo está repetido varias veces, cualquiera de los índices en donde se repite es válido.

________________

Si el vector fuera:

float v[] = {0.0, 1.0, 2.0, 2.0, 2.0, 2.0, 2.0, 2.0, 2.0, 2.0};

Entonces el programa realiza 10 comparaciones y 10 asignaciones con  v[i] >= v[k].
Pero con  v[i] > v[k] el programa realizar 10 comparaciones y sólo 3 asignaciones.

Si ahora la función que busca el máximo es llamado asiduamente por otro programa, el ahorro se empieza a sentir.

[argentinator]

Ah, gracias. Y qué ventajas tiene sizeof sobre length, ¿son muy distintas?

Saludos.

La ventaja es fundamental.

Por ejemplo, "length" es una palabra en inglés que sólo sirve para hacerle un conjuro al programa, y a ver si lo asustamos para que nos devuelva la longitud del vector.  

En cambio sizeof() es un operador de C que existe y funciona, dos grandes virtudes.  

Disculpá que te contesté así, me causó un poco de gracia que preguntes por una función length que no existe.

En realidad me parece que estás mezclando lenguajes de programación.
Hay muchos lenguajes que usan una función length para calcular el tamaño de los vectores.

En cambio en C esto no existe.

[pierrot]

Jejeje.

Es muy sutil, esperaba que lo vieras.

De hecho en mi programa está así  . Te lo iba a decir en mi primer post porque me extrañó ese >=, pero me limité a cambiarlo en mi código.

Igualmente con eso no disminuyes el número de comparaciones, que es la operación básica que se toma en los algoritmos de ordenación, por ejemplo. En el análisis de dichos algortimos la operación de asignación se considera despreciable.

Saludos

[argentinator]

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

En los algoritmos de ordenación consumen más trabajo que las comparaciones, porque implican un intercambio de los valores del vector.

En el ejercicio de hallar el máximo no se nota porque sólo se manejan índices, que no produce mucho costo.

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". 

[feriva]

Disculpá que te contesté así, me causó un poco de gracia que preguntes por una función length que no existe.

En realidad me parece que estás mezclando lenguajes de programación.
Hay muchos lenguajes que usan una función length para calcular el tamaño de los vectores.

En cambio en C esto no existe.

Pero si no me he enfadado es que estaba por ahí mirando cosas y por eso no he contestado.


 En cuanto a eso que estáis hablando, se me ocurre que todos los números iguales o menores que 1 son menores que cualquier entero, por lo que si el vector tiene coordenadas (al menos una) mayores que 1 en principio se podría hacer sin float, con int, para hacer una criba, y después tomar todos los que son iguales en su parte entera para distinguirlos después, ya sí, con el float. Todo depende del tipo de datos, de las componentes.

Saludos.

 

[argentinator]

Estuve comprobando el costo de las comparaciones y las asignaciones con varios tipos de datos, y obtuve estos resultados:


Midiendo costos para tipo float:

Comparaciones: 608
Asignaciones:  390

Midiendo costos para tipo int:

Comparaciones: 380
Asignaciones:  391

Midiendo costos para char[]:

Comparaciones: 5237
Asignaciones:  4960



Lo cual muestra que lo más común es que las asignaciones sean bastante costosas.

(---)

El programita que usé es éste:


#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 = 0,    y2 = 1;
  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++) {
        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++) {
        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++) {
        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;
   
}



Si lo corren tal cual, y les anda lento, bájenle un par de 0s a la constante maxj.

[argentinator]

Me llama la atención que la comparación de las dos strings se hace en tiempo muy eficiente por la función de biblioteca strcmp.

Es que definí ambas strings a propósito de modo que sea difícil para el programa distinguir cuál es la menor.

Pero no sólo las compara rápido, sino que en el camino hace un llamado a la función strcmp, con la subsecuente sobrecarga de recursos de CPU.

Pero parece que no se nota.

[argentinator]

Tenía un error en la asignacion de enteros, y me mostraba un valor erróneo.

Ahora lo corregí, y claramente el costo de tiempo de las asignaciones dependen del tamaño de los datos utilizados.

Mientras que las comparaciones parecen no sufrir ningún efecto.

(Mis comparaciones no hacía nada, por eso no tenían costo, pero tras agregar una sentencia "if" los costos de las comparaciones se notan).