Exemples

Aquesta lliçó presenta alguns exemples de conjunts. El primer exemple consisteix a trobar totes les paraules úniques que hi ha a l’entrada. La comparació de la solució amb conjunts amb la de llistes mostra el gran guany en eficiència. El segon exemple consisteix a trobar quin és l’element que falta en una llista d’elements amb possibles repeticions.

Trobar totes les paraules úniques

Suposem que volem llegir totes les paraules de l’entrada i fer un llistat de totes les paraules úniques que hi apareixen (en minúscules).

Aquest tasca es podria resoldre llegint primer totes les paraules de l’entrada tot anant-les inserint en minúscules en un conjunt inicialment buit. Un cop fet això, caldria escriure totes les paraules del conjunt:

from yogi import tokens

paraules: set[str] = set()
for paraula in tokens(str):
    paraula = paraula.lower()  # transforma paraula a minúscules
    paraules.add(paraula)

for paraula in paraules:
    print(paraula)

Per exemple, si executem aquest programa sobre aquesta entrada

I'm saying nothing
But I'm saying nothing with feel

el resultat és

saying
with
i'm
but
nothing
feel

o qualsevol altra ordenació d’aquestes paraules. Recordeu que l’ordre en què es recorren els elements d’un conjunt no està definit.

Per tal que les paraules ens quedin ordenades, podem utilitzar la funció predefinida sorted:

for paraula in sorted(paraules):
    print(paraula)

Així, el resultat és

but
i'm
feel
nothing
saying
with

tal com cal! 👍

Comparació amb llistes

El codi anterior també es podria haver escrit utilitzant llistes enlloc de conjunts:

from yogi import tokens

paraules: list[str] = []
for paraula in tokens(str):
    paraula = paraula.lower()
    if paraula not in paraules:
        paraules.append(paraula)

for paraula in sorted(paraules):
    print(paraula)

Si executo al meu ordinador aquesta versió amb llistes sobre les 600 pàgines del llibre Moby Dick de Herman Melville, la seva execució triga uns dotze segons. En canvi, la versió amb conjunts triga unes 19 centèsimes de segon. Aquesta comparació mostra com els conjunts són molt més eficients respecte les llistes quan cal realitzar-hi moltes operacions de cerca i inserció.

Nota: Per qui tingui curiositat de repetir l’experiment, per fer les mesures he executat aquestes comandes:

> wget https://www.gutenberg.org/files/2701/old/moby10b.txt  

--2022-10-11 16:19:24--  https://www.gutenberg.org/files/2701/old/moby10b.txt
S'està resolent www.gutenberg.org (www.gutenberg.org)… 152.19.134.47
S'està connectant a www.gutenberg.org (www.gutenberg.org)|152.19.134.47|:443… connectat.
HTTP: s'ha enviat la petició, s'està esperant una resposta… 200 OK
Mida: 1256167 (1,2M) [text/plain]
S'està desant a: «moby10b.txt»

moby10b.txt         100%[===================>]   1,20M  1,34MB/s    in 0,9s

2022-10-11 16:19:26 (1,34 MB/s) - s'ha desat «moby10b.txt» [1256167/1256167]

> time python3 p1.py < moby10b.txt > sortida1.txt

real 0m0,191s
user 0m0,154s
sys  0m0,023s

> time python3 p2.py < moby10b.txt > sortida1.txt

real 0m12,185s
user 0m12,037s
sys  0m0,061s

> cmp sortida1.txt sortida2.txt

La comanda wget descarrega un fitxer donada la seva URL i la comanda cmp compara dos fitxers (per comprovar que realment ambdós programes fan el mateix).

Trobar l’element que falta

Considerem que hem d’escriure una funció que, donada una llista que conté tots els nombres entre 0 i n - 1 tret d’un, retorni el nombre que falta.

La funció podria tenir aquesta capçalera i especificació:

def quin_falta(L: list[int], n: int) -> int:
    """Retorna l'únic element entre 0 i n - 1 que no es troba en L."""

Per exemple, quin_falta([3, 0, 2, 3, 0, 2], 4) hauria de retornar 1.

Una primera solució consistiria en buscar, per a cada i entre 0 i n - 1 si i no es troba en L:

def quin_falta(L: list[int], n: int) -> int:
    """Retorna l'únic element entre 1 i n que no es troba en L."""

    for i in range(n):
        if i not in L:
            return i 
    assert False  # no s'hauria d'arriba en aquest punt del programa

Malauradament, el cost d’aquesta funció és $O(n^2)$ o més, ja que l’operador in ha de realitzar, en el cas pitjor, $n$ cerques en una llista de, com a mínim, $n-1$ elements.

Una millor manera de fer-ho és usant conjunts: Començant per un conjunt que conté tots els nombres entre 0 i n - 1, cada element de la llista es treu del conjunt. L’únic supervivent ha de ser l’element que falta:

def quin_falta(L: list[int], n: int) -> int:
    """Retorna l'únic element entre 1 i n que no es troba en L."""

    s = set(range(n))
    for x in L:
        s.discard(x)
    assert len(s) == 1
    return s.pop()  # retorna l'únic element de s

Una altra forma de fer-ho és amb la diferència del conjunt $\{0..n-1\}$ i el conjunt dels elements en L:

def quin_falta(L: list[int], n: int) -> int:
    """Retorna l'únic element entre 1 i n que no es troba en L."""

    s = set(range(n)) - set(L)
    assert len(s) == 1
    return s.pop()




Lliçons.jutge.org
Jordi Petit
Universitat Politècnica de Catalunya, 2022

Prohibit copiar. Tots els drets reservats.
No copy allowed. All rights reserved.