PDA

Visualizza la versione completa : Progetto strutture dati


salvodj88
12-07-2014, 09:43
Salve a tutti, devo fare un progetto didattico, ma per la prima volta in vita mia, non riesco proprio a partire e riuscire a capire come fare.



Sia S una collezione di stringhe. Ogni stringa in S è associata ad una serie di tag.
Ad esempio la stringa “ruota” è associata ai tag “automobile” e “panoramica”.
Implementare una struttura dati che permetta di gestire l’inserimento di nuove stringhe e la stampa delle stringhe a partire dai tag.

In particolare, le operazioni possibili sono:

a elem tag1 ... tagN -1: Associa i tag1 ... tagN (N>=1) alla stringa elem (i tag sono separati da uno spazio, il -1 indica la fine della specifica dell’operazione).
s subtag -1: Stampa il numero di tutte le stringhe distinte associate ai tag riferiti da “subtag” (il -1 indica la fine della specifica dell’operazione).

La stringa subtag si riferisce a tutti i tag di cui è prefisso. Ad esempio, il subtag aut si riferisce ai tag automobile, auto, autovettura, autista, ecc.
Se nessun tag è associato al subtag, stampare la stringa speciale
“missing”.

Note:

Un elemento può apparire più volte in operazioni di add. Esempio:

a pesca frutta sport -1
a pesca colore -1
a pesca frutta sport -1
a mela frutta -1


ogni tag può essere associato ad uno o più elementi. Nell’esempio sopra, frutta è associato sia a pesca che a mela.


INPUT
La lettura dovrà avvenire da standard input. Per ogni test, la prima linea contiene il carattere i e un intero n che rappresenta il numero di operazioni da effettuare.
Le restanti n linee contengono le operazioni da effettuare.

OUTPUT
L’output del programma è dato dalle stampe dell’operazione s.

N.B.: L’ultima riga conterrà la stringa “<END>”.


Il progetto puo essere fatto, a discrezione dell'utente, in java o c++.

Consigli sulla modalità per crearlo al meglio dell'efficenza??

MItaly
12-07-2014, 15:26
In C++ userei una std::map<std::string, std::set<std::string>> (in C++11 al posto del set "normale" userei un std::unordered_set).

La mappa (di fatto un albero RB) associa ad ogni tag le stringhe corrispondenti, e ti consente un lookup in tempo logaritmico; a differenza di una hashtable (std::unordered_map), che vuole sempre un match esatto, std::map ti consente di cercare anche i subtag in tempo logaritmico (usando il metodo lower_bound, che cerca un match di tipo >=).

Il set, a sua volta, ti consente di inserire impunemente gli elem senza dover controllare se sono già stati inseriti, ma evitando comunque di inserire duplicati. Dato che non hai bisogno di sfruttare il fatto che std::set mantiene gli elementi ordinati, come dicevo sopra in C++11 puoi usare unordered_set (di fatto una hashtable), che ti fornisce inserimento e lookup in tempo costante invece del tempo logaritmico del set "normale" (oltre ad avere una migliore cache locality).

Tra parentesi, ho un po' sistemato la formattazione del testo dell'esercizio, che tra a-capi di troppo, "o" al posto di elenchi puntati e un punto in cui si mischiavano pezzi di due sezioni diverse era abbastanza illeggibile, in futuro ti raccomando di starci più attento, un testo incasinato scoraggia molto a rispondere.

salvodj88
12-07-2014, 16:46
Grazie per la risposta e per la sistemazione del codice.

Potreste darmi anche una mano sul codice?

oregon
12-07-2014, 17:42
Perché non provi ad iniziarlo tu con le indicazioni che hai avuto? E per eventuali problemi si vede ...

salvodj88
12-07-2014, 23:53
Ci sto provando da oggi ma non riesco a partire.. questa volta non riesco proprio... aiutino???

