Linguaggio C Costo Computazionale

[Hardcore]

Conoscete qualche sito con la tabella del costo di ogni operazione?

perke io ho dei piccoli esempi tipo :

i=3 costo 1

while (i<n) {i=i+1} costo n+n*1

ma altre cose che nn capisco tipo il costo di un printf di uno scanf , il costo di un i=o e i++ all'interno del for ecc.

plz che c'è in esame :cry:

[Kith]

ma stai parlando di tempo di calcolo?

[Hardcore]

cioè nn proprio tempo, non in secondi diciamo.

[NoeX]

penso intenda i costi computazionali che si fanno ad algoritmi o sbaglio?

[Hardcore]

Esempio piu chiaro il prof mi da un pezzo di codice, e mi chiede il costo computazionale.

tipo una funzione, il costo è il blocco della funzione , i parametri passati nn hanno costo.

un assegnamento costa 1.

un ciclo che fa i<n , costa n + 1 (n volte che controla i<n, piu la 1 volta che i=n)

[N nn viene definita, se n fosse = 3 e i=0 sarebbe 4 le 3 volte che i<n (0,1,2) e la volta che è = (3) ]

e cosi via, quello che nn riesco a capire sono i costi dei vari printf,scanf, e lavori dentro i cicli for.
se trovassi una tabella con tutti i costi :cry:

[NoeX]

scusa ma a lezione come ha spiegato quanto costa una printf per esempio ? costerà c, ovvero tempo costante...

[Hardcore]

in teoria printf scanf costerebbero 1..ma negli esercizi a volte contano a volte no...per questo cercavo se c'era una tabella con tutto scritto.

[Ercos]

e a che servirebbe sta roba? :confused:

[Axet]

Si ma tanto quello che è importante è saper calcolare il costo di un ciclo, gli altri son valori costanti.

Cmq per vedere quanto costa (ed è poi un costo costante) dovresti vedere le operazioni che fa la macchina RAM per eseguire la suddetta riga di pseudocodice.

Non ho ancora dato l'esame quindi di preciso non so, ma che io sappia non è che ci sono tabbelle dei costi lol

[Jarsil]

Qualcuno mi spiega in un linguaggio non nerdiano di che cazzo state parlando? :D

[Hardcore]

no spe nn state capendo mi sa. io parlo diciamo di esecuzione:

per esempio io so che i=0

i<n verra eseguito n volte, +1 volta che i=n quindi il costo è n+1

i=1. costo 1

cmq mi sa che vo dal prof a chiedere.

se ho un while (i<n) {i=i+2} ho n+1+n*(1) = 2n+1

non so se sono chiaro QQ

(effettivamente nn è chiaro neanche a me QQ)

[Axet]

Qualcuno mi spiega in un linguaggio non nerdiano di che cazzo state parlando? :D

Calcolo del costo di un algoritmo nel peggiore dei casi possibili (ossia tutti i cicli girano fino in fondo etc etc).. servirebbe in teoria ad ottimizzare il codice, minore il costo meglio gira l'algoritmo.

@hardcore:
guarda che stiamo parlando della stessa identica cosa.

