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

[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

[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?

[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?

[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?

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

[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

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,

@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