Newsgroup: it.comp.lang.c++
Titolo: Struttura dati veloce per ricerca pochi elementi

Sto studiando quale potrebbe essere la struttura dati più performante 
per avere una collezione di pochi elementi (<10) e ricerche rapide. I I 
dati che devo organizzare sono questi:
 
- nome (stringa di tipo non standard)
- id (int)
- valore (variant)
 
Questa collezione sarà utilizzata da due metodi: il primo ha bisogno di 
ottenere l'id usando il nome; il secondo ha bisogno di ottenere il 
valore usando l'id. Vengono quindi sempre fatte due ricerche.
 
Nome e id sono valori univoci non ripetuti. 
Il costo di creazione della struttura dati non è rilevante. 
Gli oggetti una volta inseriti nella collezione non cambiano più.
 
Nella prima implementazione ho diviso i dati in due mappe:
nome->id
id->valore
Credo però che ci siano soluzioni migliori.
Qualche idea?
 
 
 
 
 


Del resto così si fa in qualsiasi DB: se non si vuole ciclare tutta una tabella
si mette un indice sul campo per cui si cerca. L'indice di solito è un B-tree
di qualche tipo (e.g. B*-tree mi sembra comune) visto che cerchi in O(logN) ed
è facile fare I/O. Nel tuo caso, visto che gli elementi sono così pochi,
anche le due mappe sembrano esagerate :) Quante volte devi cercare?
 
Ciao!

 Quante volte devi cercare?
 
decine di migliaia di volte
 


Codifica le chiavi in due array: int e hash(stringa) normalizzati in [0,10].
Così cerchi e scrivi in O(1). Meglio di così non si può fare.
Ma del resto è quello che fa una mappa normale che si appoggia ad un vettore
più largo di 10, in assenza di collisioni.
 
Sicuro che il tuo collo di bottiglia è su questa operazione?
 
Ciao!

 Sicuro che il tuo collo di bottiglia è su questa operazione?
 
Si, nella prima fase perchè coinvolge un confronto tra stringhe. 
Volevo provare con una std::unordered_map ma dovrei scrivere una funzione di 
hash specifica (il tipo non è standard) e non lo so fare :D
 

 hash specifica (il tipo non è standard) e non lo so fare :D
 
Nel frattempo ho cercato di "limare" tutto per evitare conversioni e copie 
inutili
 


In C++ esiste map della std lib
Fai una classe che contiene due map ognuna con le chiavi di ricerca 
appropriate
Dico una classe per mantenere le due mappe sincronizzate
 
 


A questo punto mi sa che il tuo problema è di diagnostica, più che di algoritmo.
 
Se sai che, come abbiamo capito, il tuo, sul tuo problema, gira in O(1), le cose
sono solo tre:
o ti devi mettere il cuore in pace,
o lo stai chiamando troppe volte in un algoritmo sbagliato a monte,
o il problema non è dove te l'immagini.
 
Visto quello che hai scritto, propenderei per la seconda o la terza.
 
Per eliminare la seconda ipotesi allarga la granularità dei tuoi test.
 
Per la terza... puoi fare l'"error analysis" classica: fornisci ad ogni step la
ground truth a rotazione, e controlla le performances.
 
Ciao!

 Dico una classe per mantenere le due mappe sincronizzate
 
E' la soluzione che ho già adottato, però sto studiando se c'è qualcosa di 
più performante.
 

 ground truth a rotazione, e controlla le performances.
 
Faccio ancora qualche test, cercherò di lavorare anche a livello di tipi e 
confronti. 
 


Ciao,
non ho capito se i metodi _devono_ essere 2. se no e il rapporto tra 
nome/id e id/valore è 1:1, li puoi mettere in un unica struttura. se si, 
terrei uniti i tre dati in un btree con doppio link (nome e id).
Un saluto.


Prima di pensarci troppo perche' non profili l'eseguibile e vedi se ne 
vale la pena ?
 

>
#include <string>
#include <iostream>
#include <map>
 
using namespace std;
class pippo
{
	map<string, int> sTOi;
	map<int, string> iTOv;
	map<int, string> iTOs;
 
public:
	void insert(string name, int id, string value);
	string operator [](string name);
	string operator [](int id);
	void remove(string name);
	void remove(int id);
	int count(void);
};
 
void pippo::insert(string name, int id, string value)
{
	sTOi.insert(pair<string, int>(name, id));
	iTOv.insert(pair<int, string>(id, value));
	iTOs.insert(pair<int, string>(id, name));
}
string pippo::operator[](string name)
{
	return iTOv.at(sTOi.at(name));
}
string pippo::operator[](int id)
{
	return iTOv.at(id);
}
void pippo::remove(string name)
{
	int id = sTOi[name];
	iTOv.erase(id);
	iTOs.erase(id);
	sTOi.erase(name);
}
void pippo::remove(int id)
{
	sTOi.erase(iTOs[id]);
	iTOv.erase(id);
	iTOs.erase(id);
}
int pippo::count(void)
{
	return sTOi.size();
}
void main(void)
{
	pippo db;
	db.insert("uno", 1, "vuno");
	db.insert("due", 2, "vdue");
	db.insert("tre", 3, "vtre");
	db.insert("quattro", 4, "vquattro");
	db.insert("cinque", 5, "vcinque");
	cout << "via id:" << db[5] << " via name:" << db["cinque"] << " count:" 
<< db.count() << endl;
	db.remove("uno");
	cout << "via id:" << db[3] << " via name:" << db["tre"] << " count:" << 
db.count() << endl;
	db.remove(3);
	cout << "via id:" << db[2] << " via name:" << db["due"] << " count:" << 
db.count() << endl;
	cin.get();
}

 Un saluto.
 
Grazie per l'aiuto :)