Hin und wieder will man wieder etwas einfacheres machen und etwas, dass es schon 100.000mal auf dieser Welt gibt auch wieder neu erfinden. Ich hoffe ich habe jetzt hier nicht irgendein Softwarepatent gröber verletzt, wenn ja – mea culpa.
Die Sparse-Matrix hat gegenüber einem Array vor allem Vorteile, wenn man nur wenige Elemente der Matrix (bzw. des Arrays) belegt, da wäre eine Array eine Speicherverschwendung (überhaupt bei grossen Dimensionen). Anbei meine einfache Implementierung, ich habe bewusst nur eine einfache .NET Liste mit Tupeln verwendet, zur Abfrage der Liste verwende ich einfach LINQ (es ist einfach zu praktisch…) und hab noch eine kleine API draufgesetzt.
Sicherlich gäbe es auch einen effizientere Datenstrukturen dafür, aber ich denke für die meisten Fälle wird wohl die einfache Liste ausreichend sein, bzw. müsste man dann ja auch noch Vergleichsmessungen anstellen.
Mit dabei sind auch ein paar klitzekleine Tests, natürlich hätte die man auch als Unit-Tests auch ausführen können, aber sooo viel Bock hatte ich dann auch nicht.
using System; using System.Collections.Generic; using System.Linq; namespace SparseMatrix { class Program { static void Main(string[] args) { var sm = new SparseMatrix(); sm.SetAt(5, 6, "Hallo"); sm.SetAt(6, 7, "Welt!"); Console.WriteLine(sm.GetAt(5, 6)); Console.WriteLine(sm.GetAt(6, 7)); sm.SetAt(6, 7, "Harald"); Console.WriteLine(sm.GetAt(6, 7)); Console.WriteLine("RowCount row=7: {0}", sm.GetRowCount(6)); Console.WriteLine("ColCount col=6: {0}", sm.GetColumnCount(7)); Console.WriteLine("Entferne Element auf row=6 / col=7"); sm.SetAt(6, 7, null); Console.WriteLine("RowCount row=7: {0}", sm.GetRowCount(6)); Console.WriteLine("ColCount col=6: {0}", sm.GetColumnCount(7)); sm[6, 6] = "Blogleser!"; List results = sm.GetRowData(6).ToList(); // Sollte "Hallo Blogleser " ausgeben foreach (string s in results) Console.Write("{0} ", s); Console.WriteLine(); Console.WriteLine("Auf Postion 5/6 steht {0}", sm[5, 6]); Console.ReadLine(); } } public class SparseMatrix { private List<Tuple<int, int, T>> data = new List<Tuple<int, int, T>>(); private Tuple<int, int, T> getTuple(int row, int col) { return data.Where(e => e.Item1 == row && e.Item2 == col).FirstOrDefault(); } public T GetAt(int row, int col) { var e = getTuple(row, col); if (e == null) { return default(T); } else { return e.Item3; } } public void RemoveAt(int row, int col) { var e = getTuple(row, col); if (e != null) data.Remove(e); return; } public void SetAt(int row, int col, T value) { var e = getTuple(row, col); if (e == null && EqualityComparer.Default.Equals(value, default(T))) { return; } if (e != null && EqualityComparer.Default.Equals(value, default(T))) { data.Remove(e); return; } if (e == null) { data.Add(new Tuple<int, int, T>(row, col, value)); return; } data.Remove(e); data.Add(new Tuple<int, int, T>(row, col, value)); } public IEnumerable GetRowData(int row) { return data.Where(e => e.Item2 == row).Select(e => e.Item3); } public IEnumerable GetColumnData(int col) { return data.Where(e => e.Item1 == col).Select(e => e.Item3); } public int GetColumnCount(int col) { return data.Where(e => e.Item2 == col).Count(); } public int GetRowCount(int row) { return data.Where(e => e.Item1 == row).Count(); } public T this[int row, int col] { get { return GetAt(row, col); } set { SetAt(row, col, value); } } } }