MItaly
13-07-2014, 01:52
La struttura dati te l'ho detta, il parsing delle stringhe è banale... cosa non ti è chiaro?

salvodj88
13-07-2014, 08:32
L'implementazione. Allora creo una map <string, unordered_set string>
Poi metto il tag come chiave e l'elemento come valore?? Il controllo della sottostring che ritorna tutti il numero degli elementi che hanno nel tag la sottostring richiesta come ls fsccio??

MItaly
13-07-2014, 22:54
Poi metto il tag come chiave e l'elemento come valore??
Tag come chiave, e gli elementi sono elementi del set associato ad ogni tag.

Il controllo della sottostring che ritorna tutti il numero degli elementi che hanno nel tag la sottostring richiesta come ls fsccio??
Leggi la documentazione di std::map::lower_bound...

salvodj88
22-07-2014, 09:14
Siccome in C++ non riuscivo proprio a farlo.. non riuscivo a scrivere neanche un rigo di codice ho provato a farlo in java. A me nelle mie prove funziona, quando lo carico sul tester per far le prove date dall'università da come risposta TIME LIMIT, e come specifica è: "Il time limit può essere dovuto sia ad una implementazione poco efficiente che ad un loop."
Sapete dirmi secondo voi quale è il problema??? Quali modifiche apportare??



import java.util.HashMap;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Map;
import java.util.StringTokenizer;

/**
*
* @author salvo
*/
public class Struttura {

private final HashMap<String, String> chiavi;
private static BufferedReader br;
private final ArrayList<String> lista;

public Struttura() {
this.chiavi = new HashMap<String, String>();
this.lista = new ArrayList<String>();

}

public void leggi() {
br = new BufferedReader(new InputStreamReader(System.in));
int n = -1;

try {
String stringRead = br.readLine();
while (n != -1) {
StringTokenizer st = new StringTokenizer(stringRead, " ");
String primo = st.nextToken();
if (primo.equals("i")) {
n = Integer.parseInt(st.nextToken());
}
}
String id = "continua";
//esce dal ciclo solo quando viene letto <END>
while (!id.equals("<END>")) {
stringRead = br.readLine();
StringTokenizer st = new StringTokenizer(stringRead, " ");
id = st.nextToken().trim();
boolean esci = true;

// Se si stratta di un add entra in questo if
if (id.equals("a")) {
String elem = st.nextToken();
String tag = null;
while (esci) {
if (tag != "-1" && tag != null) {
this.chiavi.put(tag, elem);
}
tag = st.nextToken().trim();
if (tag.equals("-1")) {
esci = false;
}
}
}
// Se si tratta di una stampa entra in questo if
else if (id.equals("s")) {
String subTag = st.nextToken().trim();
lista.clear();
for (Map.Entry<String, String> entry : chiavi.entrySet()) {
String valore = entry.getKey().trim();
if (verificaSottostringa(subTag, valore)) {
this.lista.add(valore);
}
}
if (lista.isEmpty()) {
System.out.println("missing");
} else {
eliminaDupicati(lista);
System.out.println(lista.size());
}
}
}
br.close();
} catch (IOException ex) {
System.out.println("Impossibile leggere i dati");

}

}

// Verifica se è una sottostringa di un'altra parola
public boolean verificaSottostringa(String sottostringa, String daControllare) {
return daControllare.startsWith(sottostringa);
}

// Elimina i risultati da una lista
public void eliminaDupicati(ArrayList lista) {
for (int i = 0; i < lista.size(); i++) {
String currObj = (String) lista.get(i);
for (int k = i + 1; k < lista.size(); k++) {
String tmpObj = (String) lista.get(k);
if (currObj.equals(tmpObj)) {
lista.remove(k);
k--;
}
}
}
}


public static void main(String[] args) {
Struttura struttura = new Struttura();
struttura.leggi();

}
}


Un grazie a tutti quelli che mi aiuteranno.

Loading