En tancar el mòdul 5 vam dir que l'èxit de TascaFàcil portava amb ell el millor tipus de problema: quan l'agenda d'Estudi Alba tingui dues-centes tasques desades a tasques.json, «cercar la del client Vidal» deixarà de ser trivial. Fins ara hem fet servir in, .index() i la pertinença en conjunts com a caixes negres: funcionen, i no ens hem preguntat com. Aquesta lliçó obre la primera d'aquestes caixes.

Cercar és, amb diferència, l'operació més freqüent de qualsevol programa que manipuli dades. Aquí aprendràs les tres famílies de tècniques que existeixen —cerca lineal, cerca binària i cerca per clau—, què exigeix cadascuna, quant costa i quan triar-la. Les implementarem a mà per entendre-les per dins, amb la mateixa moralitat honesta de sempre: en producció es fa servir l'eina del llenguatge.

1. Què significa cercar i què es retorna
2. Cerca lineal: l'algorisme de referència
3. Traça pas a pas de la cerca lineal
4. Cerca amb criteri: el callback torna
5. Cercar totes les coincidències
6. Cerca binària: la idea de descartar la meitat
7. Cerca binària: implementació i traça
8. Lineal davant de binària
9. Cerca per clau: diccionaris i conjunts
10. Índex invertit: preparar la cerca
11. TascaFàcil v0.12: tres maneres de localitzar una tasca
12. Errors comuns i consells
13. Exercicis
14. Conclusió

«Cercar» sembla una sola cosa i en realitat són tres preguntes diferents, i confondre-les és el primer error del principiant:

En una llista de nombres les tres coincideixen gairebé sempre. A la nostra agenda —una llista de diccionaris— la diferència és enorme: saber que existeix una tasca de la Nuria no em serveix per canviar-li la prioritat; per a això necessito el diccionari, o com a mínim la seva posició.

