source: esimerkit/2015k/live/live19/LukujenEsiintymiskerrat/LukujenEsiintymiskerrat.cs @ 1392

Revision 1094, 7.6 KB checked in by anlakane, 2 years ago (diff)
Line 
1using System;
2using System.Text;
3using System.Linq;
4using System.Collections.Generic;
5using System.Diagnostics;
6
7/// @author Antti-Jussi Lakanen
8/// @version 17.3.2015
9///
10/// <summary>
11/// Tutkitaan lukujen esiintymiskertoja.
12/// Tässä tehtiin kolme eri versiota: järjestetyllä
13/// aineistolla, järjestämättömällä aineistolla,
14/// sekä LINQ:n avulla.
15/// </summary>
16public class LukujenEsiintymiskerrat
17{
18    /// <summary>
19    /// Kutsut ja ajastukset.
20    /// </summary>
21    public static void Main()
22    {
23        // int[] luvut = { 1, 2, 3, 34, 34, 2, 1, 34, 1, 1, 1 };
24
25        Random r = new Random();
26        int montako = 100000;
27
28        int[] luvut = Tayta(r, montako, 0, 1000);
29
30        Stopwatch sw = Stopwatch.StartNew();
31        int[] esiintymat = LaskeEsiintymat(luvut);
32        sw.Stop();
33        double ms = sw.Elapsed.TotalMilliseconds;
34        Console.WriteLine("Sortatulla Dictionarylla hommaan meni " + ms + " millisekuntia.");
35
36        sw = Stopwatch.StartNew();
37        esiintymat = LaskeEsiintymat2(luvut);
38        sw.Stop();
39        ms = sw.Elapsed.TotalMilliseconds;
40        Console.WriteLine("Ei-sortatulla Dictionarylla hommaan meni " + ms + " millisekuntia.");
41       
42        sw = Stopwatch.StartNew();
43        esiintymat = LaskeEsiintymat3(luvut);
44        sw.Stop();
45        ms = sw.Elapsed.TotalMilliseconds;
46        Console.WriteLine("LINQ:lla hommaan meni " + ms + " millisekuntia.");
47    }
48
49    /// <summary>
50    /// Täytä satunnaisia lukuja taulukkoon
51    /// </summary>
52    /// <param name="r">Random-olio</param>
53    /// <param name="montako">Montako lukua taulukkoon</param>
54    /// <param name="min">Minimi</param>
55    /// <param name="max">Maksimi (ekslusiivinen)</param>
56    /// <returns>Luvut</returns>
57    public static int[] Tayta(Random r, int montako, int min, int max)
58    {
59        int[] luvut = new int[montako];
60        for (int i = 0; i < luvut.Length; i++)
61        {
62            luvut[i] = r.Next(min, max);
63        }
64        return luvut;
65    }
66
67
68    /// <summary>
69    /// Lisätään alkiot ja niiden esiintymismäärät key-value-pareina
70    /// Dictionary-tietorakenteeseen. Lopuksi järjestetään tietorakenne
71    /// esiintymismäärien perusteella, ja valitaan pelkät avaimet.
72    /// </summary>
73    /// <param name="luvut">Aineisto</param>
74    /// <returns>Esiintymiskerrat (harvimmin esiintyvä ensin, useiten
75    /// esiintyvä viimeisenä.)</returns>
76    /// <example>
77    /// <pre name="test">
78    ///  int[] luvut = { 1, 2, 3, 34, 34, 2, 1, 34, 1, 1, 1 };
79    ///  int[] esiintymat = LukujenEsiintymiskerrat.LaskeEsiintymat(luvut);
80    ///  String.Join(" ", esiintymat) === "3 2 34 1";
81    ///  String.Join(" ", LukujenEsiintymiskerrat.LaskeEsiintymat(new int[]{})) === "";
82    ///  String.Join(" ", LukujenEsiintymiskerrat.LaskeEsiintymat(new int[]{1})) === "1";
83    ///  String.Join(" ", LukujenEsiintymiskerrat.LaskeEsiintymat(new int[]{1,2,2})) === "1 2";
84    ///  String.Join(" ", LukujenEsiintymiskerrat.LaskeEsiintymat(new int[]{1,2,2,3})) === "1 3 2";
85    /// </pre>
86    /// </example>
87    public static int[] LaskeEsiintymat(int[] luvut)
88    {
89        List<int> lista = luvut.ToList<int>();
90        lista.Sort(); // järjestää nousevaan järjestykseen
91        if (lista.Count == 0) return new int[] { };
92
93        Dictionary<int, int> alkiotJaMaarat = new Dictionary<int, int>();
94
95        int lukuJotaEtsitaan = lista[0];
96        int montakoLoydetty = 1;
97        int i = 1;
98
99        // 2 2 3 4
100
101        while (i < lista.Count)
102        {
103            if (lista[i] != lukuJotaEtsitaan)
104            {
105                alkiotJaMaarat.Add(lukuJotaEtsitaan, montakoLoydetty);
106                lukuJotaEtsitaan = lista[i];
107                montakoLoydetty = 1;
108            }
109            else // peräkkäin sama luku
110            {
111                montakoLoydetty++;
112            }
113            i++;
114        }
115
116        alkiotJaMaarat.Add(lukuJotaEtsitaan, montakoLoydetty);
117
118        // voitaisiiin tehdä uusi lista, johon silmukassa lisätään
119        // avaimet alkiotJaMaarat-dictionarysta
120        // tässä vähän lyhyemmin koodirivien säästämiseksi :-)
121
122        int[] esiintymiskerrat = alkiotJaMaarat.OrderBy(x => x.Value).Select(x => x.Key).ToArray();
123        return esiintymiskerrat;
124    }
125
126    /// <summary>
127    /// Lisätään alkiot ja niiden esiintymismäärät key-value-pareina
128    /// Dictionary-tietorakenteeseen. Lopuksi järjestetään tietorakenne
129    /// esiintymismäärien perusteella, ja valitaan pelkät avaimet.
130    /// HUOM! Alkuperäistä aineistoa ei järjestetä.
131    /// </summary>
132    /// <param name="luvut"></param>
133    /// <returns></returns>
134    /// <example>
135    /// <pre name="test">
136    ///  int[] luvut = { 1, 2, 3, 34, 34, 2, 1, 34, 1, 1, 1 };
137    ///  int[] esiintymat = LukujenEsiintymiskerrat.LaskeEsiintymat2(luvut);
138    ///  String.Join(" ", esiintymat) === "3 2 34 1";
139    ///  String.Join(" ", LukujenEsiintymiskerrat.LaskeEsiintymat2(new int[]{})) === "";
140    ///  String.Join(" ", LukujenEsiintymiskerrat.LaskeEsiintymat2(new int[]{1})) === "1";
141    ///  String.Join(" ", LukujenEsiintymiskerrat.LaskeEsiintymat2(new int[]{1,2,2})) === "1 2";
142    ///  String.Join(" ", LukujenEsiintymiskerrat.LaskeEsiintymat2(new int[]{1,2,2,3})) === "1 3 2";
143    /// </pre>
144    /// </example>
145    public static int[] LaskeEsiintymat2(int[] luvut)
146    {
147        if (luvut.Length == 0) return new int[] { };
148
149        Dictionary<int, int> maarat = new Dictionary<int, int>();
150
151        int etsittava = luvut[0];
152        int loydettyKpl = 0;
153        int i = 0;
154        int j = 0;
155        // 2 2 3 4
156
157        while (i < luvut.Length)
158        {
159            etsittava = luvut[i];
160            loydettyKpl = 0;
161            j = 0;
162            if (maarat.ContainsKey(etsittava)) { i++; continue; }
163            maarat.Add(etsittava, loydettyKpl);
164            while (j < luvut.Length)
165            {
166                if (luvut[i] == luvut[j])
167                    maarat[etsittava]++;
168                j++;
169            }
170            i++;
171        }
172
173        // voitaisiiin tehdä uusi lista, johon silmukassa lisätään
174        // avaimet alkiotJaMaarat-dictionarysta
175        // tässä vähän lyhyemmin koodirivien säästämiseksi :-)
176
177        int[] esiintymiskerrat = maarat.OrderBy(x => x.Value).Select(x => x.Key).ToArray();
178        return esiintymiskerrat;
179    }
180
181    /// <summary>
182    /// Funktio järjestää sille annetun taulukon arvojen
183    /// esiintymiskertojen lukumäärän mukaan sekä
184    /// muodostaa uuden taulukon
185    /// siten, että kukin arvo esiintyy vain kerran.
186    /// Tämä funktio käyttää hyväkseen linq:ta ja
187    /// lambda-lausekkeita.
188    /// </summary>
189    /// <param name="taulukko">Käsiteltävä taulukko</param>
190    /// <returns>Esiintymiskertojen mukaan järjestetty taulukko</returns>
191    /// <example>
192    /// <pre name="test">
193    ///   int[] luvut = {1,2,3,34,34,2,1,34,1,1,1};
194    ///   int[] tulos = LukujenEsiintymiskerrat.LaskeEsiintymat3(luvut);
195    ///   String.Join(" ",tulos) === "3 2 34 1";
196    ///   String.Join(" ", LukujenEsiintymiskerrat.LaskeEsiintymat3(new int[]{})) === "";
197    ///   String.Join(" ", LukujenEsiintymiskerrat.LaskeEsiintymat3(new int[]{1})) === "1";
198    ///   String.Join(" ", LukujenEsiintymiskerrat.LaskeEsiintymat3(new int[]{1,2,2})) === "1 2";
199    /// </pre>
200    /// </example>
201    public static int[] LaskeEsiintymat3(int[] taulukko)
202    {
203        return
204            taulukko.ToList<int>().
205            GroupBy(i => i).
206            OrderBy(g => g.Count()).
207            Select(g => g.Key).
208            ToArray<int>();
209    }
210
211}
Note: See TracBrowser for help on using the repository browser.