kommentti2.0

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Timers;
using System.Diagnostics;



namespace CsharpTester
{
    //sparseArray on luokka, jolla käydään läpi pelkkiä rivejä tai kolumneja
    class sparseArray<T> : IEnumerable<KeyValuePair<ulong, T>>
    {

        public readonly ulong size;
        private ulong trueSize;
        Dictionary<ulong, T> d;
        //Konstruktori
        public sparseArray(ulong size)
        {
            this.d = new Dictionary<ulong, T>();
            this.size = size;
            this.trueSize = 0;
        }
        /*Palauttaa lisättyjen alkioiden määrän
        returns: ulong trueSize
        */
        public ulong realSize()
        {
            return trueSize;
        }
        /*Vaihtoehto get() ja set() metodeille
        @param ulong key
        returns: ulong key
        returns: ulong value
        */
        public T this[ulong key]
        {
            get
            {
                return get(key);
            }
            set
            {
                set(key, value);
            }
        }
        /*Asettaa rivin tai kolumnin alkioon arvon
        @param ulong i
        @param T val
        */
        public void set(ulong i, T val)
        {
            if (d.ContainsKey(i))
            {
                //if val is not initilized or as a value type equal to ""|0|0.0..etc there is no point in adding it as its value is already gettable
                if (EqualityComparer<T>.Default.Equals(val, default(T)))
                {
                    d.Remove(i);
                    trueSize--;
                    return;
                }
                d[i] = val;

            }
            else
            {
                //if val is not initilized or as a value type equal to ""|0|0.0..etc there is no point in adding it as its value is already gettable
                if (EqualityComparer<T>.Default.Equals(val, default(T))) return;
                d.Add(i, val);
                trueSize++;
            }

        }
        /*Palauttaa rivin tai kolumnin alkion arvon
        @param ulong i
        returns: T
        */
        public T get(ulong i)
        {
            if (d.ContainsKey(i)) return d[i];
            return default(T); // for value types this means a value equivalent to zero aka. int 0, string "",float 0.0f
                               // for objects this means a null reference
        }
        /*Käydään läpi koko rivi tai kolumni
        returns: KeyValuePair<ulong, T> item
        */
        public IEnumerator<KeyValuePair<ulong, T>> GetEnumerator()
        {
            d.OrderBy(x => x.Key); //sort O(n log n)
            foreach (KeyValuePair<ulong, T> item in d)
            {
                yield return item;
            }
        }


         IEnumerator<KeyValuePair<ulong, T>> IEnumerable<KeyValuePair<ulong, T>>.GetEnumerator()
        {
            d.OrderBy(x => x.Key); //sort O(n log n)
            foreach (KeyValuePair<ulong,T> item in d)
            {
                yield return item;
            }
        }


         System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
         {
             return GetEnumerator();
         }
    }
    //sparseMatrix on luokka, jolla käydään läpi matriiseja
    class sparseMatrix<T> : IEnumerable<KeyValuePair<ulong, sparseArray<T>>>
    {

        Dictionary<ulong, sparseArray<T>> dY;
        Dictionary<ulong, sparseArray<T>> dX;

        public readonly ulong sizeY;
        public readonly ulong sizeX;
        private ulong trueSizeY;
        private ulong trueSizeX;

