Newsgroup: it.comp.lang.c
Titolo: qsort

vorrei ordinare un vettore usando la funzione di libreria qsort, ma
senza modificare il vettore dei dati ma solo un suo vettore collegato
di indici. 
In sostanza, dati v[8 4 5] e I[1 2 3] vorrei ottenere I[2 3 1].
Qualcuno mi puo' suggerire un metodo non troppo contorto?
Su Numerical Recipes trovo una implementazione particolare del metodo
quicksort, ma io vorrei usare la qsort della libreria standard.


Semplicemente modificando un po' la funzione di comparazione (per fare un esempio, invece di tornare a>b tornerà v[a]>b[b]).
Ciao!


grazie! 
 
riporto il listato della soluzione che ho trovato, con un main di
prova che mi ordina N numeri casuali.
Dato che sto imparando, ogni commento e' gradito!
 
ciao.    Mario
 
 
#include <stdio.h>
#include <stdlib.h>
 
#define N 5
 
typedef struct pair coppia;
 
struct pair
{
  float val;
  int ind;
};
 
int i;
coppia vettore[N];
 
int cmp(const void *a, const void *b)
{
    coppia primo = *(coppia *)a;
    coppia secondo = *(coppia *)b;
    if (primo.val > secondo.val) return 1;
    if (primo.val < secondo.val) return -1;
    return 0;
}
 
main()
{
    for (i =0; i <N; i++)
    {
    vettore[i].val = rand()/(float)RAND_MAX;
    vettore[i].ind = i;
    };
 
    printf ("Prima dell'ordinamento \n");
    for (i =0; i <N; i++)
        printf ("%f " , vettore[i].val);
    printf ("\n") ;
 
    qsort(vettore, N, sizeof(coppia),cmp);
 
    printf ("Dopo l'ordinamento \n");
    for (i =0; i <N; i++)
        printf ("%f " , vettore[i].val);
    printf("\n" );
 
    for (i =0; i <N; i++)
        printf ("%d " , vettore[i].ind);
 
    return 0;
}

 }
 
impara l'
 
if...else if....else
 
e cos'e' (e come si usa) l'operatore "->"
 
Ciao Jack
-- 
Yoda of Borg am I! Assimilated shall you be! Futile resistance is, hmm?

 
 
Faccio il precisino, come al solito :-)
Sicuramente l'OP ha i problemi che immagini, ma per gli altri faccio una riflessione.
In questo caso l'if/else è inutile: tendenzialmente i due casi sono equiprobabili (quindi non ci sarebbe modo di suggerire niente al branch predictor) ed il primo controllo positivo ritorna, quindi non vedo niente di male a mettere due if in fila.
Per quanto riguardo l'utilizzo dell'operatore -> sul cast dei parametri invece dell'accesso alla copia degli oggetti puntati c'è sempre il problema di ottimizzazione di copia vs. deferenziamento: in questo caso visto che si fanno solo quattro accessi in una funzione richiamata dalla qsort (e quindi tendenzialmente in un vettore situato in una zona "compatta" di memoria) tenderei anch'io ad utilizzare il -> (ma a queste cose meglio pensarci sempre quei cinque secondi in più che lasciar subito perdere).
M2C
Ciao!

lasciar subito perdere).
 
il fatto e' che la funzione cmp() e' la piu' usata di tutto l'algoritmo,
quindi l'idea e' che sia la piu' ottimizzata possibile.
Usando il -> ti risparmi l'uso delle due variabili locali primo e
secondo. Scusa se e' poco.


 
 
E' quello che cercavo di dire. Mettila così: la domanda a cui s unai dovrebbe rispondere è "è più veloce lavorare con una copia locale o con i puntatori?" In questo caso al 99% dei casi è indifferente, visto che un compilatore ad un livello decente di ottimizzazione farà caricare i due "val" in due registri indipendentemente dal codice, ma non è sempre così.
Personalmente non sono assolutamente convinto che le micro-ottimizzazioni in C siano utili; in questo caso infatti non lo sono, ma nel caso generale non si tratta di "micro": nel peggiore dei casi si rischiano varie decoerenze della cache (mamma mia, come suona brutto in italiano...) per poche operazioni d'algoritmo.
Personalmente volevo semplicemente puntualizzare che "copiare è sbagliato", nonostante quanto sia diffuso, non è un mantra realistico: ci sono casi e casi.
Ciao!

 sono casi e casi.
 
Anche perche' ottimizzare qualunque cosa senza avere chiaramente
dimostrato che quella cosa vada ottimizzata e' premature optimization.
 
Si profila, si capisce che li c'e' un problema e poi si interviene.
Altrimenti e' lavorare (e discutere) sul nulla. IMHO.
 
