|
|
|
|
Strumenti |
18-10-2013, 14:52 | #1 |
Senior Member
Iscritto dal: Apr 2010
Messaggi: 1707
|
[C #] Utilizzo di strutture Dictionary
Buonasera, sto realizzando un programma in C # in cui devo salvare gli elementi all'interno di un Dizionario di tipo Dictionary<KeyValueTriple<int, int, double>, double> , che rappresenta gli archi di un grafo, dove KeyValueTriple è un tipo di dato che ho realizzato io, di seguito fornirò il codice. Il codice che posto è (molto) liberamente ispirato ad un pezzo di codice open source, dell'Università dell'Arizona, serve che posti anche le note di copyright? Utilizzo un oggetto KeyValueTriple, perché ci possono essere più archi con peso diverso che partono dal nodo i e arrivano al nodo j.
Fino a che utilizzavo al posto di un KeyValueTriple un KeyValuePair, tipo predefinito, non riscontravo problemi di nessun genere, cancellavo le chiavi dal dizionario senza alcun problema, passando ai KeyValueTriple inizio a non riuscire più a rimuovere gli elementi nel modo corretto, il risultato sia della remove che della remove_edge dà sempre false, nonostante gli passi un elemento che appartiene al dizionario, verificato, stampando tutti gli elementi. Per semplificare ho realizzato un programma di tipo ConsoleApplication, non ho fatto un'interfaccia grafica, è soltanto un programma di base, anche perché il resto non potrei comunque postarlo. Teoricamente se non ci fossero alternative, potrei risolverlo ricrendo un nuovo dizionario con tutti gli elementi tranne quello che deve essere rimosso, ma ovviamente non è la soluzione migliore, visto che sarebbe piuttosto inefficiente, oppure ancora posso cambiare la struttura dati utilizzata, ma dovrei cambiare un buon numero di righe di codice del resto del programma, e sinceramente vorrei evitarlo. Struttura dati del grafo: Codice:
graph.cs using System; using System.IO; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace ConsoleApplication2 { public class Graph { public static double DISCONNECTED; // index for edge weights in the graph public Dictionary<KeyValueTriple<int, int, double>, double> _vertex_pair_weight_index; // the number of arcs in the graph public int _edge_num; /** * Constructor 1 * @param data_file_name */ public Graph(string data_file_name) { DISCONNECTED = double.MaxValue; // index for edge weights in the graph _vertex_pair_weight_index = new Dictionary<KeyValueTriple<int, int, double>, double>(); // the number of arcs in the graph _edge_num = 0; import_from_file(data_file_name); } /** * Constructor 2 * * @param graph */ public Graph(Graph graph_) { DISCONNECTED = double.MaxValue; // index for edge weights in the graph _vertex_pair_weight_index = new Dictionary<KeyValueTriple<int, int, double>, double>(graph_._vertex_pair_weight_index); // the number of arcs in the graph _edge_num = graph_._edge_num; } /** * Default constructor */ public Graph() { DISCONNECTED = double.MaxValue; // index for edge weights in the graph _vertex_pair_weight_index = new Dictionary<KeyValueTriple<int, int, double>, double>(); // the number of arcs in the graph _edge_num = 0; } /** * Clear members of the graph. */ public void Clear() { _edge_num = 0; _vertex_pair_weight_index.Clear(); } /** * There is a requirement for the input graph. * The ids of vertices must be consecutive. * * @param data_file_name */ public void import_from_file(string data_file_name) { try { // 1. read the file and put the content in the buffer TextReader bufRead = new StreamReader(data_file_name); bool is_first_line = true; string line; // String that holds current file line // 2. Read first line line = bufRead.ReadLine(); while (line != null) { // 2.1 skip the empty line if (line.Trim().Equals("")) { line = bufRead.ReadLine(); continue; } // 2.2 generate nodes and edges for the graph if (is_first_line) { //2.2.1 obtain the number of nodes in the graph is_first_line = false; } else { //2.2.2 find a new edge and put it in the graph string[] str_list = line.Trim().Split('\r', '\n', '\t', ' '); int start_vertex_id = int.Parse(str_list[0]); int end_vertex_id = int.Parse(str_list[1]); double weight = double.Parse(str_list[2]); add_edge(start_vertex_id, end_vertex_id, weight); } // line = bufRead.ReadLine(); } bufRead.Close(); } catch (IOException e) { // If another exception is generated, print a stack trace Console.Write(e.Message); } } /** * Note that this may not be used externally, because some other members in the class * should be updated at the same time. * * @param start_vertex_id * @param end_vertex_id * @param weight */ public void add_edge(int start_vertex_id, int end_vertex_id, double weight) { // actually, we should make sure all vertices ids must be correct. if (start_vertex_id == end_vertex_id) { throw new System.ArgumentOutOfRangeException("The edge from " + start_vertex_id + " to " + end_vertex_id + " does not exist in the graph."); } // store the new edge _vertex_pair_weight_index.Add(new KeyValueTriple<int, int, double>(start_vertex_id, end_vertex_id, weight), weight); ++_edge_num; } } public class VariableGraph : Graph { HashSet<KeyValueTriple<int, int, double>> _rem_edge_set; /** * Default constructor */ public VariableGraph() { _rem_edge_set = new HashSet<KeyValueTriple<int, int, double>>(); } /** * Constructor 1 * * @param data_file_name */ public VariableGraph(string data_file_name) : base(data_file_name) { _rem_edge_set = new HashSet<KeyValueTriple<int, int, double>>(); } /** * Constructor 2 * * @param graph */ public VariableGraph(Graph graph) : base(graph) { _rem_edge_set = new HashSet<KeyValueTriple<int, int, double>>(); } /** * Add an edge to the set of removed edges * * @param edge */ public void remove_edge(KeyValueTriple<int, int, double> edge) { Console.WriteLine("I'M REMOVING AN EDGE <" + edge.key1 + "," + edge.key2 + "," + edge.value + "> -> " + edge.value); _rem_edge_set.Add(edge); bool esito = _vertex_pair_weight_index.Remove(edge); Console.WriteLine("Esito della rimozione, remove_edge : " + esito); if (_vertex_pair_weight_index.ContainsKey(edge)) Console.WriteLine("L'ARCO E' ANCORA PRESENTE\n"); _vertex_pair_weight_index.Add(edge, DISCONNECTED); } public void recover_removed_edges() { _rem_edge_set.Clear(); } public void recover_removed_edge(KeyValueTriple<int, int, double> edge) { Console.WriteLine("I'M RECOVERING A REMOVED EDGE <" + edge.key1 + "," + edge.key2 + "," + edge.value + "> -> " + edge.value); bool esito = _rem_edge_set.Remove(edge); Console.WriteLine("Esito della rimozione recover_removed_edge: " + esito); if (_rem_edge_set.Contains(edge)) Console.WriteLine("L'ARCO E' ANCORA VIRTUALMENTE NON RIPRISTINATO\n"); _vertex_pair_weight_index.Add(edge, DISCONNECTED); } } //tripla da utilizzare all'interno del dizionario public class KeyValueTriple<TKey1, TKey2, TValue> { public TKey1 key1; public TKey2 key2; public TValue value; public KeyValueTriple(TKey1 key1, TKey2 key2, TValue value) { this.key1 = key1; this.key2 = key2; this.value = value; } public TKey1 getKey1() { return key1; } public TKey2 getKey2() { return key2; } public TValue getValue() { return value; } public override bool Equals(System.Object obj) { if (obj == null) return false; KeyValueTriple<int, int, double> k = new KeyValueTriple<int, int, double>(1, 1, 1.0); //serve per avere il tipo Type t = k.GetType(); if (obj.GetType() != t) { throw new InvalidCastException("L'oggetto passato non è del tipo corretto\n"); } KeyValueTriple<TKey1, TKey2, TValue> kvt = (KeyValueTriple<TKey1, TKey2, TValue>)obj; if ((this.key1.Equals(kvt.key1)) && (this.key2.Equals(kvt.key2)) && (this.value.Equals(kvt.value))) return true; return false; } public override int GetHashCode() { return base.GetHashCode(); } } } Codice:
program.cs using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace ConsoleApplication2 { class Program { static VariableGraph vg = new VariableGraph("test_7"); static void printAll() { Dictionary<KeyValueTriple<int, int, double>, double> dic2 = vg._vertex_pair_weight_index; foreach (KeyValuePair<KeyValueTriple<int, int, double>, double> kvp in dic2) { KeyValueTriple<int, int, double> kvt = kvp.Key; KeyValueTriple<int, int, double> kvtCopy = new KeyValueTriple<int, int, double>(kvt.key1, kvt.key2, kvt.value); double value = kvp.Value; Console.WriteLine("<" + kvt.key1 + "," + kvt.key2 + "," + kvt.value + " > " + value + " -> " + " equals : " + kvt.Equals(kvtCopy)); } } static void Main(string[] args) { Dictionary<KeyValueTriple<int, int, double>, double> dic = vg._vertex_pair_weight_index; printAll(); vg.remove_edge(new KeyValueTriple<int, int, double>(1, 3, 3.0)); Console.WriteLine("-------------------------------"); printAll(); vg.recover_removed_edge(new KeyValueTriple<int, int, double>(1, 3, 3.0)); Console.WriteLine("-------------------------------"); printAll(); Console.ReadLine(); } } } Codice:
test_7 7 0 1 1 1 0 1 0 2 7 2 0 7 1 2 1 2 1 1 1 3 3 1 3 4 3 1 3 1 4 2 4 1 2 2 4 4 4 2 4 3 5 6 5 3 6 3 4 1 4 3 1 4 5 2 5 4 2 3 6 100 6 3 100 6 1 1 1 6 1
__________________
NEW : Java problema pannello con barra scorrimentonew :Insert pag paypal PHP Basi x notebook cinesi Cerco notebook HP PHP problemi formattazione pagina SELECT Query PHP problem Problema Redirect PHP Project wi-fi Cerco PC C# Dictionary problem |
19-10-2013, 15:57 | #2 |
Senior Member
Iscritto dal: Apr 2010
Messaggi: 1707
|
Up!
__________________
NEW : Java problema pannello con barra scorrimentonew :Insert pag paypal PHP Basi x notebook cinesi Cerco notebook HP PHP problemi formattazione pagina SELECT Query PHP problem Problema Redirect PHP Project wi-fi Cerco PC C# Dictionary problem |
22-10-2013, 00:21 | #3 |
Senior Member
Iscritto dal: May 2004
Città: Londra (Torino)
Messaggi: 3691
|
Implementa l'interfaccia IEquatable<KeyValueTriple>
(Per questioni di chiarezza e pulizia) E scrivi un GetHashCode che abbia un senso, non il semplice public override int GetHashCode() { return base.GetHashCode(); } Il tuo hashcode deve dipendere dagli hascode degli elementi che compongono la chiave, in questa classe tutti e 3 gli elementi. Il criterio e' che oggetti uguali devono avere lo stesso hashcode. Richiamare l'hashcode base e' il problema principale. 2 oggetti (object), anche se hanno contenuti uguali avranno hashcode diverso, perche' la object.GetHashCode restituisce l'indirizzo di memoria, che e' appunto diverso in 2 istanze diverse, quand'anche uguali in contenuto. Per quello che non trovi gli elementi nella Dictionary, anche se apparentemente presenti. Quindi prima approssimazione metti Key1.GetHashCode() + Key2.GetHashCode() + Key3.GetHashCode() Meglio sarebbe cucinare per qualche fattore primo moltiplicativo per evitare quanto piu' possibile overlapping di valori tra oggetti diversi che avranno invece stessa HashCode (Che non e' vietato, solo meno efficiente)
__________________
Se pensi che il tuo codice sia troppo complesso da capire senza commenti, e' segno che molto probabilmente il tuo codice e' semplicemente mal scritto. E se pensi di avere bisogno di un nuovo commento, significa che ti manca almeno un test. |
22-10-2013, 08:41 | #4 | |
Senior Member
Iscritto dal: Apr 2010
Messaggi: 1707
|
Quote:
Codice:
public override bool Equals(KeyValueTriple<TKey1, TKey2, TValue> obj) { if (obj == null) return false; if ((this.key1.Equals(obj.key1)) && (this.key2.Equals(obj.key2)) && (this.value.Equals(obj.value))) return true; return false; } public override int GetHashCode() { if ((key1 == null) || (key2 == null) || (value == null)) throw new NullReferenceException("Arguments null"); return key1.GetHashCode() + key2.GetHashCode() + value.GetHashCode(); } Mi viene restituito l'errore "Error 1 'ConsoleApplication3.KeyValueTriple<TKey1,TKey2,TValue>.Equals(ConsoleApplication3.KeyValueTriple<TKey1,TKey2,TValue>)': no suitable method found to override" Eppure dovrebbe effettuare l'override del metodo Equals di IEquatable<KeyValueTriple<TKey1, TKey2, TValue>> L'override del metodo Equals di Object viene effettuata senza problemi, ho anche provato a toglierla, per vedere se ci sono dei conflitti, ma non riesco a risolvere. Per il resto il programma funziona, anche senza effettuare l'override del metodo Equals.
__________________
NEW : Java problema pannello con barra scorrimentonew :Insert pag paypal PHP Basi x notebook cinesi Cerco notebook HP PHP problemi formattazione pagina SELECT Query PHP problem Problema Redirect PHP Project wi-fi Cerco PC C# Dictionary problem Ultima modifica di LS1987 : 22-10-2013 alle 08:48. Motivo: Funziona lo stesso, l'errore che ho postato è ignorabile. |
|
27-10-2013, 11:18 | #5 |
Senior Member
Iscritto dal: May 2004
Città: Londra (Torino)
Messaggi: 3691
|
Bene la GetHashcode(), che era di fatto il tuo problema.
Per quanto riguarda la "Equals", togli semplicemente la keyword "override" Non stai facendo override di quel metodo. Stai implementando un contratto di interfaccia, che non ha bisgno di override, perche' di fatto non esiste un metodo base, in quanto le interfaccie non hanno body.
__________________
Se pensi che il tuo codice sia troppo complesso da capire senza commenti, e' segno che molto probabilmente il tuo codice e' semplicemente mal scritto. E se pensi di avere bisogno di un nuovo commento, significa che ti manca almeno un test. |
Strumenti | |
|
|
Tutti gli orari sono GMT +1. Ora sono le: 09:10.