Newsgroup: it.scienza.informatica
Titolo: Algoritmo "sciocco" che mi ha fatto uscire di testa

Salve a tutti,
sto elaborando un algoritmo in forma prototipale (lo scopo è segreto per 
  motivi di privacy aziendale, ma niente di assurdo, non preoccupatevi 
;-) ) e mi sono imbattutto in questo piccolo problema:
dato un vettore di interi, determinare la posizione del minimo valore in 
esso contenuto (se esiste) purche sia superiore ad un certo limite 
inferiore (lim_inf, che nel mio caso era pari a 1).
Come lo realizzereste, cercando di minimizzare il costo computazionale?
Testandolo su situazione pseudo-reali sono venute fuori un sacco di 
situazioni che non avevo previsto in fase di studio (presto sul mio 
blog... se mai troverò il tempo di scriverci qualcosa)!
Grazie,
Giulio

Giulio Petrucci ha scritto:

Ciao,
il problema mi pare abbastanza banale, nel senso che non ci sono molte 
soluzioni complesse da poter pensare; se gli inserimenti li fai volta 
volta ti basta memorizzare in una variabile separata l'indice che 
contiene il valore più piccolo prima dell'inserimento, così quando vai 
ad inserire puoi aggiornare tale variabile con l'indice del nuovo 
elemento inserito, se fosse più piccolo del minimo che avevi 
prima...esempio:
double vettore[];
int posizione_minimo, posizione_libera;
inserisci( double nuovo elemento ) {
	vettore[posizione_libera] = nuovo_elemento;
	if ( nuovo_elemento < vettore[posizione_minimo] ) 	
		posizione_minimo = posizione_libera;
	posizione_libera++;
}
Un altro modo potrebbe essere gestire il vettore in una maniera un pò 
più furba, ad esempio tramite un heap; in questo modo avresti il minimo 
in O(1) accedendo alla prima posizione del vettore, ed un costo che è 
logaritmico rispetto al numero di elementi del vettore per le operazione 
di inserimento/rimozione/aggiornamento in quanto devi ripristinare la 
condizione di heap.
Ciao, Alberto

<snip>
La soluzione migliore (che chiamo A) e' in O(n), in quanto tutti gli
elementi del vettore vanno letti almeno una volta, per conoscerne il
valore.
La soluzione di leggere i valori dal primo all'ultimo memorizzando la
posizione di quello che rispetta il tuo requisito e' quindi ottima.
Se invece devi fare piu' volte le ricerche sullo stesso vettore,
cambiando la soglia minima, posso consigliarti di (soluzione B):
- crearti un vettore di coppie (valore,posizione) 
- qsort del vettore di coppie, sul valore
- per ogni ricerca, scansione dicotonica di questo vettore creato
Quindi, per m ricerche, abbiamo questo costo:
A = m*O(n)
B = O(n) // creo il vettore di coppie
    + O(n*Log(n)) // quicksort
    + m*O(n/2) // ricerca binaria
A seconda dei valori di n ed m puo' convenire usare o l'uno o l'altro.
-- 
Andrea Rimicci

Giulio Petrucci ha scritto:

Forse c'è qualcosa che mi sfugge.
Quali sono le situazioni che non avevi previsto?
Direi che la complessità computazionale è O(n). Il vettore lo devi 
comunque scorrere tutto. E basta guardare ogni elemento una volta sola.
Una variabile "iMin" che tiene il min e una "iPos" che tiene la pos del 
min, inizializzate ai valori della prima posizione e un for che scorre 
il vettore da 2 a n con un if dentro. Se alla fine il minimo non c'è 
restituisci un valore inammissibile dell'indice (per es. < 0).
Ma è troppo semplice così, forse non ho capito qual è il problema?
-- 
TheProf
Soltanto due cose sono infinite, l'universo e la stupidità umana, e non 
sono tanto sicuro della prima.
(Albert Einstein)

 Come lo realizzereste, cercando di minimizzare il costo computazionale?
#include <limits.h>
#define lim_inf 1
int f(int *v, int size) {
   int i;
   int j = -1;
   int m = INT_MAX;
   for (i = 0; i < size; ++i) {
     if (v[i] < m && v[i] > lim_inf) {
       j = i;
       m = v[i];
     }
   }
   return j;
}
-- 
     Carlo Milanesi
 
http://digilander.libero.it/carlmila

 Ma è troppo semplice così, forse non ho capito qual è il problema?
Si, hai capito, però così facendo, se in prima posizione hai un valore 
sotto alla soglia minima ammissibile sei fregato. (la mattinata di ieri 
l'ho impiegata per capire questo). ;-)
Ciao conterraneo,
Giulio

 }
la condizione
v[i] < m
deve diventare
v[i] <= m
altrimenti se hai tutti gli elementi del vettore sotto alla soglia 
minima tranne quello massimo alla fine della scansione ti ritrovi con j 
= -1 e sei fregato (pomeriggio quasi intero di ieri per capirlo) ;-)
Ciao,
Giulio

Giulio Petrucci wrote:
 >> Giulio Petrucci wrote:
 >> dato un vettore di interi, determinare la posizione del minimo 
valore >> in esso contenuto (se esiste) purche sia superiore ad un certo 
limite >> inferiore (lim_inf, che nel mio caso era pari a 1).
 >>
 >> Come lo realizzereste, cercando di minimizzare il costo
 >> computazionale?
 >

Non direi, a meno che l'elemento massimo valga proprio INT_MAX.
Ma normalmente INT_MAX viene usato proprio per indicare un valore 
"infinito", cioe' superiore a tutti i valori ammissibili. Se e' un 
valore ammissibile, si dovrebbe specificarlo.
Per esempio, ci sono 100 elementi tutti uguali a 0 tranne il 
ventitreesimo che vale 1234.
La condizione fallisce per i primi 22 elementi, in quanto la condizione
v[i] > lim_inf
che corrisponde a
0 > 1
e' falsa.
La condizione ha successo il 23° elemento, in quanto la condizione
v[i] < m && v[i] > lim_inf
che corrisponde a
1234 < INT_MAX && 1234 > 1
e' vera.
La condizione fallisce per i successivi elementi, in quanto la condizione
v[i] > lim_inf
che corrisponde a
0 > 1
e' falsa.
Scrivendo "v[i] <= m" invece di "v[i] < m", nel caso ci sia un unico 
elemento minimo l'effetto e' lo stesso, ma se ci sono piu' elementi 
minimi, il programma risultante sarebbe leggermente meno efficiente, 
quindi non si minimizzerebbe il costo computazionale.


 "infinito", cioe' superiore a tutti i valori ammissibili.
Concentrandosi sull'algoritmo: il mio problema non prevedeva alcuna 
conoscenza "a priori" sui valori "ammissibili".
Grazie comunque per le dritte,
Giulio

errata corrige:
    + m*O(n/2) // ricerca binaria
diventa:
    + m*O(Log(n)) // ricerca binaria
...
-- 
Andrea Rimicci