-- 
-riko
http://www.enrico-franchi.org/
 
http://rik0-techtemple.blogspot.com/
 

 
 
Certamente, questo fa parte delle regole del buon senso :-)
In ogni caso IMO avere un layout della memoria efficente non ritengo rientri nel campo dell'ottimizzazione, quanto più allo stesso livello della scelta adeguata di un algoritmo: uso un vettore o una tablella di hash? metto i dati in locazioni adiacenti o li tengo sparsi? secondo me siamo sullo stesso piano..
Ciao!

 siamo sullo stesso piano.. .
 
Certamente layout ed algoritmi sono legati: di fatto la scelta del
layout ti forza la scelta degli algoritmi. Il problema e' che questa e'
una cosa che fa parte dell'ottimizzazione prematura. 
 
Se il linguaggio ti *costringe* a fare la scelta presto perche' cambiare
poi e' costoso, e' un problema, essenzialmente, del linguaggio. 
 
Io sono un mezzo algoritmista come struttura. Mi sono implementato le
cose piu' esoteriche (dopo avere misurato). Ed e' stato drammaticamente
istruttivo lavorare un pochetto in Lisp. 
 
Metti come struttura di default la lista, anche per strutture dati
associative. Quindi sei in O(n) dove potresti essere O(1) ammortizzato.
All'inizio ero terrorizzato. Poi salta fuori che spesso e volentieri
l'uso tipico e' comunque scorrere la struttura per farci delle cose (e
quindi la lista va bene) e quando non lo e': (i) gli elementi sono
sufficientemente pochi da non pesare eccessivamente; (ii) gli elementi
sono tanti ma viene fatto di rado; (iii) gli elementi sono tanti ma
proprio tutto il componente e' usato raramente e non pesa nel costo
computazionale dell'applicazione.
 
Attenzione: non sto dicendo che non bisogna scegliere le strutture
opportune. Sto dicendo che sapendo quello che si sta facendo e sapendo
che lo si puo' cambiare dopo si fa meglio.


 che lo si puo' cambiare dopo si fa meglio.
 
si ok Enrico, ma nel caso specifico converrai che il mio consiglio di
usare un operatore, "->" per evitare due assegnazioni non e' che fosse
un'ottimizzazione prematura fuori di testa, era semplicemente un guarda
che invece di fare cosi, c'e' l'operatore "->" che ti rende la vita piu'
facile e il codice piu' pulito.
 
Poi sono d'accordo anch'io che prima di mettersi li a butt...ehm
investire una settimana ad ottimizzare una manciata di righe di codice
vale la pena fare un po' di profiling per vedere dove effettivamente
conviene ottimizzare.



Ho pensato un po' prima di decidere se inviare quanto ho scritto qui sotto, ma alla fine rileggendo il tutto ritengo che anche quanto dico tragga più ispirazione dal buon senso che dal mio bias.. Vi prego di leggerlo senza pregiudizi oppure di saltare direttamente alla fine per le conclusioni che di sicuro condividerete ;-)
 
Fermo restando che purtroppo il C è uno di quei linguaggi nei quali non si cambia facilmente un algoritmo con la stessa facilità con cui si fa in altri linguaggi (dove però ironicamente è più difficile se non impossibile cambiare il layout dei dati in memoria), il caso che hai proposto secondo me è un buon esempio.
Per un tipo di compito scelgo una lista invece di una tabella di hash (che so avere performance migliori). Per la maggior parte delle applicazioni non vedo problemi di performance, ma *se* questo dovesse accadere? Per prima cosa il tempo per fare il profiling necessario ad isolare il problema è tutt'altro che breve (è lecito supporre che se non ho avuto tempo di usare un algoritmo invece di un altro tantomeno ho avuto tempo di rendere il codice profiler-friendly). Una volta capito che l'algoritmo era inadatto occorre sostituirlo magari, come potrebbe succedere in C++ o in Javascript, cambiando solo un identificatore (ed io non vorrei mai essere nella situazione di dover spiegare perché ho perso un giorno di lavoro per cambiare una riga che sarebbe dovuta essere così fin dal principio, ma diciamo che non era questo il nostro caso).
Il discorso vale ancora di più per linguaggi come il C, dove solitamente per cambiare un algoritmo non basta cambiare due righe, e dove le implementazioni di algoritmi o strutture dati complesse e/o non troppo diffuse hanno un costo in termini di tempo non trascurabile (se devo perdere quattro ore a scrivere un B-tree* o quattro ore a scrivere un RB-tree, tanto vale che scelgo quello che si adatta meglio al mio problema).
Per quanto riguarda il layout in memoria, alcuni problemi semplicemente non sono profilabili, oppure è estremamente difficile farlo, come i casi in cui il collo di bottiglia sia l'invalidazione della cache (un classico esempio sono i motori 3D, dove prima del frame solitamente scorrono in un ciclo stretto un array di copie dei dati essenziali, per evitare di avere cache-miss prima/durante il rendering). Concordo con il fatto che la maggior parte dei campi dell'informatica non hanno questo tipo di problema neppure da lontano, ma per un programmatore C potrebbe non essere un caso "così" raro, visto che molti lavorano su sistemi embedded o realtime.
 