        //Konstruktori
        public sparseMatrix(ulong y, ulong x)
        {
            this.dY = new Dictionary<ulong, sparseArray<T>>();
            this.dX = new Dictionary<ulong, sparseArray<T>>();
            this.sizeX = x;
            this.sizeY = y;
            trueSizeX = 0;
            trueSizeY = 0;
        }
        /*Palauttaa y -akselille lisättyjen alkioiden määrän
        returns: ulong trueSizeY
        */
        public ulong RealSizeY(){
            return trueSizeY;
        }
        /*Palauttaa x -akselille lisättyjen alkioiden määrän
        returns: ulong trueSizeX
        */
        public ulong RealSizeX()
        {
            return trueSizeX;
        }
        /*Vaihtoehto metodeille get() set()

        Esimerkki:
        typeT variable = sparseMatrix[x, y];
        sparseMatrix[x, y] = typeT variable;

        @param ulong y
        @param ulong x
        returns: ulong y, ulong x, ulong value
        */
        public T this[ulong y,ulong x]
        {
            get
            {
                return get(y,x);
            }
            set
            {
                set(y,x, value);
            }
        }
        /*Asettaa arvon matriisin alkiolle
        @param ulong y
        @param ulong x
        @param T val
        */
        public void set(ulong y, ulong x, T val)
        {
            //if val is not initilized or as a value type equal to ""|0|0.0..etc there is no point in adding it as its value is already gettable
            if (EqualityComparer<T>.Default.Equals(val, default(T))) return;
            if (dY.ContainsKey(y))
            {
                trueSizeX -= dY[y].realSize();
                dY[y].set(x, val);
                trueSizeX += dY[y].realSize();
                if (dX.ContainsKey(x))
                {
                    dX[x].set(y, val);
                }
                else
                {
                    dX.Add(x, new sparseArray<T>(sizeY));
                    dX[x].set(y, val);
                }
            }
            else
            {
                dY.Add(y, new sparseArray<T>(sizeX));
                dY[y].set(x, val);
                if(dY[y].realSize() > 0)trueSizeY++;
                if (dX.ContainsKey(x))
                {
                    dX[x].set(y, val);
                }
                else
                {
                    dX.Add(x, new sparseArray<T>(sizeY));
                    dX[x].set(y, val);
                }
            }
        }
        /*Palauttaa alkion matriisista
        @param ulong y
        @param ulong x
        returns: T
        */
        public T get(ulong y, ulong x)
        {
            if (y > sizeY | x > sizeX)
                throw new NullReferenceException("@LooseMatrix get");
            if (dY.ContainsKey(y)) return dY[y].get(x);
            return default(T);
        }
        /*Palauttaa rivin alkiot sanakirjana
        @param ulong y
        returns: Dictionary dY[ulong y]
        */
        public sparseArray<T> getRow(ulong y)
        {
            if (dY.ContainsKey(y))
                return dY[y];
            else
                return new sparseArray<T>(sizeX);
        }
        /*Palauttaa kolumnin alkiot sanakirjana
        @param ulong y
        returns: Dictionary dY[ulong y]
        */
        public sparseArray<T> getColumn(ulong columnNumber)
        {
            if (dY.ContainsKey(columnNumber))
                return dX[columnNumber];
            else
                return new sparseArray<T>(sizeX);
        }
        /*Käy läpi sparseMatrixin
        returns: KeyValuePair<ulong, sparseArray<T>> item
        */
        public IEnumerator<KeyValuePair<ulong, sparseArray<T>>> GetEnumerator()
        {
            dY.OrderBy(x => x.Key);
            foreach (KeyValuePair<ulong, sparseArray<T>> item in dY)
            {
                yield return item;
            }
        }

