2008 December » SlashCode

C/C++ – Dichiarazione Avanzata dei Tipi

Dec 102008

Questo articolo prende spunto dal corso di Ingegneria degli Algoritmi e da un articolo di Steve Friedl sulla lettura delle dichiarazione di tipo.

Uno degli scogli principali per chi comincia a programmare in C è proprio quello di comprendere bene il significato dei vari * e delle funzioni più contorte. Non è inverosimile che per i principianti si sviluppi un metodo di programmazzione chiamato “proviamo e vediamo se funziona” che consiste nell’aggiungere asterischi a caso nella dichiarazione fino a quando il programma funziona come sperato.

Ovviamente questo metodo è sconsigliabile, contando che esiste una pratica regola che rende decifrabile anche le dichiarazioni più ingarbugliate: “go right when you can, go left when you must”

Algoritmica – Ordinamento – Bubble Sort

Algoritmica 1 Response »

Dec 102008

L'algoritmo di Bubble Sorting in azione.

Insertion Sort e Selection Sort non si sono rivelati all’altezza delle nostre aspettative e noi ci ritroviamo ancora senza un algoritmo efficente per ordinare, o meglio: sappiamo ordinare le tracce di un album, oppure i CD di un apiccola collezione domestica, ma avremo molte difficoltà nell’ordinare in ordine di età gli abitanti di Roma o i volumi di un agrande biblioteca.

Dobbiamo proseguire la nostra ricerca, cambiamo approccio, questa volta il nostro tentativo cade sul Bubble Sort.

Algoritmica – Ordinamento – Selection Sort

Algoritmica No Responses »

Dec 082008

Rappresentazione grafica di un ordinamento con Selection Sort

Nell’ultimo appuntamento abbiamo visto e analizzato gli aspetti generali dell’Insertion Sort e notato che esso non è affatto un algoritmo usabile in pratica per istanze (ovvero input) molto grandi.

Ovviamente l’Insertion Sort non è l’unico algoritmo di sorting esistente. Nella nostra ricerca dell’algoritmo ottimo di sorting oggi guarderemo il Selection Sort.
Continue reading »

C -Analisi con GProf

C/C++ No Responses »

Dec 072008

Effettuare il tuning di un modulo C.

L’efficenza di un algoritmo e di un programma va affrotata in due passi: un analisi teorica dell’algoritmo e una analisi “on the road” in cui l’algoritmo va implementato e testato sulle varie architetture reali.

Ovviamente, come abbiamo avuto modo di vedere, non c’è linguaggio che possa vantare le capacità prestazionali del C, anche senza contare le capacità di interfacciarsi direttamente a basso livello con innesti di codice assembly grazie al costrutto _asm_.

Ma come tutti gli strumenti potenti vanno saputi utilizzare, molto spesso differenze impercettibili e che pensiamo irrilevanti si ripercuotono in maniera catastrofica sul nostro software. Ad esempio ho avuto modo di vedere algoritmi in cui la sola variazione di due parametri strutturali faceva passare il tempo di esecuzione da 2 minuti a 11 giorni.

E’ quindi importante identificare, in un software, quali sono le funzioni e le procedure che occupano più tempo, e quale è il loro peso nel tempo complessivo di esecuzione.

A venirci incontro è proprio GProf.