Cmq un ciclo che va da i = 0 con la condizione i < n viene eseguito N volte, non N + 1.
Tu devi calcolare il numero di volte che il contenuto del ciclo viene ripetuto, non quante volte viene ripetuto il controllo sulla condizione (cioè N +1 volte, ma l'ultima volta non entra nel ciclo).

[Jarsil]

Calcolo del costo di un algoritmo nel peggiore dei casi possibili (ossia tutti i cicli girano fino in fondo etc etc).. servirebbe in teoria ad ottimizzare il codice, minore il costo meglio gira l'algoritmo.
@hardcore:
guarda che stiamo parlando della stessa identica cosa.
Cmq un ciclo che va da i = 0 con la condizione i < n viene eseguito N volte, non N + 1.
Tu devi calcolare il numero di volte che il contenuto del ciclo viene ripetuto, non quante volte viene ripetuto il controllo sulla condizione (cioè N +1 volte, ma l'ultima volta non entra nel ciclo).

L'ultima parte era l'unica che avevo capito anche io, dato che i<n implica che al momento in cui i=n dal ciclo si esce senza eseguirlo, quindi qualsiasi cosa sia il costo computazionale, non può influire in quel caso.

La domanda che mi pongo è: a parte l'università in cui queste cose sono ovvie e scontate... è la prima volta che ne sento parlare, mai visto applicare sto concetto nella realtà di tutti i giorni, almeno, probabilmente i programmatori lo applicano, almeno quelli bravi, ma non ho mai visto fare i calcoli di sta cosa, e non ne capisco l'utilità, dato che si tratta di calcolare un "costo" usando unità di misura teoriche e non legate alla potenza della macchina utilizzata, quindi senza un riscontro "reale" di velocità... Tuttavia, se serve a insegnare a chi programma a fare del codice ottimizzato, ben venga, è una nozione che ho imparato on the road e non sapevo fosse anche argomento di esame universitario :D

[Hardcore]

L'ultima parte era l'unica che avevo capito anche io, dato che i<n implica che al momento in cui i=n dal ciclo si esce senza eseguirlo, quindi qualsiasi cosa sia il costo computazionale, non può influire in quel caso.
La domanda che mi pongo è: a parte l'università in cui queste cose sono ovvie e scontate... è la prima volta che ne sento parlare, mai visto applicare sto concetto nella realtà di tutti i giorni, almeno, probabilmente i programmatori lo applicano, almeno quelli bravi, ma non ho mai visto fare i calcoli di sta cosa, e non ne capisco l'utilità, dato che si tratta di calcolare un "costo" usando unità di misura teoriche e non legate alla potenza della macchina utilizzata, quindi senza un riscontro "reale" di velocità... Tuttavia, se serve a insegnare a chi programma a fare del codice ottimizzato, ben venga, è una nozione che ho imparato on the road e non sapevo fosse anche argomento di esame universitario :D
essenzialmente serve a dimostrare che ci sono algoritmi validi e altri no, ci sta pure una tabellina che spiega come trovare il risultato usando due diversi algoritmi , il primo ci mette x, l'altro ci mette x^9 tempo. è da me esame di fondamenti B,non che chiusura del programma del C, :gha:

@axet: sei sicuro? mi sembra strano , dato che in teoria i<n dovrebbe essere una espr condizionale e quindi venire calcolata.

[NoeX]

"dato che si tratta di calcolare un "costo" usando unità di misura teoriche e non legate alla potenza della macchina utilizzata, quindi senza un riscontro "reale" di velocità..."

Per 'facilitare' il conto dei costi, operazioni quali printf\assegnamenti ecc vengono considerate costanti quindi O(1), che sarebbe una stima asintotica, l'utilità sta nel fatto che un algoritmo deve essere buono a prescindere dalle mole di dati in input, un algoritmo che ci mette log n per eseguire una determinata operazione e un altro che ci mette n^x fà differenza... poi ci sono altre chicche per sistemi operativi dove non devi assolutamente usare il costrutto while per eseguire il polling ma queste sono altre cose :D

[Mosaik]

Io se vuoi posso dirti quando e' il "Costo" di incazzature di un prof quando gli parli di GO TO..

Auahauha mi divertivo troppo a farli sbroccare :rotfl:

[Jarsil]

@axet: sei sicuro? mi sembra strano , dato che in teoria i<n dovrebbe essere una espr condizionale e quindi venire calcolata.

Cos'è che fa "aumentare" il costo? il fatto che esegua il ciclo o che verifichi se deve o meno essere eseguito? (madò mi intrippano ste cose, mi sono ricordato perché ho deciso di NON fare ingegneria ;)

Nel primo caso, con la condizione i<n al momento dell'uguaglianza il ciclo non viene eseguito quindi non aumenta, nel secondo caso (ovvero basta che il ciclo "controlli" se deve o meno girare per fare aumentare il costo) hai ragione tu...

Fin qui è logica quasi elementare :)

[Hardcore]

Cos'è che fa "aumentare" il costo? il fatto che esegua il ciclo o che verifichi se deve o meno essere eseguito? (madò mi intrippano ste cose, mi sono ricordato perché ho deciso di NON fare ingegneria ;)
Nel primo caso, con la condizione i<n al momento dell'uguaglianza il ciclo non viene eseguito quindi non aumenta, nel secondo caso (ovvero basta che il ciclo "controlli" se deve o meno girare per fare aumentare il costo) hai ragione tu...
Fin qui è logica quasi elementare :)
essenzialmente è Cost di controllo del ciclo + Costo di esecuzione di quello che c'è nel ciclo. quindi se il ciclo lo si ripete n volte, ed esegue operazioni che costano 3, hai un costo di esecuzione del ciclo = 3n + costo di controllo = n+1.