Attenzione! Non dico assolutamente che implementare->misurare->correggere_se_necessario sia errato, anzi, è l'unico modo decente di procedere in informatica! Semplicemente in generale, e questo non lo dico solo io, scegliere l'algoritmo giusto per un determinato compito (e sottolineo "scegliere", non "implementare") è quello che distingue un buon programmatore da un cattivo programmatore (in fin dei conti non è poi quello il fulcro del nostro lavoro?); un ottimo programmatore sa trovare un compromesso tra performance e tempi/costi :-)
 
Ciao!

 facile e il codice piu' pulito.
 
Non parlavo del caso specifico. Quello che io mi aspetto, nel caso
specifico, e' che un compilatore decente -- e non mi e' mai capitato di
trovarne uno che non faccia questa cosa, magari in ambito embedded e'
diverso, ma il gcc, per dire, lo fa -- faccia da solo.
 
Riformulo: sono capace *io* di scrivere un affare che faccia quel tipo
di ottimizzazione. ;) 


 
 
Probabilmente stiamo dicendo la stessa cosa. E' chiaro che uno non puo'
permettersi di sapere quali sono i problemi che ha scegliendo un array
su una mappa. E questo e' un grosso problema. Mi arriva ancora gente che
si stupisce delle varie strutture dati disponibili -- d'altra parte ci
sono interi corsi di studi che non hanno veramente un corso di algoritmi
serio --. Quello che dico io e' che spesso e volentieri conviene
scrivere la prima cosa che funziona, scrivere i test (io in realta'
prima scrivo i test, poi scrivo la prima cosa che funziona). A questo
punto quando so che il mio codice e' *corretto* -- per lo meno
ragionevolmente -- se ho un problema lo risolvo. 
 
Per me e' molto meglio accettato un codice sub-ottimale ma corretto che
uno molto veloce ma con bachi relativamente visibili. 


 
 
Sì, stiamo dicendo la stessa cosa :) E anch'io non posso che essere d'accordo sul fatto che un codice che funziona è meglio di uno che non funziona indipendentemente dalla velocità :D
 
Ti spiego solo quello che intendevo con "testabile ma non (o difficilmente) profilabile", tanto per chiudere il cerchio..
 
Come prima cosa (tanto per concordare sulla nomenclatura, ma direi che è abbastanza ovvia), intendo per test (o unit-test) gli strumenti utili a verificare la "correttezza" dell'output del codice (o di una parte di esso), e per profiling la procedura per effettuare misurazioni di performance (velocità, cicli, memoria, etc.) del codice (o di una parte di esso).
Nel caso semplice, con un codice "medio-grande", finché la granularità necessaria al profiling è maggiore o uguale a quella dei test non ci sono particolari problemi (ho 10 unit-test, posso analizzare le performance separate di 10 pezzi agilmente).
Quando devo scendere ancora (quindi profilare un pezzo più piccolo dello unit-test stesso) ho tre possibili soluzioni: scrivere un nuovo unit-test per il pezzo interessato, agganciarmi ad hook che avevo precedentemente preparato nel codice, oppure usare uno strumento di profiling avanzato che fa qualche magia a livello di linking o di sistema operativo (per esempio linkare con una diversa serie di librerie o agganciarsi a trappole del kernel). Quando i punti 1 e 2 sono non viabili a causa del tempo, rimane da vedere se lo sia il 3, e spesso non lo è a causa del cambio di behaviour della parte che non abbiamo sotto controllo, che fa cambiare o sparire la cosa che cerchiamo di profilare; purtroppo questo succede molto spesso - i problemi di cache che abbiamo citato entrambi sono un caso, ma anche tutti i codici che soffrono di problemi legati all'aggiunta o rimozione di timeouts, nonché i terribili (e maledettisimi) codici multithreaded/multiprocesso.
 
Tutto qua :-)
Ciao!

 di ottimizzazione. ;) 
 
:D
ma perche' far fare al compilatore una cosa che dovresti essere in grado
di fare tu? :P


 di fare tu? :P
 
Perche' io ho di meglio da fare... tipo fare tutte quelle cose che il
compilatore non sa fare. ;)
