Lesson10

O crivo de Eratóstenes

def sieve(n):
    from math import sqrt
    
    def delmults(i):
        for k in range(len(lst) - 1, i, -1):
            if lst[k] % lst[i] == 0:
                del(lst[k])
    
    # 2 is a prime number
    lst = [2]
    
    # all other primes are odd numbers
    lst.extend(range(3, n+1, 2))
    
    # let us iterate and remove those that are multiple of known primes
    i = 0
    while lst[i] <= sqrt(n):
        delmults(i)
        i = i + 1
    
    return lst    

Porque razão não podemos utilizar o for na função anterior? E porque podemos utilizar na função interna? Será que esta é a solução mais eficiente?

Vejamos a seguinte alternativa:

def sieve(n):
    from math import sqrt
    
    sievelst = [ True ] * (n+1)
    sievelst[0:2] = [ False, False ]
    
    for i in range(2, int(sqrt(n)) + 1):
        for k in range(i * i, n+1, i):
            sievelst[k] = False
    
    return [ i for i in range(2, n+1) if sievelst[i] ]

Exercício: Testar qual é mais eficiente.

Algoritmos de procura

A procura de elementos é uma das operações mais comuns em listas ou, em geral, em sequências iteráveis. Dada uma lista l podemos perguntar se um dado elemento x está nessa lista:

def linearsearch(l, x):
    for i in range(len(l)):
        if l[i] == x:
            return i
    return -1

Neste caso retornamos ou o primeiro índice na lista onde encontrámos x, ou retornamos -1 caso x não ocorra na lista. Notar que esta função é idêntica à operação pré-definida in, ou seja, x in l.

Se a lista estiver ordenada podemos fazer melhor. O algoritmo anterior é conhecido por procura linear uma vez que podemos ter de inspeccionar todos os elementos na lista para descobrir se x ocorre ou não na mesma. Numa lista ordenada podemos realizar a procura de uma forma mais eficiente inspeccionando apenas alguns elementos:

def binsearch(l, x):
    left = 0
    right = len(l) - 1
    
    while left <= right:
        mid = left + (right - left)//2
        if x == l[mid]:
            return mid
        elif x > l[mid]:
            left = mid + 1
        else:
            right = mid - 1
    return -1

Podemos agora ficar convencidos que então é melhor ordenar e procurar depois, mas estaríamos enganados. Ordenar uma lista tem em geral um custo superior à procura linear, e o custo de manter a lista ordenada à medida que são adicionados novos elementos é ainda pior. Veremos estes custos de seguida. No entanto, se o número de procuras for muito superior ao número de alterações na lista, compensa ordenar e utilizar a pesquisa binária, sendo em geral bastante mais eficiente.

Algoritmos de ordenação

Pode ser útil ordenar uma lista como acabámos de ver. Existem vários algoritmos de ordenação e, em Python, temos as funções pré-definidas sorted (que vimos já para os tuplos) e a função sort sobre listas, que implementa um desses algoritmos de ordenação:

>>> l = [1,8,21,4,1,8,9]
>>> sorted(l)
[1, 1, 4, 8, 8, 9, 21]
>>> l
[1, 8, 21, 4, 1, 8, 9]
>>> l.sort()
>>> l
[1, 1, 4, 8, 8, 9, 21]
>>>

Vejamos então duas possíveis implementações da função ordenação sobre listas.

def bubblesort(l):
    changed = True
    k = 0
    while changed:
        changed = False
        for i in range(len(l) - 1, k, -1):
            if l[i-1] > l[i]:
                l[i], l[i-1] = l[i-1], l[i]
                changed = True
        k = k + 1

def insertionsort(l):
    for i in range(1, len(l)):
        x = l[i]
        j = i - 1
        while j >= 0 and x < l[j]:
            l[j+1] = l[j]
            j = j - 1
        l[j+1] = x

Considerações sobre eficiência

Para compararmos a eficiência de algoritmos temos de analisar a ordem de crescimento dos recursos necessários em função do tamanho da entrada, i.e., a sua complexidade computacional. Por recursos entende-se tempo e espaço necessários para executar o algoritmo. Este assunto será discutido mais em detalhe na disciplinas de Introdução aos Algoritmos e Estruturas de Dados (IAED) e de Análise e Síntese de Algoritmos (ASA), mas para já podemos espreitar a aula relevante de IAED a respeito deste assunto e tentar descobrir as ordens de crescimento para os algoritmos anteriores.

Para esta análise é importante conhecer a complexidade das operações sobre várias entidades computacionais em Python, nomeadamente sobre listas.