Diskuze: Binárna sčítačka v céčku
Luboš Běhounek Satik:14.5.2013 21:01
Vice cisel tam nenacpes, protoze vytvaris pole na zasobniku. Vytvarej ho na
halde (pres new) a budet moci taky 10M 
A ted koukam, ze to nescita bity, ale bajty 
EDIT: tak ne, jen jsem to na prvni pohled nepochopil
Lukáš Hruda:14.5.2013 21:08
Větší pole můžeš udělat dynamicky. Statické pole může být pouze
tak velké jak velký je stack, což tuším je asi 1MB.
Myslím, že zadání nepočítá s tím, že budeš generovat rovnou součty,
ale že vygeneruješ náhodné číslo a teprve potom spočítáš součet
binárních cifer nějakým algoritmem. V tvém případě by to měření mělo
tudíž začínat už nad tím druhým velkým forem, což by dalo mnohem
větší čas.
Jinak co se týká kódu, tak nevypadá moc hezky, když je celý kód v jedné
funkci
Libor Šimo (libcosenior):14.5.2013 21:34
Trochu som to upravil a je tam 10 000 000 cifier. 
#include <stdio.h>
#include <time.h>
#define POCET 100000
typedef struct {
unsigned jeden : 5;
unsigned dva : 10;
unsigned tri : 15;
unsigned styri : 20;
unsigned pat : 31;
} CISLO;
void vypis(void);
double generovanie(CISLO cislo[], int pocet);
int main(void)
{
int i;
CISLO cislo[POCET];
double cas = 0.0;
srand(time(0));
vypis();
for (i = 0; i < 20; i++) {
cas += generovanie(cislo, POCET);
}
printf("\n\nScitanie cifier u %d cisiel trvalo %.0f ms.\n\n", POCET * 5 * 20, cas);
return 0;
}
/* vypis 100 cisiel */
void vypis(void)
{
int i, j, nah_cislo, spolu;
for (i = 0; i < 100 ; i++){
spolu = 0;
printf("%3d. ", i + 1);
for (j = 0; j < 32; j++)
{
nah_cislo = rand()%2;
printf("%d", nah_cislo);
spolu += nah_cislo;
}
printf(" = %d\n", spolu);
}
}
double generovanie(CISLO cislo[], int pocet)
{
int i, j, spolu, sucet = 0;
double cas;
clock_t t1, t2;
/* nacitanie suctov vygenerovanych cisiel do binarneho pola */
for (i = 0; i < pocet ; i++){
spolu = 0;
for (j = 0; j < 32; j++)
{
spolu += rand()%2;
}
cislo[i].jeden = spolu;
spolu = 0;
for (j = 0; j < 32; j++)
{
spolu += rand()%2;
}
cislo[i].dva = spolu;
spolu = 0;
for (j = 0; j < 32; j++)
{
spolu += rand()%2;
}
cislo[i].tri = spolu;
spolu = 0;
for (j = 0; j < 32; j++)
{
spolu += rand()%2;
}
cislo[i].styri = spolu;
spolu = 0;
for (j = 0; j < 32; j++)
{
spolu += rand()%2;
}
cislo[i].pat = spolu;
}
/* zmeranie casu spocitania cisiel z binarneho pola */
t1 = clock();
for (i = 0; i < pocet; i++)
sucet += cislo[i].jeden + cislo[i].dva + cislo[i].tri + cislo[i].styri
+ cislo[i].pat;
t2 = clock();
cas = (double) (t2 - t1) / CLOCKS_PER_SEC * 1000;
return cas;
}Je to lepšie? 10 000 000 cifier 62 ms.
Len neviem prísť na to, ako to sčítať bez cyklu.
Lukáš Hruda:14.5.2013 21:52
Já nevím, jestli existuje nějaký rychlejší algoritmus pro získání ciferného součtu binárního čísla, při googlení jsem nic nenašel, ale zkoušel jsem to v C++ jenom tak, že jsem pomocí bitového posunu a ANDu sčítal jednotlivé bity za sebou. Milion čísel to spočítá za cca 40ms. Ta funkce vypadá takhle:
inline char GetCount(unsigned int num)
{
char count = 0;
for(char i = 0; i < 32; i++, num>>=1)
count += num & (unsigned int)1;
return count;
}Mno, moc rychlé to není
Luboš Běhounek Satik:14.5.2013 22:02
Existuje, 1M cisel v C# mi trva cca 24ms s jednim vlaknem vlastni metodou a
asi 16ms vygooglenou lehce upravenou
Lukáš Hruda:14.5.2013 22:22
Já spíš nevěděl pod čím to googlit. Napadlo že bych mohl upravit ten
můj způsob tak, že bych vždy kontroloval jestli je poslední byte větší
než třeba 15 a pokud ano, tak to posunou rovnou o 4 bity. To by ale bylo
rychlejší jenom za určitých okolností, pokud by ty jedničky byly hustě u
sebe, bylo by to pomalejší. Každopádně, vyzkoušel bych to, ale teď na to
nemám čas, musím se učit na maturitu
David Hartinger:15.5.2013 15:34
Těší mě zájem o soutěž i v jiném jazyce, jestli si najdeš ještě
nějakého soupeře, vyhlásil bych jí i pro C++
Libor Šimo (libcosenior):15.5.2013 17:39
Pretože táto časť kódu:
((cislo >>= 1) & (unsigned int)1) == 1 ? count += 17 : count;vo funkcii short spocitat(unsigned int cislo) platí len niekedy.
Stačí aby sa zväčšil rozsah generovaných čísiel a nebude to pravda.
@sdraco, ja som si to chcel len vyskúšať, nie súťažiť.
Lukáš Hruda:17.5.2013 18:40
Já to udělal takhle:
#include <iostream>
#include <windows.h>
using namespace std;
inline char GetCount(unsigned short num)
{
char count = 0;
for(char i = 0; i < 16; i++, num>>=1)
count += num & 1;
return count;
}
inline void FillNumberCounts(char* arr)
{
for(unsigned short i = 0; i < 65535; i++)
arr[i + 1] = GetCount(i + 1);
}
void PrintBinary(unsigned int num)
{
for(int i = 0; i < 32; i++)
cout<<((num>>(31-i))&1);
}
inline void PrintExamples(int count)
{
char numberCounts[65536];
FillNumberCounts(numberCounts);
for(int i = 0; i < count; i++)
{
unsigned int rnd = rand()*rand()*rand();
unsigned short* bytes = (unsigned short*)&rnd;
PrintBinary(rnd);
cout<<" "<<(int)numberCounts[bytes[0]] + numberCounts[bytes[1]]<<endl;
}
}
int main()
{
LONGLONG frequency;
LONGLONG counter;
LONGLONG begin;
QueryPerformanceFrequency((LARGE_INTEGER*)&frequency);
srand(time(0));
const int size = 10000000;
unsigned int* array = new unsigned int[size];
char* countArray = new char[size];
char numberCounts[65536] = {0};
PrintExamples(100);
for(int i = 0; i < size; i++)
array[i] = rand()*rand()*rand();
QueryPerformanceCounter((LARGE_INTEGER*)&begin); //zacatek mereni
FillNumberCounts(numberCounts);
for(int i = 0; i < size; i++)
{
unsigned short* bytes = (unsigned short*)&array[i];
countArray[i] = numberCounts[bytes[0]] + numberCounts[bytes[1]];
//PrintBinary(array[i]); cout<<" "<<dec<<(int)countArray[i]<<endl;
}
QueryPerformanceCounter((LARGE_INTEGER*)&counter); //konec mereni
cout<<endl<<"Binarni ciferny soucet "<<size<<" cisel trval "<<(counter - begin) / (frequency / 1000)<<" ms"<<endl;
delete [] array;
delete [] countArray;
getchar();
}Není to nejpomalejší, na mém notebooku to udělá 10 000 000 čísel za
40 - 50 ms. Ale třeba Luboš Běhounek Satik to v C# má prý za 10 ms. Já na to ani
nenašel žádný algoritmus, tak vycházím pořád z toho základního.
Rychlejší už to asi neudělám, a to je to psané v C++
Som zvedavý na zajtra, ako to zvládnu v c#. Dúfam, že nejaký kód bude
zverejnený. 
Zobrazeno 39 zpráv z 39.