[Hador]

Cos'è che fa "aumentare" il costo? il fatto che esegua il ciclo o che verifichi se deve o meno essere eseguito? (madò mi intrippano ste cose, mi sono ricordato perché ho deciso di NON fare ingegneria ;)
Nel primo caso, con la condizione i<n al momento dell'uguaglianza il ciclo non viene eseguito quindi non aumenta, nel secondo caso (ovvero basta che il ciclo "controlli" se deve o meno girare per fare aumentare il costo) hai ragione tu...
Fin qui è logica quasi elementare :)
while (i<n) {
i=i+2
}
il "costo computazionale" è la stima asintotica (una approssimazione quindi) della somma di tutte le operazioni che fa un programma, ovviamente in un esempio base come questo si ridurrà a calcolare quante volte il ciclo while esegue quella operazione, di costo, approssimato, O1 (O grande, li stessi di taylor :nod: ).
L'esercizio ha un ottimo modo di risoluzione, quello di infilarci valori a cazzo ed estrarne una equazione generalizzata
ponendo esempio i=0 e n=5 quanti cicli farà?
parte con 0, nel primo ciclo i=2, nel secondo i=4, nel terzo i=6 poi si ferma, il tempo di calcolo di sta minchiata è n/2+1 quindi On/2, deducibile pure dal fatto che se
while(i<n) {
i=i++ (o i = i+1 che dir si voglia)
}
ha tempo On nel momento in cui raddoppio la crescita di i diminuirà il tempo di esecuzione :p


Il senso di ste cose sta nello studio degli algorirmi, l'esempio classico del cazzo sono gli algoritmi di ordinamento, devo ordinare 4 3 5 1 2 come faccio?
Potrei prendere il 4 e confrontarlo con tutti e metterlo nella posizione adeguata rispetto a cosa mi viene fuori, ma confronterei 5 numeri per 5 volte, avrei quindi un tempo di calcolo esponenziale n^n, se dovessi ordinare una stringa di diecimila milioni di numeri verrebbe fuori un bel tempo di calcolo (con un vecchissimo processore :p) - di conseguenza si studiano altre soluzioni, iterative e ricorsive, per ottimizzare il tempo di calcolo, in questo caso con il merge sort sfruttanto il divide et impera.

- dimenticavo il "axet sei una capra", ha ragione lui, solo che tu nell'esame lo hai già approssimato con On :nod:

[Helrohir]

invece di fa il saputello vai a studiare il tuo di esame :sneer:

[Hador]

quale dei 4? QQ

[Axet]

Anch'io settimana prossima ho 4 parziali..

Analisi, Algoritmi, l'ultimo di Architettura 2 e basi di dati.
Hador ma algoritmi e basi di dati li fanno insieme o son due esami separati? :look:

Btw io mi riferivo al fatto che il codice contenuto nel ciclo viene eseguito n volte, mentre la condizione n + 1.. forse non son stato chiaro o non ho capito la domanda, cmq il costo di quell'algoritmo è 2n + 1 dato da:

n + 1 che sono le volte che la condizione del ciclo si ripete
n che è il numero di volte che si ripete il codice nel ciclo

