() translation by (you can also view the original English article)
Se ti dessero un foglio di carta contenente una lista di 1000 nomi, e ti chiedessero di trovare qualche nome, ma questa lista non fosse ordinata (ad esempio alfabeticamente), sarebbe un compito veramente frustante, no? Riordinare la lista per effettuare la ricerca agevolmente richiederebbe molto tempo. Avere le cose in ordine è un desiderio naturale, chiaramente con questo elenco di ricerca ci vorrebbe meno sforzo rispetto alla ricerca di un elenco non ordinato.
Passiamo al mondo dei computer dove le liste su cui effettuare la ricerca sono enormi, e dove le prestazioni potrebbero risentirne anche con computer veloci. In questo caso, usare un'appropriato algoritmo di ordinamento e ricerca, risolverebbe il problema. Mentre l'ordinamento è disporre la lista in ordine, la ricerca è il processo di estrazione della posizione di un valore all'interno della lista.
Per chiarirvi quanto questo problema così critico, vi illustrerò cosa scrisse Donald Knuth, studioso in computazione, matematica e professore emerito alla Stanford University, scrisse su The Art of Computer Programming, vol.3, Sorting and Searching, page 3:
Le industrie del computer, negli anni '60 stimarono che più del 25 % del tempo di elaborazione nei loro computer era speso ad effettuare operazioni di ordinamento, mentre tutti i loro clienti erano collegati ai loro account. In fatti, c'erano molte installazioni i cui compiti di ordinamento impiegavano più della metà del tempo complessivo di elaborazione. Da queste statistiche, possiamo concludere che o ci sono molte applicazioni che effettuano compiti di ordinamento, o molte persone non lo effettuavano oppure che gli algoritmi di ordinamento erano inefficienti.
In questo tutoria, vi illustrerò l'algoritmo di Selection Sort (ordinamento) e l'algoritmo di Linear Serach (ricerca).
Selection Sort Algorithm
L'algoritmo di Selection Sort è basato su una selezione successiva tra valori minimi e massimi. Assumiamo che abbiate una list (lista) e che vogliate ordinarla in modo crescente (dal più piccolo al più grande) L'elemento più piccolo sarà all'inizio della lista, il più grande alla fine.
Mettiamo che la lista originale sia simile a questa:
| 7 | 5 | 3.5 | 4 | 3.1 |
La prima cosa da fare è trovare il valore minimo nella lista, che nel nostro caso è 3.1
Dopo aver trovato il valore minimo, invertiamo il valore minimo con il primo elemento della lista Cioè invertiamo 3.1 con 7. La lista ora sarà:
| 3.1 | 5 | 3.5 | 4 | 7 |
Adesso siamo certi che il primo elemento è nella posizione corretta, ripetiamo i passi dell'operazione precedente (trovando il valore minimo) partendo dal secondo elemento della lista. Troviamo che il valore minimo della lista (partendo dal secondo elemento) è 3.5 . Così, invertiamo 3.5 con 5 . La lista ora sarà:
| 3.1 | 3.5 | 5 | 4 | 7 |
A questo punto, siamo certi che il primo e il secondo elemento sono nelle posizioni corrette.
Ora verifichiamo quale sia l'elemento più piccolo nella lista rimanente, partendo dal terzo elemento, ossia 5 . Il valore minimo è 4, invertiamolo con 5 . La lista diventerà:
| 3.1 | 3.5 | 4 | 5 | 7 |
Ora siamo certi che i primi tre elementi sono nella posizione corretta, continuiamo il processo in questo modo.
Vediamo come si possa implementare l'algoritmo Selection Sort in Python ( basato sul lavoro di Isai Damier):
1 |
def selectionSort(aList): |
2 |
for i in range(len(aList)): |
3 |
least = i |
4 |
for k in range(i+1, len(aList)): |
5 |
if aList[k] < aList[least]: |
6 |
least = k |
7 |
|
8 |
swap(aList, least, i) |
9 |
|
10 |
def swap(A, x, y): |
11 |
temp = A[x] |
12 |
A[x] = A[y] |
13 |
A[y] = temp |
Testiamo l'algoritmo, aggiungendo le seguenti istruzioni alla fine dello script precedente:
1 |
my_list = [5.76,4.7,25.3,4.6,32.4,55.3,52.3,7.6,7.3,86.7,43.5] |
2 |
selectionSort(my_list) |
3 |
print my_list |
In questo caso, otterremo il seguente output:
[4.6, 4.7, 5.76, 7.3, 7.6, 25.3, 32.4, 43.5, 52.3, 55.3, 86.7]
Linear Search Algorithm
L'algoritmo di Linear Search è veramente semplice; ogni elemento della lista (partendo dal primo) è controllato fino a quindo non viene trovato l'elemento richiesto, o si è raggiunta la fine della lista.
L'algoritmo di Linear Search è implementabile in Python come segue (basato su Python School):
1 |
def linearSearch(item,my_list): |
2 |
found = False |
3 |
position = 0 |
4 |
while position < len(my_list) and not found: |
5 |
if my_list[position] == item: |
6 |
found = True |
7 |
position = position + 1 |
8 |
return found |
Testiamo il codice. Inseriamo il seguente segmento di codice alla fine dello script Python:
1 |
bag = ['book','pencil','pen','note book','sharpener','rubber'] |
2 |
item = input('What item do you want to check for in the bag?') |
3 |
itemFound = linearSearch(item,bag) |
4 |
if itemFound: |
5 |
print 'Yes, the item is in the bag' |
6 |
else: |
7 |
print 'Oops, your item seems not to be in the bag' |
Quando inserisci l'input, assicurati che sia tra una coppia di apici singoli (ad esempio 'pencil'). Se inserisci 'pencil', per esempio, otterrai il seguente output:
Yes, the item is in the bag
Se usi 'ruler' come input, otterrai il seguente output:
Oops, your item seems not to be in the bag
Come possiamo vedere, Python dimostra ancora una volta di essere un linguaggio di programmazione che facilita la programmazione di algoritmi, come abbiamo appena fatto con quelli di ordinamento e di ricerca.
E' importante notare che esistono anche altri tipi di algoritmi di ordinamento e ricerca. Se vuoi cimentarti usando Python, puoi fare riferimento a questa pagina.