        IEnumerator<KeyValuePair<ulong, sparseArray<T>>> IEnumerable<KeyValuePair<ulong, sparseArray<T>>>.GetEnumerator()
        {
            dY.OrderBy(x => x.Key);
            foreach (KeyValuePair<ulong, sparseArray<T>> item in dY)
            {
                yield return item;
            }
        }

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            dY.OrderBy(x => x.Key);
            foreach (KeyValuePair<ulong, sparseArray<T>> item in dY)
            {
                yield return item;
            }
        }
        /*Tulostaa matriisit oikeassa muodossa
        returns String sb
        */
        public string printableString()
        {
            StringBuilder sb = new StringBuilder();
            for (ulong y = 0; y < sizeY; y++)
            {

                sb.Append('[');
                for (ulong x = 0; x < sizeX; x++)
                {
                    sb.Append(" " + get(y, x) + " ");
                }
                sb.Append("]\n");
            }
            return sb.ToString();
        }
    }

    class Program
    {
        static sparseMatrix<ushort> matrixProduct(sparseMatrix<ushort> a, sparseMatrix<ushort> b)
        {
            sparseMatrix<ushort> c = new sparseMatrix<ushort>(Math.Max(a.sizeY, b.sizeY), Math.Max(a.sizeY, b.sizeY));
            for (ulong y = 0; y < c.sizeY; y++)
            {
               sparseArray<ushort> rowY = a.getRow(y);
                for (ulong x = 0; x < c.sizeX; x++)
                {
                    sparseArray<ushort> rowX = b.getColumn(x);

                    ushort res = 0;
                    foreach (KeyValuePair<ulong,ushort> kvp in rowY)
                    {
                        res += (ushort) (kvp.Value * rowX[kvp.Key]);
                    }
                    c[y,x] = res;
                }
            }

            return c;
        }
        static void Main(string[] args)
                {
            Console.WriteLine("Anna matriisien koot (muodossa 3x3(valilyontivaliin)45x245  tai muun muotoinen vastaus jotta ajetaan vertailut normaaleihin matriiseihin");
            String tmp = Console.ReadLine();
            tmp = tmp.Trim();
            string[] kootString = tmp.Split('x',' ');

            if (kootString.Length > 3) //on kaksi eri kokoa annettu
            {
                UInt16[] koot = new ushort[kootString.Length];
                for (int i = 0; i < kootString.Length; i++)
                {
                    UInt16.TryParse(kootString[i], out koot[i]);
                }
                sparseMatrix<ushort> a = new sparseMatrix<ushort>(koot[0], koot[1]);
                sparseMatrix<ushort> b = new sparseMatrix<ushort>(koot[2], koot[3]);
                sparseMatrix<ushort> c;
                Console.WriteLine("Haluatko syöttää itse numerot? Anna tyhjä vastaus jos et halua");
                string v = Console.ReadLine();
                v = v.Trim();
                if (v != "")
                {
                    for (int o = 0; o < 2; o++)
                    {
                        sparseMatrix<ushort> current;
                        if (o == 0) current = a;
                        else current = b;
                        Console.WriteLine("Syötä matriisin: " + o + " rivit:");
                        for (ulong i = 0; i < a.sizeY; i++)
                        {
                            Console.WriteLine("Syötä rivi: " + i);
                            string s = Console.ReadLine();
                            s = s.Trim();
                            string[] arvotString = s.Split(' ');
                            UInt16[] arvot = new UInt16[arvotString.Length];
                            for (uint j = 0; j < arvotString.Length; j++)
                            {
                                UInt16.TryParse(arvotString[j], out koot[j]);
                                current[i, (ulong)j] = koot[j];
                            }

                        }
                    }
                    Console.WriteLine("Matrix 1:");
                    Console.WriteLine(a.printableString());
                    Console.WriteLine("\nMatrix 2:");
                    Console.WriteLine(b.printableString());
                    c = matrixProduct(a, b);
                    //tulostetaan tulos matriisi
                    Console.WriteLine("\nResult Matrix:");
                    Console.WriteLine(c.printableString());
                    Console.ReadKey();
                }
                else
                {
                    byte[] rngBuffer = new byte[sizeof(ushort)];
                    for (int o = 0; o < 2; o++)
                    {
                        sparseMatrix<ushort> current;
                        if (o == 0) current = a;
                        else current = b;
                        Random r = new Random();
                        int rI = r.Next(1, 200);
                        int rI2 = r.Next(1, 200);
                        uint rIu = (uint)(Math.Abs(rI));
                        uint rIu2 = (uint)(Math.Abs(rI));
                        for (ulong y = 0; y < current.sizeY; y+= rIu)
                        {
                            for (ulong x = 0; x < current.sizeX; x += rIu2)
                            {
                                //generoidaan
                                r.NextBytes(rngBuffer);
                                ushort random = BitConverter.ToUInt16(rngBuffer, 0);
                                current[y, x] = random;
                            }
                        }
                    }
                    //tulostetaan generoidut
                    Console.WriteLine("Matrix 1:");
                    Console.WriteLine(a.printableString());
                    Console.WriteLine("\nMatrix 2:");
                    Console.WriteLine(b.printableString());
                    c = matrixProduct(a, b);
                    //tulostetaan tulos matriisi
                    Console.WriteLine("\nResult Matrix:");
                    Console.WriteLine(c.printableString());
                    Console.ReadKey();
                }
            }
            else //ajetaan vertailut normaaleihin matriiseihin
            {
                ulong testSize = 126;
                ulong fillrate = 100;
                var asd = new sparseMatrix<ushort>(testSize, testSize);
                for (int i = 0; i < 7; i++)
                {
                    testSize = testSize * 2;
                    Random rng = new Random();
                    byte[] rngBuffer = new byte[sizeof(ushort)];
                    var a = new sparseMatrix<ushort>(testSize, testSize);
                    var b = new sparseMatrix<ushort>(testSize, testSize);
                    Stopwatch time = new Stopwatch();
                    time.Restart();

                    for (ulong y = 0; y < a.sizeY; y++)
                    {
                        for (ulong x = 0; x < a.sizeX; x++)
                        {
                            if (x % fillrate == 0)
                            {
                                rng.NextBytes(rngBuffer);

                                ushort u = BitConverter.ToUInt16(rngBuffer, 0);
                                a.set(y, x, u);
                                rng.NextBytes(rngBuffer);
                                u = BitConverter.ToUInt16(rngBuffer, 0);
                                b.set(y - 1, x - 1, u);
                            }
                        }
                    }

                    string populateString = "SPARSE " + time.Elapsed + " population:" + a.RealSizeX();
                    time.Restart();
                    var c = new sparseMatrix<ushort>(a.sizeY, b.sizeX);
                    foreach (KeyValuePair<ulong, sparseArray<ushort>> y in a)
                    {
                        foreach (KeyValuePair<ulong, ushort> x in y.Value)
                        {
                            c.set(y.Key, x.Key, (ushort)(a.get(y.Key, x.Key) + b.get(y.Key, x.Key)));
                        }
                    }
                    string addingString = "SPARSE " + time.Elapsed;
                    time.Restart();

                    ushort[][] matA = new ushort[testSize][];
                    ushort[][] matB = new ushort[testSize][];

                    for (ulong y = 0; y < testSize; y++)
                    {
                        matA[y] = new ushort[testSize];
                        matB[y] = new ushort[testSize];
                        for (ulong x = 0; x < a.sizeX; x++)
                        {
                            if (x % fillrate == 0)
                            {
                                rng.NextBytes(rngBuffer);
                                ushort u = BitConverter.ToUInt16(rngBuffer, 0);
                                matA[y][x] = u;
                                rng.NextBytes(rngBuffer);
                                u = BitConverter.ToUInt16(rngBuffer, 0);
                                matB[y][x] = u;
                            }
                            else
                            {
                                matA[y][x] = 0;
                                matB[y][x] = 0;
                            }
                        }
                    }
                    Console.WriteLine("Populating");
                    Console.WriteLine(populateString);
                    Console.WriteLine("MATRIX " + time.Elapsed + " Size: " + (a.sizeX * a.sizeY));

                    time.Restart();
                    {
                        ushort[,] matC = new ushort[testSize, testSize];
                        for (ulong y = 0; y < a.sizeY; y++)
                        {
                            for (ulong x = 0; x < a.sizeX; x++)
                            {
                                matB[y][x] = (ushort)(matB[y][x] + matA[y][x]);
                            }
                        }
                    }
                    Console.WriteLine("Adding:");
                    Console.WriteLine(addingString);
                    Console.WriteLine("MATRIX " + time.Elapsed);
                    Console.WriteLine();
                    time.Restart();
                }

                Console.ReadLine();
            }
        }
    }
}