Alcuni esempi di brevi programmi per affrontare problemi che si incontrano sovente nella pratica. Possono servire di ispirazione per ulteriori esplorazioni di algoritmi in Python.
Come esempio, calcoliamo la somma dei numeri pari in modi diversi. Notate la definizione di funzioni seguite dal test dopo:
if __name__ == "__main__":.
def compute_sum1(n):
"""computes and returns the sum of 2,4,6, ..., m
where m is the largest even number smaller than n.
For example, with n = 7, we compute 0 + 2 + 4 + 6 = 12.
With n = 6, we compute 0 + 2 + 4 = 6.
Start from 0 to account for n ≤ 2.
This implementation uses a variable 'mysum' that is
increased in every iteration of the for-loop."""
mysum = 0
for i in range(0, n, 2):
mysum = mysum + i
return mysum
def compute_sum2(n):
"""computes and returns ...
This implementation uses a while-loop:
"""
counter = 0
mysum = 0
while counter < n:
mysum = mysum + counter
counter = counter + 2
return mysum
def compute_sum3(n, startfrom=0):
"""computes and returns ...
Slightly more general:
Calling compute_sum3(7,4) we compute 4 + 6 = 10
This is a recursive implementation:"""
if n <= startfrom:
return 0
else:
return startfrom + compute_sum3(n, startfrom + 2)
def compute_sum4a(n):
"""A functional approach ... this seems to be
the shortest and most concise code.
"""
return sum(range(0, n, 2))
from functools import reduce
def compute_sum4b(n):
"""A functional approach ... not making use of 'sum' which
happens to exist and is of course convenient here.
"""
return reduce(lambda a, b: a + b, range(0, n, 2))
def compute_sum4c(n):
"""A functional approach ... a bit faster than compute_sum4b
as we avoid using lambda.
"""
import operator
return reduce(operator.__add__, range(0, n, 2))
def compute_sum4d(n):
"""Using list comprehension."""
return sum([k for k in range(0, n, 2)])
def compute_sum4e(n):
"""Using another variation of list comprehension."""
return sum([k for k in range(0, n) if k % 2 == 0])
def compute_sum5(n):
"""Using numerical python (numpy). This is very fast
(but would only pay off if n >> 10)."""
import numpy
return numpy.sum(2 * numpy.arange(0, (n + 1) // 2))
def test_consistency():
"""Check that all compute_sum?? functions in this file produce
the same answer for all n>=2 and <N.
"""
def check_one_n(n):
"""Compare the output of compute_sum1 with all other functions
for a given n>=2. Raise AssertionError if outputs disagree."""
funcs = [compute_sum1, compute_sum2, compute_sum3,
compute_sum4a, compute_sum4b, compute_sum4c,
compute_sum4d, compute_sum4e, compute_sum5]
ans1 = compute_sum1(n)
for f in funcs[1:]:
assert ans1 == f(n), "%s(n)=%d not the same as %s(n)=%d " \
% (funcs[0], funcs[0](n), f, f(n))
#main testing loop in test_consistency function
for n in range(2, 1000):
check_one_n(n)
if __name__ == "__main__":
m = 7
correct_result = 12
thisresult = compute_sum1(m)
print("compute_sum1 result is {}, expected to be {}".format(
thisresult, correct_result))
# compare with correct result
assert thisresult == correct_result
# also check all other methods
assert compute_sum2(m) == correct_result
assert compute_sum3(m) == correct_result
assert compute_sum4a(m) == correct_result
assert compute_sum4b(m) == correct_result
assert compute_sum4c(m) == correct_result
assert compute_sum4d(m) == correct_result
assert compute_sum4e(m) == correct_result
assert compute_sum5(m) == correct_result
# a more systematic check for many values
test_consistency()
compute_sum3(10, 4)
Tutte le implementazioni viste sopra danno lo stesso risultato. Alcune lezioni da apprendere:
Ci sono molte soluzioni (probabilmente infinite) ad un problema dato: questo significa che programmare richiede creatività.
Le diverse soluzioni possono ottenere lo stesso "risultato", in questo caso il calcolo di un numero.
Soluzioni diverse possono avere caratteristiche differenti. Possono:
essere più veloci o più lente
usare più o meno memoria
essere più facili o più difficili da capire quando si legge il codice
essere considerate più o meno "eleganti"
Supponiamo di aver bisogno di ordinare una liste di ntuple a due elementi di user-id e nomi, per esempio:
mylist = [("fangohr", "Hans Fangohr",),
("admin", "The Administrator"),
("guest", "The Guest")]
che vogliamo ordinare in ordine crescente di user-id. Se ci sono due o più user-id identici (Pratica da evitare come la peste), vogliamo che questi vengano ordinati a seconda del nome associato allo user-id. Questo è semplicemente il comportamento di default del metodo sort, che si basa su come due oggetti vengono paragonati.
stuff = mylist # collect your data
stuff.sort() # sort the data in place
print(stuff) # inspect the sorted data
Le sequenze sono paragonate comparando inizialmente solo i primi elementi. Se sono diversi, allora la decisione viene presa sulla base di questi soli elementi. Per esempio, in un vocabolario, "az" viene prima di "ba". Se i primi elementi sono uguali, solo allora vengono paragonati i secondi elementi ... e così via fino a quando viene trovata una differenza oppure finiscono gli elementi. Per esempio:
(2,0) > (1,0)
(2,1) > (1,3)
(2,1) > (2,1)
(2,2) > (2,1)
'a' < 'b'
('a' < 'A','A' < 'a')
('a' < '1','1' < 'a')
Si può anche ordinare con la funzione sorted:
stuff = sorted(stuff)
Quando la lista non è paticolarmente lunga, in genere è preferibile usare la funzione sorted, che restituisce copia ordinata della lista, invece del metodo sort dell'oggetto lista, che trasforma la lista nella lista ordinata e restituisce None, sovrascrivendo la lista di partenza.
s0 = [2,5,1]
s1 = sorted(s0)
print(s0)
print(s1)
Supponiamo invece che i dati siano stati immagazzinati in modo tale che in ciascuna ntupla il nome viene prima dell'id, cioè:
mylist2 = [("Hans Fangohr", "fangohr"),
("The Administrator", "admin"),
("The Guest", "guest")]
L'ordinamento deve utilizzare l'id come discriminante primario. La prima possibilità è quella di scambiare l'ordine degli elementi nelle ntuple e poi usare sort come prima.
La seconda, più elegante, richiede di decifrare l'help, piuttosto oscuro, della funzione sorted. list.sort() ha le stesse opzioni ma il suo help è meno utile.
help(sorted)
Si noti che sorted and list.sort hanno due keyword parameters. Il primo si chiama key. Lo si può utilizzare per passare una key function, con cui trasformare gli elementi che sort deve comparare.
Vediamo come sfruttarla nel nostro esempio. I nostri dati hanno la struttura:
pair = name, id
e li vogliamo ordinare secondo l'id e ignorando il nome. Lo possiamo ottenere definendo una funzione che restituisca solo il secondo elemento della coppia che gli viene passata:
def my_key(pair):
return pair[1]
mylist2.sort(key=my_key)
Si può anche usare una funzione anonima:
mylist2.sort(key=lambda p: p[1])
La funzionekey viene chiamata una volta sola per ogni elemento nella lista. Tuttavia, se la lista da ordinare è molto lunga l'overhead di chiamare una funzione di Python function (che è relativamente grande rispetto alle chiamate in altri linguaggi come il C) potrebbe farsi notare.
Se l'efficienza è veramente importante e vi siete resi conto che una parte significativa del tempo di esecuzione viene spese in queste funzioni (Si chiama profiling)allora è possibile che sia necessario riscrivere le funzioni in C oppure un altro linguaggio più low-level. Python può essere interfacciato con questi linguaggi ma i dettagli li vedrete in altri corsi.