Newsgroup: it.comp.lang.c
Titolo: medio tra elementi di un vettore

Salve a tutti.
Come posso implementare un funzione che dato un vettore di n interi
calcoli il valore medio tra tutti?
Non devo calcolare la media, ma l'intero medio: questa cosa mi crea
qualche problema. Avevo pensato di sommare tutti gli elementi dividere
per il loro numero e verificare qual era l'intero che si avvicinava di
più a questo valore. Ma come posso implementare una cosa di questo
tipo?
Grazie a tutti.


Dovresti definire meglio il tuo problema:
cosa intendi, precisamente, quando dici
 > Non devo calcolare la media, ma l'intero medio...
"L'intero medio" non e' una definizione precisa.
Vuoi forse trovare il valore intero X (presente nel vettore),
tale che, se ordiniamo tutti i numeri del vettore, allora
esattamente meta' sono piu' piccoli di X e meta' piu' grandi di X
(+1 o -1 a seconda della parita' del numero n)  ?
ciao,
g.

 tipo?
Beh, allora cambio idea ed incomincio a pensare che tu intenda la seconda
interpretazione.....
Beh, semplice... ma visto che hai dei problemi a farlo da solo descrivo il
metodo piu' semplice anche se non e' tanto performante....
sommi tutti i numeri, dividi per il numero degli elementi dell'array ed
ottieni la media matematica. Arrotonda questo valore ad un intero (es
75.8 -> 76; 75.4 -> 75). Calcoli la distanza del primo elemento dell'array
dal valore medio trovato e salvi da qualche parte la distanza e anche
l'indice dell'elemento.
Fatto questo riscorri tutto l'arrray calcolando la distanza di ogni singolo
elemento dal valore intero trovato usando la media matematica. Ogni volta
che trovi (se lo trovi) un elemento che ha distanza minore di quella
attualmente salvata aggiorni i due dati (distanza/elemento).
Alla fine non te ne fai molto della distanza, ma dell'elemento si...
quell'elemento e' quello piu' vicino ( il 75 del secondo esempio!).
Il problema della seconda interpretazione (e della implementazione appena
suggerita), performance a parte, e' evidente nel caso di ad esempio ...
centomila numeri da zero ad un miliardo. Avresti dei problemi a calcolare la
media matematica con numeri a 32 bits ;-) (sommali tutti e con grande
probabilita' vai in overflow). Se e' questo che devi fare e su array
"grandi" con numeri "grandi" bisogna quindi adottare una delle possibili
soluzioni.
Insomma, prima di andare avanti con argomenti non chiari... cerchiamo di
chiarire cosa vuoi e/o devi fare!
Domanda dovuta... tu questo almeno lo sai o non sai nemmeno questo?
Tommy

Domanda dovuta... tu questo almeno lo sai o non sai nemmeno questo?
Quello che devo fare lo so con certezza (almeno questo!).
Mi spiego meglio. 
Il problema mi si pone in circostanze ben precise. Sto facendo un
progetto sull'algoritmo del quicksort. Devo modificare la strategia di
scelta del pivot. Tra le varie scelte il testo (in inglese) dice di
scegliere il pivot come: " the average of all keys in the set".
Dal momento che il mio "set" è un vettore, l'interpretazione mia e
quella del mio docente è stata quella di cui sopra.
Spero di essere stato un po' più chiaro.
Grazie dell'aiuto che mi state dando.
Tommaso

Chiedo scusa, avevo postato con l'oggetto sbagliato.


 sommando gli n elementi e dividendo poi per n non è da poco.
La maggior parte dei compilatori (o almeno il gcc sotto linux e il
borland sotto win)
contempla un tipo di dato intero a 64 bit (tipo unsigned long long int
per il gcc e non mi ricordo come per il borland, qualcosa tipo uint64).
Siccome e' abbastanza improbabile che tu debba avere piu' di
2^(32) chiavi, dovrebbe bastare....
per esempio potresti fare (in gcc), supponendo che le chiavi
siano unsigned int
unsigned int Media,diff,t;
int quale;
unsigned long long int Acc = 0;
for (i=0; i<numero_chiavi; i++) Acc+=Key[i];
Media = (unsigned int) (Acc/numero_chiavi);
diff=0xFFFFFFFFU;
quale =0;
for (i=0; diff!=0 && i<numero_chiavi; i++)
{
    t = (Media>=Key[i] ? Media-Key[i] : Key[i]-Media);
    if (t<diff) {diff=t; quale=i;}
}
Dovrebbe funzionare ed e' proprio elementare.
ciao,
g.

 scelta del pivot.
ARGHH!
Il quicksort ha tempo n*log n... se tu per ogni volta che che devi scegliere
un pivot vuoi usare quello piu' vicino alla media matematica, allora ogni
volta dovrai scorrere tutto l'array... In pratica diventa molto piu' lento,
non cambia ordine di grandezza, ma rallenta molto!
Il quicksort, al contrario del mergesort non e' perfetto in questo senso
(non e'  sempre n*log n, anzi...), ma e' ugualmente piu' veloce (in genere)
in quanto riesce a ordinare in situ e con poco sforzo. Se pero' ogni volta
vuoi trovare la media lo appesantisci parecchio....
Il problema e' che se questa operazione ti garantisse di dividere a "meta'"
allora forse ne trarreste anche vantaggi, ma questa tecnica non garantisce
NULLA:
9 4 3 8 6 7 5 4 2 6 1000 33 12
Ecco la media e': 84.5
il piu' vicino e' 33:
9 4 3 8 6 7 5 4 2 6 12
33 1000 (se mettiamo il 33 di qua!)
In pratica non ha per nulla diviso in parti eguali! (la prima parte ha 11
elementi la seconda 2).
A mio avviso il costo di tale operazione (n come ordine di grandezza) non e'
giustificato. I benefici NON sono evidenti!
Forse con un piu' semplice "median of 3" (molto impreciso anch'esso)
raggiungi gli stessi risultati con costi molto inferiori.
Poi il median of 3 e' il piu' semplice, sappiamo tutti che non e' certo il
migliore...
Tommy

Non capisco cosa tu pretendessi!
Non pretendo niente. Ma di un "quasi codice" il compilatore se ne fa
poco.

So benissimo che la modifica di scelta del pivot comporta un notevole
rallaentamento del running time.
Vedi, qui il problema non è quello di rendere il più possibile
efficente l'algoritmo, ma di studiarne il comportamento nelle diverse
situazioni.
E' ovvio che se devo utilizzare il quicksort con lo scopo di
ottimizzare il running time non utilizzerò questo tipo di scelta del
pivot.
Il median of three è un'altra delle tecniche che mi viene richiesto di
analizzare, ma nell'implementazione non ho avuto problemi.
Grazie per i suggerimenti.
A presto.
Tommaso

 Tommaso
Bumulo (Tommy)
P.S. anchio mi chiamo Tommy (e non è un diminutivo...) ma non sono quello
che posta per la maggiore....


Ciao e innanzitutto grazie per l'aiuto.
Scusa l'ignoranza ma cosa significa 
diff=0xFFFFFFFFU        ????
Grazie ancora!
Ciao 
Tommaso

 Tommaso
si informa il compilatore che il numero che segue
e' espresso in esadecimale premettendo 0x (zero ics).
si informa il compilatore che il numero deve essere inteso
come UNSIGNED posponendo una U. (probabilmente non era necessario)
Quindi 0xFFFFFFFFU e' il piu' grande numero intero
unsigned a 32 bit (cioe' sono 32 bit tutti a 1).
ciao,
g.

 situazioni.
Ok, allora bene, procedi.
Tommy

ma io speravo  che te ne facessi qualche cosa tu ;-)
Fino al quasi codice faccio da solo!!! Grazie comunque per l'aiuto.

hannibal wrote:
intanto hai riutilizzato in modo errato le poche righe di codice che ti
avevo inviato.
porre diff=0xFFFFFFFFU; aveva un senso nel mio esempio, dove si assumeva 
che diff fosse un "unsigned int". Qui invece e' sbagliatissimo perche'
hai definito diff come "int".
Di fatto diff=0xFFFFFFFFU; pone diff uguale a -1 .... quindi poi
non riesci mai ad andare sotto diff.... e ritorna sempre key=0 !!
 > Faccio un esempio:
 > Ammettiamo che nel vettore siano presenti gli interi 7 e 8. Facendo la
 > divisione intera non riesco a scegliere 7 nel caso media<=7.4 o 8
 > altrimenti. Come posso risolvere? Grazie
Accumula in un double invece che in un int (anche per ovviare a problemi
di overflow se hai tanti numeri molto grandi).
oppure converti in double prima di fare la divisione:
double media;
media = ((double)somma)/n;
g.

media = ((double)somma)/n;
Il mio codice è questo:
int pivot_medio (int *a, int n)
{
        int diff, t, key, i,somma;
        double media;
        somma=0;
        for (i=0; i<n; i++)
                somma=somma+a[i];
        media = ((double)somma/n);
        printf("Media del vettore: %d\n\n", media);
        diff=100000000000;
        key=0;
        for (i=0; diff!=0 && i<n; i++)
        {
        if (media>a[i]) t = media-a[i];
        else t = a[i]-media;
        if (t<diff)
        {
                diff=t;
                key=a[i];
        }
        }
        return key;
}
Il mio vettore è questo:
a[10] = { 1, 11, 4, 14, 5, 12, 9, 13, 7, 8}
La media è 8.4 quindi la chiave scelta dovrebbe essere 8, invece viene
scelto 9.
Come posso fare?
Grazie ancora.

 Come posso fare?
Avrebbe dovuto essere ovvio che in questo caso
anche diff e t devono essere  dei double...  altrimenti
come discrimini fra una differenza 0.4 e una 0.6 se entrambe,
una volta assegnate all'intero t o a diff, valgono 0 ?
ciao,
g.


Effettivamente è abbastanza ovvio! Fatto e adesso funziona.
Grazie dell'aiuto e della pazienza.
Ciao

 Come posso fare?
Giovanni ti ha detto di avere diff come double.... e' vero funziona, ma io
farei in un altro modo:
QUELLO DEL SOLITO QUASI CODICE DA TE CRITICATO:
<QUOTE>
Arrotonda questo valore ad un intero (es 75.8 -> 76; 75.4 -> 75).
<QUOTE>
In pratica puoi tenere diff come intero, visto che il tuo array e' di SOLI
interi (da quanto mi hai detto).
Siccome 8.4 viene arrotondato come 8 (nel metodo descritto) viene scelto 8 e
non 9. Se fosse 8.6 verrebbe arrotondato a 9 e verrebbe quindi scelto 9.
Resta il problema del 8.5, devi decidere se farlo diventare 8 o 9. D'altro
canto il problema rimane anche con il metodo di Giovanni, visto che la
distanza in entrambi i casi e' 0.5.
Ad ogni modo forse ti risulta piu' semplice ignorare il mio metodo ed usare
quello di Giovanni. Quello che ci tengo a dire e' che pero' la soluzione era
gia' presente nel quasi "codice" che tu hai sfottuto tanto ;-)
Buon proseguimento.
Tommy

 quello di Giovanni.
Credo che la soluzione di Giovanni nel caso del 8.5 sia molto meno
problematica ;-)
Lascia stare la mia... vai per quella di Giovanni.
Tommy