I hi ha una quarta decisió: què passa quan no es troba res. Els tres convenis habituals són retornar -1 (tradició heretada de C i Java), retornar None (l'idiomàtic en Python quan es retorna un element) o llançar un error, que és el que fa .index() amb el seu ValueError. Farem servir -1 per a posicions i None per a elements. Sigui quin sigui el conveni, documenta'l al docstring i sigues coherent a tot el programa.

La cerca lineal (o seqüencial) és l'algorisme més simple que existeix: mirar els elements un per un, des del principi, fins a trobar el que busques o esgotar la col·lecció. No exigeix absolutament res de les dades: serveixen ordenades o desordenades, en una llista, en un fitxer o en una cinta.

Traduït a Python sobre la nostra agenda, amb enumerate de 05-01 per tenir alhora posició i element:

Tres detalls fan bo aquest codi. La sortida primerenca amb return: així que troba la tasca, la funció acaba; si deséssim el resultat en una variable i continuéssim recorrent, en una agenda de 200 tasques en miraríem 199 de més. El return -1 és fora del bucle, alineat amb el for: només s'hi arriba quan el recorregut ha acabat sense trobar res; posat a dins, la funció retornaria -1 a la primera volta que no coincidís. I la comparació és ==, no in: exigeix coincidència exacta, i ja veurem la variant «conté» a la secció 4.

Les dues funcions són idèntiques tret d'allò que retornen, la posició o l'element. I recorda l'aliasing de 05-01: el que retorna la segona és el mateix diccionari que hi ha a la llista, de manera que cercar_tasca(agenda, "Cartell fira")["prioritat"] = "baixa" modifica l'agenda de debò. És el mecanisme en què ja es recolzava triar_tasca des de la v0.10.

Fem la prova d'escriptori de 01-05 sobre aquesta agenda d'Estudi Alba:

Tracem dos casos alhora: A, cercar "Logotip client Vidal", que sí que hi és; i B, cercar "Flyer estiu", que no existeix.

El cas A acaba en tres comparacions i la posició 3 no s'arriba a mirar: aquest és l'efecte de la sortida primerenca. El cas B en necessita quatre, és a dir, totes. I aquí tens la primera lliçó de cost del mòdul, que es llegeix directament de la taula. Millor cas: l'element és el primer, una comparació. Pitjor cas: és l'últim o no hi és, tantes comparacions com elements. Cas mitjà: la meitat dels elements. Retén el detall important: el pitjor cas de la cerca lineal és no trobar res, de manera que un programa que cerca sovint coses inexistents es troba en el pitjor escenari possible per a aquest algorisme.

Les funcions anteriors només saben cercar per títol exacte. Si la Marta vol cercar per responsable, per prioritat o per «títols que continguin la paraula fira», escrivim una funció per cas? No: apliquem el patró callback de 04-05, i en comptes del valor a comparar, la funció rep la comprovació en forma de funció.

L'esquelet del recorregut el posa cercar_si; la decisió de què compta com a «trobat» la posa qui la crida. La tercera línia fa servir l'in de cadenes de 05-02 —«conté»— i .lower() per no distingir majúscules, que és el que espera qualsevol usuari; la quarta combina dues condicions sense que cercar_si se n'assabenti. Python porta aquesta idea incorporada a next amb una expressió generadora:

Es llegeix «el següent element de l'agenda el responsable del qual sigui Nuria, o None si no n'hi ha cap». Sense aquest segon argument, next llança un error quan no hi ha coincidències. És la forma idiomàtica i mandrosa —deixa de recórrer així que troba, igual que el nostre return— i la que faries servir en un projecte real. cercar_si existeix perquè vegis que per dins no hi ha màgia: és un for amb un if.

De vegades no vols la primera, vols totes: «totes les tasques del Luis», «totes les de prioritat alta». L'algorisme canvia en un punt essencial: no hi ha sortida primerenca, perquè cal examinar la col·lecció sencera.

La comprensió és l'opció preferent per llegibilitat. I atenció a l'última línia: si només necessites quantes n'hi ha, compta directament en comptes de construir una llista que anaves a llençar.

Si les dades estan ordenades, es pot fer una cosa molt millor que mirar un per un. Pensa en com busques una paraula en un diccionari de paper: no comences per la A, l'obres per la meitat, veus en quina lletra ets i descartes mitja obra de cop. Aquest és l'algorisme de cerca binària, i el seu requisit és innegociable: la col·lecció ha d'estar ordenada segons el mateix criteri pel qual cerques. Si no ho està, la cerca binària no dona error, dona respostes incorrectes, que és molt pitjor.

Sobre aquesta llista ordenada de codis d'encàrrec d'Estudi Alba —[102, 118, 134, 156, 170, 189, 203, 240], posicions 0 a 7— cerquem el 170:

Tres comparacions per a vuit elements, davant de les cinc de la lineal. La diferència sembla modesta aquí; amb un milió és abismal, i ho veurem numèricament a la secció 8.

L'algorisme manté tres variables: esquerra i dreta delimiten el tros on el valor encara podria ser, i mig és la posició que s'examina a cada volta.

Quatre punts on es trenca aquest algorisme, i cal entendre'ls amb precisió:

• while esquerra <= dreta, amb l'igual. Quan tots dos coincideixen queda un element per mirar, i s'ha de mirar. Amb < a seques fallarien justament els valors que queden sols al final del tros.
• (esquerra + dreta) // 2 fa servir la divisió entera de 02-02: si la suma és senar s'arrodoneix cap avall. Tant se val cap a quin costat, sempre que el tros es redueixi a cada volta.
• mig + 1 i mig - 1, mai mig a seques. Ja hem comprovat que valors[mig] no és el cercat, així que també el descartem. Amb esquerra = mig, el tros deixa d'encongir quan queden dos elements i el programa es queda penjat en un bucle infinit.
• El tros es redueix a la meitat a cada volta, i per això el bucle sempre acaba: o troba el valor, o esquerra acaba passant dreta.

Tracem dues cerques sobre la llista de codis, una fila per volta del while: el 170, que hi és, i el 150, que no.

Fixa't en les dues terceres voltes: en totes dues esquerra i dreta valen el mateix, el bucle sí que hi entra i examina l'últim candidat. Només després esquerra supera dreta i el bucle acaba. És la millor demostració que el <= no és un detall cosmètic.

Existeix també una versió recursiva d'aquest algorisme, més curta i per a molts més elegant, que escriurem a Recursivitat quan tinguem l'eina. I, com sempre, Python ja porta això fet: el mòdul bisect de la biblioteca estàndard implementa la cerca binària en C, i la seva funció bisect.insort(llista, valor) insereix mantenint l'ordre. En producció es fa servir bisect; aquesta implementació és per entendre què fa per dins.

Els números surten d'una regla senzilla: cada volta de la binària divideix entre dos el tros pendent, de manera que doblar les dades li afegeix una sola comparació. Passar de mil a un milió d'elements multiplica per mil la feina de la lineal i li suma deu comparacions a la binària; el nom formal d'aquesta diferència el posarem a Eficiència i notació Big-O. Però la taula també avisa de la lletra petita: ordenar costa. Si has de cercar una sola vegada en una llista desordenada, ordenar-la per poder fer servir la binària surt més car que recórrer-la sencera. La binària compensa quan la col·lecció ja està ordenada o quan hi cercaràs moltes vegades.

Queda la tècnica més ràpida de les tres, la que ja fas servir des de 05-03 sense saber com funciona. Preguntar "Marta" in equip o llegir fitxa["rol"] no recorre res i no compara res: troba la dada d'un salt, tingui el diccionari deu claus o deu milions. El mecanisme s'anomena taula hash, i la idea intuïtiva, sense entrar en el detall, és aquesta: Python aplica a la clau una funció matemàtica —la funció hash— que la converteix sempre en el mateix nombre; aquest nombre indica en quina casella d'una taula interna viu el parell clau-valor; i per cercar es repeteix el càlcul i s'hi va directament, sense recórrer res.

Aquesta és també l'explicació del requisit de 05-03: les claus d'un diccionari i els elements d'un conjunt han de ser immutables. Si fessis servir una llista com a clau i després la modifiquessis, el seu hash canviaria, la casella calculada seria una altra i la dada quedaria desada en un lloc on ningú no anirà a mirar. El resum pràctic és contundent:

La conclusió operativa la vam anticipar a 05-03 i ara ja saps per què: si el teu programa fa moltes comprovacions de pertinença sobre una col·lecció, aquesta col·lecció hauria de ser un conjunt o un diccionari, no una llista. El preu és memòria extra i la pèrdua de l'ordre d'inserció com a criteri de cerca.

Aquí arriba la idea que converteix tot l'anterior en una decisió de disseny. Si la Marta preguntarà quinze vegades al dia «què té el Luis?», recórrer l'agenda sencera quinze vegades és absurd: millor recórrer-la un cop i construir un diccionari que respongui a l'instant. Aquesta estructura s'anomena índex invertit: en comptes d'anar de la tasca al seu responsable, va del responsable a les seves tasques.

El patró if nom not in index: index[nom] = [] és el mateix «primera vegada» de 05-03, i també s'escriu en una línia amb index.setdefault(nom, []).append(tasca). index.get("Luis", []) retorna una llista buida si aquesta persona no té res, evitant el KeyError.

Això és un intercanvi: gastem memòria i un recorregut previ perquè les consultes posteriors siguin immediates. Compensa quan es consulta molt i es modifica poc; no compensa quan l'agenda canvia sense parar, perquè l'índex queda obsolet així que es registra una tasca nova. És la primera aparició de l'intercanvi temps-memòria, que estudiarem amb nom propi a 06-04.

Afegim al programa una opció de cerca que fa servir les tres tècniques segons el cas: per títol exacte quan la Marta sap què busca, per text contingut quan només en recorda una paraula, i per responsable amb índex quan vol el repartiment. El menú passa a vuit opcions.

Decisions de disseny que val la pena assenyalar:

• cercar_si i cercar_totes no saben res de tasques. Reben el criteri com a callback, de manera que serveixen per a qualsevol col·lecció de diccionaris; tota la lògica específica viu a les lambda de menu_cercar.
• menu_cercar és l'única que parla amb l'usuari, complint la separació entre entrada/sortida i lògica de 04-04. Les funcions de cerca no imprimeixen res, i les tres branques conflueixen en una única llista trobades que es mostra igual en els tres casos. A més, la cerca per text passa tots dos costats a minúscules, de manera que «vidal», «Vidal» i «VIDAL» troben el mateix.
• L'índex es construeix dins de la branca 3 i es descarta en sortir. És deliberat: l'agenda canvia entre consulta i consulta, i un índex desat en una global quedaria obsolet. Amb vint tasques, reconstruir-lo costa un sospir.

No hi ha cerca binària a TascaFàcil, i és una decisió conscient: l'agenda no està ordenada per títol, i ordenar-la només per poder cercar seria més car que recórrer-la. Amb vint tasques, la lineal és la resposta correcta.

Posar el return de «no trobat» dins del bucle. És l'error número u de la lliçó: la funció retorna -1 o None a la primera volta que no coincideix, sense mirar la resta. Aquest return va fora del for, a la seva mateixa alçada.

Oblidar comprovar el resultat. Si cercar_tasca retorna None i escrius tasca["prioritat"], obtens TypeError: 'NoneType' object is not subscriptable. Comprova sempre amb if tasca is not None: abans de fer servir el que s'ha retornat. I fer servir cerca binària sobre dades sense ordenar no falla amb un error, falla amb un resultat equivocat: diu que un element no hi és quan sí que hi és. Si la teva funció exigeix ordre, digues-ho al docstring. Escriure esquerra = mig en comptes de mig + 1 fa que el tros deixi d'encongir i el programa es pengi en un bucle infinit; si la teva binària es queda aturada, mira-hi primer.

Confondre == amb in en cercar textos. t["titol"] == "fira" només troba una tasca que es digui exactament així; "fira" in t["titol"] troba totes les que la continguin.

Consell: normalitza abans de comparar. Aplica .strip().lower() als dos costats quan cerquis text escrit per una persona: un espai final és invisible i fa fallar la comparació.

Consell: en producció, l'eina del llenguatge. in, .index(), next(...), una comprensió, un diccionari o bisect estan escrits en C, provats per milions de programes i són més ràpids que qualsevol bucle que escriguis. Aquestes implementacions existeixen perquè entenguis què fan per dins i sàpigues quina triar, no per copiar-les al teu projecte.

Sobre la llista ordenada [2, 5, 9, 14, 21, 30, 44, 51, 68] (posicions 0 a 8), traça en una taula la cerca binària dels valors 44 i 7, indicant a cada volta esquerra, dreta, mig, el valor examinat i l'acció. Digues quantes comparacions necessita cada cerca i quantes n'hauria necessitat la cerca lineal.

Escriu tres funcions sobre l'agenda (llista de diccionaris amb titol, responsable, prioritat, dies, completada):

• primera_urgent(agenda): retorna la primera tasca pendent de prioritat alta, o None.
• pendents_de(agenda, nom): retorna la llista de tasques pendents d'aquesta persona, sense distingir majúscules.
• hi_ha_bloqueig(agenda): retorna True si algú té més de tres tasques pendents. S'ha de recolzar en un índex, no en un bucle imbricat.

Escriu index_per_prioritat(agenda) que retorni un diccionari amb les claus "alta", "mitjana" i "baixa" —les tres sempre presents, encara que alguna quedi buida— i com a valor la llista de títols de les tasques pendents d'aquella prioritat. Després, escriu informe(index) que imprimeixi cada prioritat amb el seu nombre de tasques i els seus títols.

Solució 1.

Dues comparacions per al 44 (la lineal n'hauria necessitat set) i tres per al 7 (la lineal, les nou del recorregut complet, perquè no hi és). Fixa't en l'asimetria: la binària triga gairebé el mateix trobi o no trobi, mentre que a la lineal el fracàs li costa sempre el màxim.

Solució 2.

hi_ha_bloqueig recorre l'agenda una sola vegada construint un índex de recomptes, en comptes de recórrer-la un cop per cada membre de l'equip. Amb tres persones la diferència és irrellevant; amb tres-centes, és la diferència entre un programa usable i un que no ho és. any retorna True així que troba un valor que compleix la condició i deixa de mirar: és la sortida primerenca de la secció 2, ja incorporada al llenguatge.

Solució 3.

La clau és a la primera línia: {p: [] for p in PRIORITATS} és una comprensió de diccionari que crea les tres claus per endavant fent servir la constant PRIORITATS. Gràcies a això el bucle pot fer index[...].append(...) sense comprovar res, i informe recorre les prioritats en el seu ordre lògic —alta, mitjana, baixa— en comptes de l'ordre en què apareguessin a l'agenda. Triar bé l'estructura simplifica el codi que ve després.

Cercar no és una operació, són tres preguntes: si existeix, on és i quin és; i una quarta decisió, què retornar quan no hi ha res (-1, None o un error). La cerca lineal recorre un per un amb sortida primerenca mitjançant return: no exigeix res de les dades, troba en una comparació en el millor cas i necessita recórrer-ho tot en el pitjor, que és precisament quan l'element no hi és. Convertida en funció d'ordre superior amb un callback, la mateixa funció cerca per títol, per responsable o per text contingut; i sense sortida primerenca es transforma en la cerca de totes les coincidències, que en Python s'escriu amb una comprensió de llista.

La cerca binària canvia recórrer per descartar: exigeix dades ordenades i a cada volta parteix el problema en dos, de manera que un milió d'elements es resolen en vint comparacions. Els seus tres paranys són el while esquerra <= dreta, el (esquerra + dreta) // 2 i el mig + 1 / mig - 1 que garanteixen que el tros encongeix. I la cerca per clau en diccionaris i conjunts guanya a les dues anteriors gràcies a la taula hash, que calcula la casella en comptes de comparar; d'aquí que les claus hagin de ser immutables. Quan una consulta es repeteix molt, val la pena pagar un recorregut i una mica de memòria per construir un índex invertit. I en producció, sempre, l'eina del llenguatge: in, .index(), next, una comprensió, un diccionari o bisect. TascaFàcil arriba a la v0.12 i la Marta ja pot preguntar-li a la seva agenda. Però la cerca binària s'ha quedat sense fer servir per una raó concreta: l'agenda no està ordenada, i ordenar-la és justament el que hem estat delegant a sorted sense preguntar. A Algorismes d'ordenació obrirem aquesta segona caixa negra: què fa sorted per dins, què significa que una ordenació sigui estable i per què ordenar és l'operació més rendible de tot el curs.