Diskuze: Hledání opakujícího čísla v poli a jejich počet.
V předchozím kvízu, Test znalostí C# .NET online, jsme si ověřili nabyté zkušenosti z kurzu.
Proc tak slozite?
Prvni cast dela random a ulozi hodnotu cisla to do pole. OK.
Druha cast muze vytvaret pole. `if exist(pole[hodnota]) pole[hodnota]++
nebo pole[hodnota]=1 `. A pak potrebujes dalsi cyklus, ktery vypisuje vsechny
hodnoty, ktere nejsou 1.
Ty to resis nejak strasne slozitou cestou, ze pokazde prohledavas cele pole
(takovy jako kdyz bubble sort). Kdybys mel milion cisel, tak to pocitas jeste
druhy den 
+20 Zkušeností
+2,50 Kč
Matúš Olejník:11.3.2022 11:29
Presne ako spomenul Peter, číslo ktoré padne môžeš rovno použiť ako index do poľa kde zvýšiš hodnotu o 1. Takto sa robí aj histogram pre výskyt písmen atď.
Module VBModule
'13) Je dána posloupnost kladných celých čísel (ne lineární, tedy čísla budou nějak na přeskáčku).
'Zjistěte, zda se v dané posloupnosti nějaké číslo opakuje.
'13 b) zjistěte, která čísla se opakují.
'13c) přidejte ještě informaci, kolikrát se opakují.
Sub Main()
Dim randomIntervalFrom, randomIntervalTo, i, randomNumber, randomNumbersCount As Integer
Dim histogram() As Integer
Dim output As String
Dim someNumberIsRepeated As Boolean
output = ""
someNumberIsRepeated = False
'toto keby si chcel niekedy dynamicke velkosti
randomNumbersCount = 20
randomIntervalFrom = 1
randomIntervalTo = 20
ReDim histogram(randomIntervalTo + 1)
Randomize()
For i = 0 To randomNumbersCount - 1
randomNumber = Int((randomIntervalTo - randomIntervalFrom + 1) * Rnd + randomIntervalFrom)
histogram(randomNumber) = histogram(randomNumber) + 1
If histogram(randomNumber) > 1 Then
someNumberIsRepeated = True
End If
Console.Write(Str(randomNumber) + " ")
output = output + Str(randomNumber) + ", "
Next
Console.WriteLine
If someNumberIsRepeated Then
Console.Write("Existuje cislo/cisla ktore sa opakuje/opakuju")
Console.WriteLine
For i = randomIntervalFrom To randomIntervalTo + 1
If histogram(i) > 1 Then
Console.Write("Cislo " + Str(i) + " sa opakuje " + Str(histogram(i)) + " krat ")
Console.WriteLine
End If
Next
Else
Console.Write("Ziadne cislo sa neopakuje")
End If
End Sub
End ModuleDo MsgBoxu už si to prerobíš 
Spravil som pokus. Vytvoril som 4 verzie programu. Pre zoznam čísiel
používam List. Krátky popis:
Verzia 1:
zoradí List a potom stačí keď prejde celé pole iba jeden krát
Verzia 2:
prechádza List v dvoch cykloch, v prípade že nájde zhodu, zaznamená to a
položku z Listu odstráni, čím redukuje počet iterácii cyklu
Verzia 3:
Od používateľa Jakub Raida
Nevýhodou je výpis - všetky duplicitné čísla vypisuje tzn. napr. ak je
číslo 9 v poli 5x tak ho 5x vypíše
Verzia 4:
Od používateľa zelvicek
toto naštudované nemám
Tu je vysledok testu: Trvanie je v milisekundách
Počet čísiel: 10
Verzia 1 trvanie: 1,7476
Verzia 2 trvanie: 1,0081
Verzia 3 trvanie: 2,9303
Verzia 4 trvanie: 71,8895
Počet čísiel: 100
Verzia 1 trvanie: 4,7877
Verzia 2 trvanie: 2,9706
Verzia 3 trvanie: 25,2603
Verzia 4 trvanie: 85,0549
Počet čísiel: 1 000
Verzia 1 trvanie: 3,301
Verzia 2 trvanie: 10,0022
Verzia 3 trvanie: 240,0204
Verzia 4 trvanie: 133,0393
Počet čísiel: 10 000
Verzia 1 trvanie: 5,0046
Verzia 2 trvanie: 15,0028
Verzia 3 trvanie: 4649,8514
Verzia 4 trvanie: 76,2385
Počet čísiel: 100 000
Verzia 1 trvanie: 15,8993
Verzia 2 trvanie: 1187,2465
Verzia 3 trvanie: 451568,8017
Verzia 4 trvanie: 86,0043
using System;
using System.Collections.Generic;
using System.Linq;
namespace OpakovaniaCislaVpoli
{
internal class Program
{
List<int> list = new List<int>();
string opakujuceCisla = "";
public List<NajiteCislo> NajitaCisla { get; private set; }
public int Pocitadlo { get; private set; }
public int PocetCisel { get; private set; }
public string Vypis { get; private set; }
public Random Nahoda { get; private set; }
int min = 1; // minimálna hodnota čísiel
int max = 20; // (max - 1) - maximálna hodnota čísiel
int pocet = 100000; // počet
static void Main()
{
Program program = new Program();
program.NacitajHodnoty();
program.HladajDuplicity1();
program.HladajDuplicity3();
program.HladajDuplicity4();
program.HladajDuplicity2();
Console.ReadKey();
}
void NacitajHodnoty() // Naplní List náhodnými číslami
{
Random rand = new Random();
for (int i = 0; i < pocet; i++)
list.Add(rand.Next(min, max));
}
private void HladajDuplicity1() // zoradí List a potom postupne hľadá počet opakovaní
{
opakujuceCisla = "";
int pocetOpakovani = 1;
list.Sort();
for (int i = 0; i < list.Count - 1; i++)
if (list[i] == list[i + 1])
pocetOpakovani++;
else if (pocetOpakovani > 1)
{
opakujuceCisla += $"Cislo {list[i]} sa nachádza v poli {pocetOpakovani }x\n";
pocetOpakovani = 1;
}
else
pocetOpakovani = 1;
if (pocetOpakovani > 1)
opakujuceCisla += $"Cislo {list[list.Count - 1]} sa nachádza v poli {pocetOpakovani }x\n";
// Výpis hodnôt
Console.WriteLine($"Verzia1: \n{opakujuceCisla}");
}
private void HladajDuplicity2()
{
opakujuceCisla = "";
int pocetOpakovani = 1;
for (int i = 0; i < list.Count-1; i++)
{
for (int j = i+1; j < list.Count; j++)
if (list[i] == list[j])
{
pocetOpakovani++;
list.RemoveAt(j);
j--;
}
if (pocetOpakovani > 1)
{
opakujuceCisla += $"Cislo {list[i]} sa nachádza v poli {pocetOpakovani }x\n";
pocetOpakovani = 1;
}
}
//Výpis
Console.WriteLine($"Verzia2: \n{opakujuceCisla}");
}
private void HladajDuplicity3() // Jakub Raida
{
NajitaCisla = new List<NajiteCislo>();
// Procházíme řadu čísel
foreach (int prvniVyskyt in list)
{
Pocitadlo = 0;
foreach (int vsechnyVyskyty in list)
if (prvniVyskyt == vsechnyVyskyty)
Pocitadlo++;
NajitaCisla.Add(new NajiteCislo(prvniVyskyt, Pocitadlo));
}
// Vyprázdníme si výpis
Vypis = String.Empty;
// Vytvoříme si výpis
foreach (NajiteCislo polozka in NajitaCisla)
Vypis += String.Format("Číslo: {0} ---- Počet výskytů: {1}\n", polozka.NumerickaHodnota, polozka.Vyskytovost);
//Výpis
Console.WriteLine($"Verzia3: \n{Vypis}");
}
void HladajDuplicity4() // zelvicek
{
Random rand = new Random();
(int Value, int Count)[] res = Enumerable.Range(0, pocet).Select(x => rand.Next(min, max)).ToArray()
.GroupBy(x => x).Select(x => (Value: x.Key, Count: x.Count())).Where(x => x.Count > 1).OrderBy(x => x.Value).ToArray();
for (int i = 0; i < res.Length; i++)
Console.WriteLine($"Číslo {res[i].Value} sa nachádza v poli {res[i].Count}x");
}
}
public class NajiteCislo
{
public int NumerickaHodnota { get; private set; }
public int Vyskytovost { get; private set; }
public NajiteCislo(int numerickaHodnota, int vyskyty)
{
NumerickaHodnota = numerickaHodnota;
Vyskytovost = vyskyty;
}
}
}
DarkCoder:19.3.2022 2:03
Samozřejmě že se to porovnávat dá, zadání úlohy je pro všechny testy stále stejné: Vygeneruj 100000 náhodných čísel v rozsahu 1-20 a vypiš na obrazovku hlášku o tom, kolikrát se opakované číslo opakuje. Jak už se s tím který způsob popere, je jedno.
Jako výchozí hodnotu budu brát čas nejrychlejší verze, tedy té první kde se využívá List, a to: 15,8993 ms.
Verze s polem, jehož hodnoty na indexech představují počty opakování čísla odpovídající indexu a výpisem pole o velikosti rozsahu generovaných náhodných čísel (1-20) s lineární složitostí na základě jedné relace, má čas: 36,4313 ms.
Nevěřím, že by tato verze s polem byla více než 2x pomalejší, než první verze s Listem, ve které se provádí tolik úkonů.
A tak uděláme test přímo v programu nad jednotlivými verzemi a uvidíme,
jak to skutečně je.
Pro zjištění času použijeme třídu Stopwatch.
using System.Diagnostics;
// ...
Stopwatch sw = new Stopwatch();
sw.Start();
// mereny usek programu
sw.Stop();
Console.WriteLine("cas = {0}", sw.Elapsed);Tedy verze s polem doplněná o kód potřebný k měření času úseku kódu:
using System;
using System.Diagnostics;
public class Program {
public static void Main() {
int min = 1;
int max = 20;
int throws = 100000;
int[] vals = new int[max + 1];
Stopwatch sw1 = new Stopwatch();
sw1.Start();
// generovani histogramu
Random rand = new Random();
for (int i = 0; i < throws; i++) vals[rand.Next(min, max + 1)]++;
sw1.Stop();
Stopwatch sw2 = new Stopwatch();
sw2.Start();
// vypis opakujicich se cisel
for (int i = min; i <= max; i++){
if(vals[i] > 1) Console.WriteLine("Cislo {0} se opakuje {1}x", i, vals[i]);
}
sw2.Stop();
Console.WriteLine("sw1 = {0}", sw1.Elapsed);
Console.WriteLine("sw2 = {0}", sw2.Elapsed);
}
}U ostatních verzí tedy udělat totéž (nezapomenout na using System.Diagnostics):
using System.Diagnostics;
// ...
static void Main() {
Program program = new Program();
Stopwatch sw1 = new Stopwatch();
sw1.Start();
program.NacitajHodnoty();
sw1.Stop();
Stopwatch sw2 = new Stopwatch();
sw2.Start();
program.HladajDuplicity1();
// program.HladajDuplicity3();
// program.HladajDuplicity4();
// program.HladajDuplicity2();
sw2.Stop();
Console.WriteLine("sw1 = {0}", sw1.Elapsed);
Console.WriteLine("sw2 = {0}", sw2.Elapsed);
Console.ReadKey();
}Zajímají mě výpisy naměřených hodnot sw1 a sw2 všech verzí.
Nad každou verzí spustit program alespoň 5x.
Ještě jeden dodatek k funkci generující náhodné číslo.
int min = 1;
int max = 20;
// ...
Random rand = new Random();
for (int i = 0; i < pocet; i++) list.Add(rand.Next(min, max));rand.Next(min, max) způsobí vygenerování náhodného čísla v rozsahu 1-19, nikoli v rozsahu 1-20.
Je tedy třeba upravit zdrojový kód na rand.Next(min, max + 1)
Peter Mlich:19.3.2022 23:20
ups, ja jsem ti dal spatny link, na pokusnou verzi. tam ted testuji jeden
algoritmus, tak to mam omezene na 15 prvku
https://mlich.zam.slu.cz/…g4-pokus.htm
- dej si test 2 (nebo 3), klikni 100.000 prvku, klikni na "All" u algoritmu a klikni "start"
- vsude, kde se neobjevi t0, tak byl algoritmus stopnut pro cas>500ms (to
sem tam dal zamerne stopku, kdyby nekdo pustil algoritmus, co by to pocital
hodinu )
- u mne trvalo 45ms nez se provedl tim-sort pole o velikosti 100.000 timsortem, a jednalo se o 3.397.537 cyklu, coz je 34x vic nez tvych 100.000 cyklu. Takze, tvuj kod by mel byt kolem 2-5-10 ms.
- a taky tam mas counting sort, ktery to seradil za polovicni cas, pri pouziti 300.000 cyklu (vytvari nejdriv pole pocet opakovani, to resis ty, + pak z nej generuje serazene pole - tento algoritmus se pouziva pro serazeni pole s integer hodnotami); cili, mel bys byt rychlejsi nez counting-sort Pigeonhole (ale mam pomaly pocitac, tak, treb na tvem to bude 2ms a ne 20ms)
Pokud tam tedy mas 1000 a vic, tak je neco zasadne spatne. A take je jasne, u zelvicka, ze dela nejspis nejake operace navic, kdyz nedosahl tech 15ms jako ten prvni kod.
// zajimalo by mne, zda je nejaky casovy rozdil mezi
for (int i = 0; i < pocet; i++) nums[i] = rand.Next(min, max);
for (int i = 0; i < pocet;) nums[i++] = rand.Next(min, max);
int i = 0; for (; i < pocet;) nums[i++] = rand.Next(min, max);
int i = 0; while (i < pocet) nums[i++] = rand.Next(min, max);
// a jestli by byl rozdil v tom, prepsat ten random do pomocne funkce
int i = 0; while (i < pocet) nums[i++] = random(); // return rand.Next(min, max);Totiz, jako, kdyz se to prepise do pomocne funkce, procesor by na to mohl
nahodit nejake optimalizace a vygenerovat si treba nekolik cisel dopredu.
A ten random ti trva 500 ms pro 1.000 nebo 10.000 cisel? Za stejny cas mam pole
vygenerovane pres random a serazene pro n = 1.000.000 Viz, ten muj javascriptovy program.
Ten cas by se ti mel pohybovat tak do 30 ms, myslim.
Na druhou stranu, jestli pouzivas c#, tak to mozne je. Minule jsem delal nejake
pokusy v php, ktere je alternativou c# a byl dost problem pracovat s pixel mapou
obrazku. Co jsem mel v js blik, tak to tam trvalo i 5s.
Potom som ešte spravil jeden pokus, prerobil som výpočet priemeru takto:
Console.WriteLine("sw = {0}", sw.Elapsed.TotalSeconds / rep);pretože mi to v tom tvojom tvare nefungovalo cez Visual Studio. A spustil som v NTB a aj v online compileri a:
//NTB:
sw = 0,020148322
//Online:
sw = 0.000279046Takže problém asi bude v NTB, ak aj toto vylúčiš, tak bude problém asi
medzi stoličkou a NTB
Cili, v zasade to vygeneruje stejny asm kod, jen jsou nektere instrukce v jinem poradi. Takze by to melo asi dosahovat stejne casy. Leda ma procesor nejake optimalizace pro konkretni posloupnosti instrukci.
Spis mne jako napadlo, ze kdyz se deklaruje promena predem, tak by cyklus
mohl bezet rychleji.
Kdyz se udela i++ mimo deklaraci cyklu, tak se treba ztrati nejaky radek.
Jeste by teoreticky slo zkusit dat misto i++, ++i. To by se melo chovat
rychleji. Ale, to ma asi spis vyznam uvnitr cyklu. V zahlavi to asi
prekonvertuje stejne.
Samozrejme, kazda z tech uprav by mela byt v podstate bezvyznamna, max 0.01%
nebo tak neco Spis jsem byl
zvedavy. Ja treba stridam obcas pouziti while a for, nektere kody jsou
prehlednejsi s while.
DarkCoder:30.3.2022 10:26
Ano, pokud nemá procesor nějaké své vnitřní optimalizace, tak budou dosažené časy stejné. Samozřejmě to také může být pouze hrubý nástřel a nakonec si nějakou tu optimalizaci najde. U některých zápisů ale skutečně může dojít k navýšení výkonu, respektive některý zápis bude rychlejší. Např. indexace a ukazatelová aritmetika.
Příklad ukazuje, jak 4 způsoby uložit hodnotu 10 do druhého prvku pole.
#include <stdio.h>
int main(void) {
int nums[10], *p = nums;
nums[1] = 10;
*(nums + 1) = 10;
p[1] = 10;
*(p + 1) = 10;
return 0;
}; 4 : int nums[10], *p = nums;
lea rax, QWORD PTR nums$[rbp]
mov QWORD PTR p$[rbp], rax
; 5 :
; 6 : nums[1] = 10;
mov eax, 4
imul rax, rax, 1
mov DWORD PTR nums$[rbp+rax], 10
; 7 : *(nums + 1) = 10;
mov DWORD PTR nums$[rbp+4], 10
; 8 : p[1] = 10;
mov eax, 4
imul rax, rax, 1
mov rcx, QWORD PTR p$[rbp]
mov DWORD PTR [rcx+rax], 10
; 9 : *(p + 1) = 10;
mov rax, QWORD PTR p$[rbp]
mov DWORD PTR [rax+4], 10Výsledky jsou jistě zajímavé.
Nicméně je to jiný způsob zápisu než to, o čem byla řeč. Není na škodu a chybou rozepisovat kód do více řádků, nejen z důvodu čitelnosti, ale také z důvodu vedlejších efektů, které při zkrácených zápisech mohou nastat.
Ano, určitý rozdíl rychlosti v deklaraci proměnné je. Je rozdíl např. deklarovat pole staticky nebo až za běhu.
V programech se často používají cykly, ty mají své iterační proměnné, které se lokálně deklarují. Z hlediska rychlosti se nabízí možnost deklarovat proměnnou vně cyklu a používat ji pro více cyklů a vyhnout se tak nové deklaraci a zkrátit tak čas. To už jsou extrémní případy které mohou mít dopad na přehlednost programu, bezpečnost a rychlost psát kód. Ten drobný nárust rychlosti v tomto případě za to nestojí.
Co se týká inkrementace v prefixové podobě ++i proti postfixové podobě i++, pro vestavěné typy zde není žádný rozdíl. Drobný rozdíl je u tzv. compound typů, tedy typů co vytváří programátor, struktury, objekty, unie, tam je prefixová podoba zápisu nepatrně rychlejší.
Každý cyklus se pro něco hodí lépe pro něco méně. Důvodem je přehlednost a v určitých případech funkčnost, to zejména u rozdílu mezi do-while a while cykly. Ve skutečnosti jsou to jen varianty pro lidi, neboť překladače každý while a do-while cyklus zpracovávají do podoby for cyklu. Proto když jsem posílal asm výstup while cykly, nebyl tam žádný rozdíl. Já osobně preferuji for cyklus, neboť mohu dost zápisů napsat do jednoho řádku díky tomu, že inkrementační část je na stejném řádku na konci v těle cyklu.
Optimalizace je složitá, jsou místa kde to má smysl, třeba tvé
porovnání všech možných algoritmů, tam se dá ušetřit spoustu času. A
pak tyto drobné zápisy, které se hodí do extrémních situací a zabývat se
jimi může zabrat příliš mnoho času. Ale je to bezesporu zajímavé.
DarkCoder:30.3.2022 14:19
Možností je mnoho. Je dobré udržovat věci pospolu, které mezi sebou souvisí.
for (; i<i_end; i++, k++) arr2[k] = arr1[i];for (; i<i_end; ) arr2[k] = arr1[i], i++, k++;for (; i<i_end; ) {
arr2[k] = arr1[i];
i++;
k++;
}for (; i<i_end; ) {
arr2[k] = arr1[i];
i++, k++;
}Nechť si každý vybere co mu vyhovuje..
Zobrazeno 50 zpráv z 50.