gia' presente nel quasi "codice" che tu hai sfottuto tanto ;-)
Se hai interpretato il tono delle mie risposte come una presa in giro
o in qualche modo offensifo ti faccio le mie scuse.
Non era mia intenzione "sfottere" nessuno.
Tu hai dato risposte corrette e pertinenti, ma che non mi hanno dato
nuove informazioni. Tutto qui.
Spero di aver chiarito. In caso contrario fammi sapere dove sta
l'equivoco.
Grazie in ogni caso.
Ciao
Tommaso

 non avrò di certo un numero più alto.
No, hai sbagliato di nuovo, bisogna che tu ti ripassi
1) La rappresentazione in base 2
2) i tipi di dati fondamentali del C
un numero binario "unsigned" a K bit NON puo' contenere il numero 2^K,
in quanto puo' rappresentare solo i numeri tra 0 e (2^K)-1.
Per esempio con 8 bit rappresenti i numeri da 1 a 255.
Se poi il numero e' "signed" (come e' il tipo di dato int)
allora il numero e' rappresentato in complemento a 2 e in pratica
perdi circa un bit, quindi il massimo numero rappresentabile e'
generalmente 2^(K-1)-1. (Ovvero 2^31-1 = 
2147483647
)
Quindi nel tuo caso assegnare 2^(32) ad un int e' errato.
(La soluzione di assegnare a diff la prima differenza con la
media, suggerita da Tommy, e' in effetti quella piu' ragionevole,
io non l'avevo considerata per pigrizia.)
ciao,
g.

 l'equivoco.
Ok, non importa.
Chiudiamo questo botta riposta che ora e' diventato inutile.
Tommy