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

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