Essenzialmente assegnamo un costo costante alle operazioni basilare, cmq lavorando sulla macchina RAM (che non è la ram che si intende normalmente ma non mi ricordo al momento di cosa è l'acronimo) si può capire nel dettaglio il costo di ogni operazione guardando a livello macchina ogni istruzione quante operazioni comporta (una specie di assembler :look:).

Però è tendenzialmente inutile perchè il calcolo non viene eseguito nel dettaglio e per comodità, appunto come diceva hador, alle costanti viene assegnato costo 1.

Il fatto che sia in C piuttosto che in Java non importa, almeno per come lo stiamo studiando noi, poichè cmq ti basi sullo pseudo-codice.

@jarsil:
non è ingengeria questa, è informatica :nod:

[Hador]

separati, se ti servono ripetizioni dimmelo :sneer:
spero cmq ti sia farcito la cartella del lab di esempi almeno riesci a fare algoritmi nell'ora di tempo :nod:

cmq è tutta approssimazione, teoricamente guardi quante volte fa il controllo ma di fatto tu guardi la funzione asintotica, quindi addizioni e sottrazioni (tralaslazioni della stessa) nn ti cambiano un cazzo la pendenza della funzione resta sempre la stessa


ah nn ho 4 parziali, ho 2 parziali e 2 esami è_é
tra i quali SISTEMI OPERATIVI - PARADIGMI CONCORRENTI E DISTRIBUITI, detto anche l'INCUBO. :nod:

[Jarsil]

@jarsil:
non è ingengeria questa, è informatica :nod:

Bah, questa è materia anfibia galleggiante comunemente detta merda, che altro non è che un sinonimo di Matematica.

Sarà che per me informatica = pratica, non teoria, ma che ci vuoi fare, non è un caso se faccio il sistemista e non il programmatore, io i problemi li risolvo, non li studio :D

[Hador]

Bah, questa è materia anfibia galleggiante comunemente detta merda, che altro non è che un sinonimo di Matematica.
Sarà che per me informatica = pratica, non teoria, ma che ci vuoi fare, non è un caso se faccio il sistemista e non il programmatore, io i problemi li risolvo, non li studio :Dil problema è che se li risolvi di merda nn è che serva poi a molto

[Axet]

separati, se ti servono ripetizioni dimmelo :sneer:
spero cmq ti sia farcito la cartella del lab di esempi almeno riesci a fare algoritmi nell'ora di tempo :nod:
cmq è tutta approssimazione, teoricamente guardi quante volte fa il controllo ma di fatto tu guardi la funzione asintotica, quindi addizioni e sottrazioni (tralaslazioni della stessa) nn ti cambiano un cazzo la pendenza della funzione resta sempre la stessa
ah nn ho 4 parziali, ho 2 parziali e 2 esami è_é
tra i quali SISTEMI OPERATIVI - PARADIGMI CONCORRENTI E DISTRIBUITI, detto anche l'INCUBO. :nod:

Son separati, il che vuol dire che ho 3 parziali consecutivi in un giorno.. :faccinachesisparaintesta:

Per tutto quello che ruota attorno all'informatica non ho problemi, più che altro mi servirebbero davvero delle ripetizioni di analisi che non so NULLA.
E quando dico nulla intendo nulla :rain:

In laboratorio gli esercizi manco li ho toccati, ho fatto i quiz ho avuto ottimi risultati e son felice.. voglia di fare pure gli esercizi = 0, al solito mi metterò a farli il giorno prima dell'esame -.-

@jars:
Che matematica = merda siam d'accordo, ma questa è informatica che si avvale dell'aiuto di matematica >_<

[Hador]

(era per jarsil)
prima che si arrabbi :sneer:
il che nn è un accusa, ma parlare di informatica è come parlare di matematica, comprende tutto e niente.
Per gestire una rete, scrivere programmini per aziende, gestire database, lavorare sul web eccetera tutta sta roba nn ti serve a un cazzo, ma son cose che stanno alla base di qualsiasi minchiata chiedi di fare a un programma, come l'ordinare una stringa.
La lezioncina sui tempi di calcolo è di fatto una minchiata sulla quale spendono 1 ora di lezione, ma serve a spiegare perchè convenga usare un metodo invece che un altro, tutti sono capaci di scrivere un programma in pseudo codice, intuitivo, per ordinare una stringa di numeri. Quanti però lo scrivono nel modo più ottimizzato possibile? :p

axet
si ma con la teoria ci pigli 15, ma che parziale è? se il primo ok la teoria è una minchiata (preso 30 :|), anche nel terzo... il secondo ha una teoria impossibile :nod:

[Axet]

Primo parziale, e poi mica ho detto che non so fare la pratica, ho detto che non avevo voglia di fare gli esercizi, è diverso :D

Cmq non cambiare discorso, come vai in analisi? :nod:

[Hador]

15 nei parziali, 21 con l'orale :nod:
alla 2 dio caro mi ha sturato al secondo parziale, ho sbagliato un cristo di segno e mi ha dato 2 punti in un esercizio invece che 12 tipo -_-
ma in 1 settimana è dura :nod:

[Axet]

Ok sono fottuto :rain:

Il punto non è tanto analisi in sè, quanto che mi mancano le basi perchè alle superiori non ho mai seguito mate QQ

Vabbè troverò una soluzione, al massimo dò l'esame completo tra qualche mese :nod:

[Jarsil]

(era per jarsil)
prima che si arrabbi :sneer:
il che nn è un accusa, ma parlare di informatica è come parlare di matematica, comprende tutto e niente.
Per gestire una rete, scrivere programmini per aziende, gestire database, lavorare sul web eccetera tutta sta roba nn ti serve a un cazzo, ma son cose che stanno alla base di qualsiasi minchiata chiedi di fare a un programma, come l'ordinare una stringa.
La lezioncina sui tempi di calcolo è di fatto una minchiata sulla quale spendono 1 ora di lezione, ma serve a spiegare perchè convenga usare un metodo invece che un altro, tutti sono capaci di scrivere un programma in pseudo codice, intuitivo, per ordinare una stringa di numeri. Quanti però lo scrivono nel modo più ottimizzato possibile? :p


Ma certo che serve la teoria che c'è dietro....

Ma a me basta conoscere il nesso causa-effetto per sapere cosa fare nel mondo dell'informatica, non devo ognivolta reinventare la ruota, se dietro al funzionamento del pc c'è una sterminata teoria matematica, non è un mio problema, come non lo è del mio cliente ;)

