Struttura dati veloce per ricerca pochi elementi

[_merlinO_]

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?

[f***@gmail.com]

Post by _merlinO_
Sto studiando quale potrebbe essere la struttura dati più performante
per avere una collezione di pochi elementi (<10) e ricerche rapide. I I
- 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ù.
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!

[_merlinO_]

Post by f***@gmail.com
Quante volte devi cercare?

decine di migliaia di volte

[f***@gmail.com]

Post by _merlinO_

Post by f***@gmail.com
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!

[_merlinO_]

Post by f***@gmail.com
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

[_merlinO_]

Post by _merlinO_
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

Nel frattempo ho cercato di "limare" tutto per evitare conversioni e copie
inutili

[f***@gmail.com]

Post by _merlinO_

Post by _merlinO_
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

Nel frattempo ho cercato di "limare" tutto per evitare conversioni e copie
inutili

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!

[_merlinO_]

***@gmail.com <***@gmail.com> ha scritto:

[...]

Post by f***@gmail.com
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.

Purtroppo non ho giurisdizione sul chiamante, è un sistema di late binding che
richiede nome e id per un componente sviluppato da terze parti.

Post by f***@gmail.com
Per la terza... puoi fare l'"error analysis" classica: fornisci ad ogni step la
ground truth a rotazione, e controlla le performances.

Faccio ancora qualche test, cercherò di lavorare anche a livello di tipi e
confronti.

[enoquick]

Post by _merlinO_
Sto studiando quale potrebbe essere la struttura dati più performante
per avere una collezione di pochi elementi (<10) e ricerche rapide. I I
- 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ù.
nome->id
id->valore
Credo però che ci siano soluzioni migliori.
Qualche idea?

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

[_merlinO_]

Post by enoquick
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

E' la soluzione che ho già adottato, però sto studiando se c'è qualcosa di
più performante.

[enoquick]

Post by _merlinO_

Post by enoquick
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

E' la soluzione che ho già adottato, però sto studiando se c'è qualcosa di
più performante.

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

[jak]

Post by _merlinO_
Sto studiando quale potrebbe essere la struttura dati più performante
per avere una collezione di pochi elementi (<10) e ricerche rapide. I I
- 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ù.
nome->id
id->valore
Credo però che ci siano soluzioni migliori.
Qualche idea?

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.

[jak]

Post by _merlinO_
Sto studiando quale potrebbe essere la struttura dati più performante
per avere una collezione di pochi elementi (<10) e ricerche rapide. I I
- 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ù.
nome->id
id->valore
Credo però che ci siano soluzioni migliori.
Qualche idea?

#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();
}

[_merlinO_]

Post by jak
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).

Devono essere due per forza, vengono chiamati in tempi diversi

Post by jak
Un saluto.

Grazie per l'aiuto :)