Vector de booleans?
És una opció. Un vector de booleans, inicialment a false, que quan apareix un element posi la seva posició a true. El problema és que tindrem un vector enorme, que probablement no aprofitarem. Imaginem, si no, que volem emmagatzemar tots els enters positius existents.
Vector ordenat amb els números?
Una altra opció. Inicialment és buit. Quan apareix un número, l'insertem a la posició on hauria d'anar (cost lineal). Per localitzar el número, fem una cerca dicotòmica, temps logarítmic.
Llista ordenada amb els números?
Una altra opció. Insertar té cost constant un cop tenim la posició, però trobar-la té cost lineal (ja que no hi podem fer una cerca dicotòmica). Per tant, té cost lineal tant la cerca com la inserció
Llista no ordenada amb els números?
Insertar té cost constant (insertem on vulguem i au). La cerca té cost lineal, ja que hem de recórrer tota la llista. El problema és que si volem evitar repeticions, hem de fer que abans d'insertar busqui si ja hi és o no, per tant, tindríem cost lineal
Nota: insertar al final d'un vector en general és més ràpid que fer-ho en una llista, tot i que ara no ve al cas la raó
Sembla que de moment no hem estudiat cap estructura de dades que ens permeti representar un conjunt matemàtic de manera eficient. Cap? No! En tenim una de molt bona (que te la pots saltar si només t'interessa aprovar l'assignatura, anant directament al set)
Arbres binaris de cerca
Un arbre binari de cerca és un arbre definit de manera que els elements del fill esquerre són menors o iguals que l'arrel, i els elements del fill dret són més grans o iguals. Per tant, per trobar un element, seria una cosa així:
bool cerca (Arbre<int>& a, int x) {
if (a.es_buit()) return false;
if (a.arrel()==x) return true;
int ar=a.arrel();
Arbre<int> fe,fd;
a.fills(fe,fd);
if (ar<x) {
if (cerca(fd,x)) {
a.plantar(ar,fe,fd);
return true;
}
}
else {
if (cerca(fe,x)) {
a.plantar(ar,fe,fd);
return true;
}
}
a.plantar(ar,fe,fd);
return false;
}
Mirem el node actual. Si hi és, retornem cert. Si no, mirem si hauria d'estar a la dreta o a l'esquerra, i mirem allà. Això ens permet mirar només un node per nivell. La gràcia d'això és que, al anar duplicant la quantitat de nodes a cada nivell, la quantitat de nivells és logarítmicament proporcional a la quantitat d'elements (un arbre complet de 255 elements té 8 nivells, un de 511 en té 9...)
Al final, ens trobem amb que cercar un element té cost logarítmic, ja que, com a molt, haurem de visitar un cop cada nivell. Per tant, la cerca té cost logarítmic.
Si volem insertar, primer hem de decidir si acceptem repeticions. En el que volem ara, que és emmagatzemar si un número ja ha aparegut o encara no, jo no n'acceptaré.
//Pre: cert
//Post: x està a l'arbre. Si ja hi era, retorna false
// Si l'hem insertat, retorna true
bool insertar (Arbre<int>& a, int x) {
if (a.es_buit()) {
Arbre<int> fe,fd;
a.plantar(x,fe,fd);
return true;
}
if (a.arrel()==x) return false;
Arbre<int> fe,fd;
int ar=a.arrel();
a.fills(fe,fd);
bool res;
if (x<ar) res=insertar(fe,x);
else res=insertar(fd,x);
a.plantar(ar,fe,fd);
return res;
}
És a dir, fem la nostra cerca, i si el trobem, vol dir que ja hem acabat. Si ens acabem l'arbre i no l'hem trobat, l'insertem. Insertar té temps constant, ja que només crea el nou node i l'enganxa. Per tant, fer la inserció té temps logarítmic, ja que hem de buscar on insertem, i fer-ho.
Amb això implementarem la següent estructura de dades.
Set
Un set és, en essència, un conjunt matemàtic. Emmagatzema les dades ordenades, sense repeticions, permetent-nos afegir, eliminar i consultar eficientment. Concretament, té les següents funcions:
begin i end:
Retornen els respectius iteradors
empty i size:
El que podríem esperar
insert:
Inserta l'element. La seva capçalera és:
pair<iterator,bool> insert (const value_type& val);
pair<iterator,bool> insert (const value_type& val);
La posició on s'insertarà la busca automàticament. El retorn són una parella, on el primer element apunta a la posició on tenim el valor, i el segon ens indica si l'hem insertat o no.
La funció té temps logarítmic
També tenim una versió que rep un iterador que fa de pista. Aquest apunta a un element proper, i ens serveix per insertar l'element més ràpid.
erase:
Elimina l'element. Hi ha tres versions, que són:
iterator erase (const_iterator position);
size_type erase (const value_type& val);
iterator erase (const_iterator first, const_iterator last);
La primera versió rep un iterador que apunta a l'element que volem eliminar. Té, per tant, temps constant amortitzat (ja tenim la posició a eliminar, només hem d'eliminar-lo). Retorna un iterador que apunta al següent element
La segona versió rep el valor que volem eliminar. Té, per tant, temps logarítmic, ja que l'hem de buscar. Retorna la quantitat d'elements eliminats (és a dir, o 0 o 1).
La tercera versió rep dos iteradors, i elimina els elements que hi ha al rang. Té cost lineal respecte a la quantitat d'elements
find:
Retorna un iterador que apunta a l'element (si hi és), o a l'end (si no hi és). Cost logarítmic
Un exercici
Podem fer un exercici, ja que, de fet, en el Jutge és el que hi ha. El problema X83904.
void llegir_set(set<string>& S) {
string s;
while (cin >>s and s!=".") S.insert(s);
}
void actualitzar_totes(set<string>& totes, const set<string>& S) {
set<string>::iterator it=totes.begin();
while (it!=totes.end()) {
if (S.find(*it)!=S.end()) ++it;
else it=totes.erase(it);
}
}
void actualitzar_cap(set<string> &cap, const set<string> &S) {
set<string>::iterator it=cap.begin();
while (it!=cap.end()) {
if (S.find(*it)!=S.end()) {
it=cap.erase(it);
}
else ++it;
}
}
void mostrar_set(const set<string>& S) {
for (set<string>::const_iterator it=S.begin();it!=S.end();++it) cout <<' '<<*it;
cout <<endl;
}
int main(){
set<string> cap_activitat;
llegir_set(cap_activitat);
int n;
cin >>n;
set<string> totes_activitats(cap_activitat);
for (int i=0;i<n;++i) {
set<string> actual;
llegir_set(actual);
actualitzar_totes(totes_activitats, actual);
actualitzar_cap(cap_activitat,actual);
}
cout <<"Totes les activitats:";
mostrar_set(totes_activitats);
cout <<"Cap activitat:";
mostrar_set(cap_activitat);
}
És a dir, llegim tots els elements, i tenim dues còpies, ja que inicialment, els que fan totes les activitats són els mateixos que no en fan cap. Aleshores, anem llegint els que fan cada activitat. Fem una funció que actualitzi totes, de manera que si un no apareix, l'eliminem, i una altra que actualitzi cap, de manera que si apareix un, l'eliminem. I ja està
Map:
Ara presento una estructura molt similar al set. Aquest és el map, o diccionari. És com un set, però amb un valor associat. És a dir, té una sèrie de claus, i a cada clau un valor. Està ordenat per les claus, i les que no poden repetir-se són les claus.
Les funcions que té són en essència les mateixes que el set, però canviant l'element per una parella. És a dir, l'insert, enlloc de rebre un element, rep una parella. La desreferència de l'iterador igual, ens dóna una parella
A més d'això, tenim l'operador []. Aquest el que fa és, si no hi ha l'element, el crea, i si hi és, el modifica. I no, no és un embarbussament. La diferència fonamental és:
map<int,int> m, m2;
m.insert(pair<int,int>(3,3));
m2.insert(pair<int,int>(3,3));
...
m[3]=4;
m2.insert(pair<int,int>(3,4));
Si miréssim com queden, veuríem que hem modificat m, mentre que m2 queda igual. Aquesta és la diferència fonamental
map<int,int> m, m2;
m.insert(pair<int,int>(3,3));
m2.insert(pair<int,int>(3,3));
...
m[3]=4;
m2.insert(pair<int,int>(3,4));
Si miréssim com queden, veuríem que hem modificat m, mentre que m2 queda igual. Aquesta és la diferència fonamental
Truc amb els iteradors
Ara els iteradors fan referència a una parella, enlloc de fer-la a un sol element. Per tant, si volem accedir al segon de la parella (per exemple, per incrementar), el que faríem intuitivament seria
++(*it).second;
No obstant, tenim una altra eina, que és l'operador ->. Aquest el que fa és que, quan estem apuntant a una estructura, donar-nos aquell element en concret. Per exemple
++it->second;
Ens dóna el segon element. Això és heretat dels punters, però és molt pràctic
Un exercici
Podem fer l'exercici X34352 del jutge.
int main() {
map<string,int> m;
char c;
string s;
while(cin >>c>>s) {
if (c=='a') {
map<string,int>::iterator it=m.find(s);
if (it!=m.end()) ++it->second;
else m[s]=1;
}
else {
map<string,int>::iterator it=m.find(s);
if (it!=m.end()) cout<<it->second<<endl;
else cout<<0<<endl;
}
}
}
Fem un map que tingui un string com a clau, i un enter com a valor. Anem llegint l'entrada, si hem d'afegir, mirem si hi és o no. Si ja hi és, incrementem el valor. Si no hi és, l'afegim i li posem un 1. Si volem mostrar, mirem si hi és. Si hi és, mostrem la freqüència, i si no hi és, un 0.
Vectors de mida variable
Això ho poso aquí perquè, malgrat que no té a veure amb els sets ni amb els maps, es fa a la mateixa sessió. A més n'he parlat una mica al principi, així que ho poso
Mai us heu preguntat com funciona internament un vector? Porteu des de PRO1 utilitzant-los. Normalment ens diuen que reserva espai a posicions de memòria seguides, i realment no és fals. Però no és gaire precís tampoc.
Un vector, internament, conté una sèrie d'atributs, tals com la mida actual, o un punter que apunta al primer element. La memòria es reserva utilitzant l'operador new[], que ara no cal explicar què fa.
Quan declarem un vector de mida n, el que fa és reservar espai per exactament n elements. Ara, què passa si ens adonem de que necessitem més espai? O si no sabem la mida que necessitarem. Existeix una funció, a la que molts professors de PRO1 tenen mania, que és el push_back. Aquest, el que fa és incrementar en 1 la mida del vector, i posar allà l'element que volem posar
Espera un moment, no havies dit que reservàvem exactament la mida del vector? Això com es menja?
Fàcil.
Reservar més espai, i moure'ns allà
Si tenim espai per n elements, i volem tenir-ne n+1, el que hem de fer és reservar més espai, i desplaçar el vector cap allà. El problema que ens trobem, aleshores, és que desplaçar un vector té cost lineal respecte la quantitat d'elements que desplacem. Però aleshores, la solució és fàcil. Reservar més espai del necessari. Enlloc de reservar espai per n+1 elements, reservem només per potències de 2. Aleshores, si tenim un codi com el següent:
vector<int> v;
for(int i=0;i<n;++i) v.push_back(i);
Imaginem que n=63. Aleshores, faríem:
-Reservem espai per 1 element. Posem el primer
-Reservem espai per 2 elements. Posem el segon
-Reservem espai per 4 elements. Posem el tercer
-Posem el quart
-Reservem espai per 8 elements. Posem el cinquè
-Posem el sisè
-Posem el setè
-Posem el vuitè
-Reservem espai per 16 elements. Posem el novè
...
-Reservem espai per 32 elements. Posem el dissetè
...
-Posem el 63è
Podríem calcular el cost d'això. En molts casos és constant, i en alguns lineal. No obstant, l'important és saber quin cost en tindrà quan en fem molts. Si en fem molts, fent la mitjana, veiem que és cost constant amortitzat. No creix el cost en funció de la quantitat d'elements. Tinguem 8 elements o 800.000, el cost en mitjana serà el mateix
Oju (que vol dir ull)
Als professors no els agrada que utilitzem push_back sense una justificació. Per exemple, un dia vaig llegir un codi com el següent, en una pàgina que teòricament ensenyava a programar
En els vectors
int n;
vector<int> v;
cin >>n;
int a;
for (int i=0;i<n;++i) {
cin >>a;
v.push_back(a);
}
Utilitzar push_back aquí no té cap justificació lògica. Sabem quants elements tindrem, i sabem que reservar l'espai inicialment és més eficient que anar modificant la mida. Per tant, fer això restaria de nota manual.
piles/cues
bool ben_parentitzat(const string& s) {
vector<char> v;
for (int i=0;i<int(s.length());++i) {
if (s[i]=='(' or s[i]=='[' or s[i]=='{') {
v.push_back(s[i]);
}
else {
if (v.empty()) return false;
if (s[i]==')' and v.back()!='(') return false;
else if (s[i]==']' and v.back()!='[') return false;
else if (s[i]=='}' and v.back()!='{') return false;
v.pop_back();
}
}
return v.empty();
}
En aquest cas, estem utilitzant un vector enlloc d'una pila. No utilitzem res del que permet el vector. Ni l'accés aleatori, ni el recorrem... Només accedim a l'últim element, i això ja ens ho fa una pila (de manera més eficient)
Nota: una pila de la STL es pot implementar internament amb una deque o un vector (per defecte, una deque). Una deque s'implementa amb un vector de punters, de manera que realment, utilitzant una pila, estem utilitzant un vector. No obstant, es pot fer la prova per veure què va més ràpid, si fer push_back en un vector, o fer push en una pila. No l'he fet, però m'apostaria alguna cosa a que és més ràpid fer-ho en una pila
llistes
Si necessitem insertar només al final, o ens és indiferent la posició, jo realment utilitzaria un vector. Contràriament al que pot semblar, és més eficient fer push_back en un vector, que en una llista
Per altra banda, si vols tenir l'estructura ordenada, potser també surt més a compte utilitzar el vector. Insertar tindrà cost lineal, perquè haurem de desplaçar els elements del vector per fer espai, però amb la llista hauríem de buscar la posició també en temps lineal (a no ser que tinguem ja la posició). El que ens aporta aquí utilitzar el vector, és que hi podem fer una cerca dicotòmica
Cap comentari:
Publica un comentari a l'entrada