(Ti perdono il risolverere di merda solo perché poi hai chiarito un po' il punto, altrimenti eri un uomo morto, non si dice una cosa simile a uno che nell'arco della giornata ha battuto il suo record personale di installazioni e configurazioni di server da spedire ai clienti, 7 macchine partite da 0 e configurate al 100%...)

[Ercos]

Bah, questa è materia anfibia galleggiante comunemente detta merda, che altro non è che un sinonimo di Matematica.
Sarà che per me informatica = pratica, non teoria, ma che ci vuoi fare, non è un caso se faccio il sistemista e non il programmatore, io i problemi li risolvo, non li studio :D


:bow:

[Hador]

Ma certo che serve la teoria che c'è dietro....
Ma a me basta conoscere il nesso causa-effetto per sapere cosa fare nel mondo dell'informatica, non devo ognivolta reinventare la ruota, se dietro al funzionamento del pc c'è una sterminata teoria matematica, non è un mio problema, come non lo è del mio cliente ;)
(Ti perdono il risolverere di merda solo perché poi hai chiarito un po' il punto, altrimenti eri un uomo morto, non si dice una cosa simile a uno che nell'arco della giornata ha battuto il suo record personale di installazioni e configurazioni di server da spedire ai clienti, 7 macchine partite da 0 e configurate al 100%...)si quello che volevo far passare è che finchè sistemi un server nn servono a un cazzo, ma informatica comprende anche altro, se devi scrivere un programma che coordina i movimenti di un braccio meccanico o che simuli i comportamenti fisici di un oggetto in un certo stato cose del genere ti servono.
Cioè si studiano cose inutili in facoltà, assembler, LISP, PROLOG, ma algoritmi è proprio un corso ben fatto :p
nella mia e di axet università i primi 2 anni sono generali, il terzo è già molto specifico sulla branca dell'informatica alla quale uno vuole dedicarsi (che poi prosegue nella specialistica).

[Ercos]

Assembler può essere utile :sneer:

[Hardcore]

solo da me si fa C e java al primo :look: ?

[Ercos]

si vede che voi siete avanti, e nn danno peso ai linguaggi di basso livello (e fan anche bene ghhg)

[Hardcore]

@axet : spiegami una cosa plz:

se ho while (i<=n) esegue n+1 volte il controllo e n volte il ciclo

se ho while (i<n) esegue n volta il controllo e n-1 volte il ciclo?

e col for?

se ho for (i=0;i<=n;i++) praticamente nn dovrebbe essere 1+n+1+n*(1) ?

1(i=0)+n+1(il i<=n)+n(volte che esegue il ciclo for)*1 (i++) ?

[Kith]

algoritmi == la materia più inutile dopo linguaggi di programmazione all'uni.

meno male che il primo l'ho passato :\

[ihc'naib]

@axet : spiegami una cosa plz:
se ho while (i<=n) esegue n+1 volte il controllo e n volte il ciclo
se ho while (i<n) esegue n volta il controllo e n-1 volte il ciclo?


Guarda, piu' o meno era gia' nascosto in un consiglio di Hador, ma ti ribadisco un consiglio utile in queste questioni. In genere il rischio e', come hai visto, sempre quello dell'errore di 1.
Per risolverlo, quindi, ti basta fare una prova con un ciclo cortissimo(non trovo le graffe su questa tastiera):

i=0;
while(i<=2)
[ BLABLABLABLA;
i++;]



Il ciclo viene controllato per i=0, i=1; i=2; i=3; ed eseguito per i=0,1,2.
Dunque, la condizione di terminazione viene verificata 4 volte (n+2) e il contenuto del ciclo eseguito 3 volte (n+1)

E' per questo che in genere i cicli si controllano con il minore secco, e non con il minore/uguale.. in quel modo se scrivi while(i<n) ti _esegue_ il ciclo n volte.



e col for?
se ho for (i=0;i<=n;i++) praticamente nn dovrebbe essere 1+n+1+n*(1) ?
1(i=0)+n+1(il i<=n)+n(volte che esegue il ciclo for)*1 (i++) ?

Il for e' solo un while rigirato, vale lo stesso discorso:

quel ciclo for li' fa il controllo per n+2 volte (se includi il primo controllo, che fa parte dell'inizializzazione del for) e esegue il suo contenuto n+1 volte.
Ricordati sempre che quando la variabile di controllo e' 0 il ciclo viene eseguito.
e' l'errore degli anni di cristo (se e' morto nel 33 d.C., allora e' morto a 32 anni), o dei secoli (Xv secolo=1400).. e' sempre lo stesso.

[Hardcore]

penso di amarti.:kiss: :kiss:

[Axet]

Ha ragione ihc, ma devi considerare che il numero di volte che il ciclo gira dipende sempre da come inizializzi la variabile.

Se all'inizio dell'esecuzione i = 0
while (i < n) allora la condizione verrà eseguita N + 1 volte e il contenuto del ciclo N volte.

Ma ovviamente se all'inizio hai i = 1, allora la condizione while (i < n) verrà eseguita N volte e il contenuto del ciclo N - 1 volte.

Stesso discorso per il for, è identico al while da questo punto di vista :p

[San Vegeta]

algoritmi == la materia più inutile dopo linguaggi di programmazione all'uni.

meno male che il primo l'ho passato :\

infatti la gente che non conosce gli algoritmi non sa capire la differenza tra le varie implementazioni dell'interfaccia Map e fa le meglio puttanate, dall'usare 3 diversi tipi di collection (ognuno allocato dinamicamente e riempito a runtime) per fare una semplice ricerca all'interno della collezione di oggetti al mischiare algoritmi di ricerca lineare con strutture dati ad albero (oVVoVe)
Oppure usano una ricerca che pesa o(n^2) su milioni di record e poi si sorprendono perchè l'applicazione "si blocca".

come disse il mio prof di linguaggi, usare il bucket sort durante il servizio militare/civile per ordinare le scartoffie vi regala mezza giornata di cazzeggio e vi fa fare la figura del genio davanti agli altri.
non per altro, io in 1 ora ordinavo metà archivio e poi dormivo.

[Hador]

si cmq avevo già risposto io perchè nn mi ha cagato è_é

[Hardcore]

si cmq avevo già risposto io perchè nn mi ha cagato è_é
la cosa gli O nn la capisco QQ

in teoria nn è f(n)=O(g(n)) cioè la funzione f(n) è dello stesso ordine di g(n) ? e se anche fosse io che ci ricavo?

[Hador]

è la funzione asintotica che determina la velocità di crescita di una funzione (in un punto).
ci ricavi che capire cosa si sta facendo nn fa mai male, poi nn so quanto il tuo corso prosegui, ma i concetti degli O ti arriveranno a preve... on, On, ologn Onlogn n^2logn, log2 ecc...