Diskuze: Binárna sčítačka v céčku
V předchozím kvízu, Online test znalostí C++, jsme si ověřili nabyté zkušenosti z kurzu.
Tvůrce
Zobrazeno 39 zpráv z 39.
//= Settings::TRACKING_CODE_B ?> //= Settings::TRACKING_CODE ?>
V předchozím kvízu, Online test znalostí C++, jsme si ověřili nabyté zkušenosti z kurzu.
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
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
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.
Stale ale meris cas neceho jineho, nez bys mel, takze ti vychazi mnohem mensi cas, nez by mel.
Melo by to vypadat takhle:
Pri generovani cisel pocty bitu uz castecne scitas, takze pak mereny vypocet je rychlejsi, protoze uz to mas predvypocitane.
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í
Existuje, 1M cisel v C# mi trva cca 24ms s jednim vlaknem vlastni metodou a asi 16ms vygooglenou lehce upravenou
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
Tak toto je posledné, čo som zatiaľ zvládol díky Luckinovi.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define POCET 10000000
#define MAX 100000
#define MIN 15000
short spocitat(unsigned int cislo);
void vypis(unsigned int cislo);
int main(void)
{
unsigned int i, pom, *cislo;
short vysledok = 0;
double cas;
clock_t t1, t2;
srand(time(0));
cislo = (int *) malloc(POCET * sizeof(int));
for (i = 0; i < 100; i++) {
pom = rand()%MAX - MIN;
printf("%3d. %6d: ", i + 1, pom);
vypis(pom);
printf(" = %d\n", spocitat(pom));
}
for (i = 0; i < POCET; i++) {
cislo[i] = rand()%MAX - MIN;
}
t1 = clock();
for (i = 0; i < POCET; i++)
vysledok += spocitat(cislo[i]);
t2 = clock();
cas = (double) (t2 - t1);
printf("\n\nScitanie cifier u 10.000.000 cisiel trvalo %.0f ms.\n\n", cas);
return 0;
}
short spocitat(unsigned int cislo)
{
short i, count = 0;
for(i = 0; i < 15; i++, cislo >>= 1)
count += cislo & (unsigned int)1;
((cislo >>= 1) & (unsigned int)1) == 1 ? count += 17 : count;
return count;
}
void vypis(unsigned int cislo)
{
short i;
for(i = 0; i < 32; i++, cislo >>= 1)
printf("%d", cislo & (unsigned int)1);
}
Vo funkcii spočítať som napísal blbosť. Ak sa dá, zmažte môj príspevok.
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++
Kód uživatele Libor Šimo (libcosenior) je v C. Já se asi nezúčastním, jelikož teď nemám moc času.
Libco: proč bych to měl mazat?
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ť.
Klidně sem hoď opravu, mazat se to nemusí.
Ona je to vlastne tvoja funkcia, len som si myslel, že ju vylepším. :[
short spocitat(unsigned int cislo)
{
short i, sucet = 0;
for(i = 0; i < 32; i++, cislo >>= 1)
sucet += cislo & (unsigned int)1;
return sucet;
}
Vyskúšal som aj rekurziu, ale je to pomalšie. Už ma nič nenapadá.
int cyklus_rek(int cislo, int n)
{
if (cislo == 0) return spolu;
spolu += cislo % 2;
cislo >>= 1;
cyklus_rek(cislo, n + 1);
return spolu;
}
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++
Asi tomu úplne nerozumiem, ale kde ti to spočítava hodnoty jednotlivých
bitov všetkých náhodných čísiel?
Malo by to byť v nasledujúcej časti, ale nevidím to tam.
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
Môžeš mi to vysvetliť, poprípade napísať riadok, ktorý vypíše celkový súčet?
Ten vykomentovaný řádek to vypíše do konzole pro každé číslo. Jinak ten algoritmus je trochu složitější. Funkce FillNumberCounts převezme jako parametr pole o velikosti 65536 (max. hodnota 2 bytů + 1) prvků a naplní ho tak, že na každém indexu je počet jedniček v tom daném indexu, tzn. třeba 12. prvek obsahuje počet jedniček v čísle 12, takže 2. Tohle zabere dost málo času, u mě asi 2ms. Pak se v tom hlavním cyklu pouze každé číslo rozdělí na horní a spodní dva byty, vezme se hodnota každé z těchto dvou částní a použije se jako index do toho pole, které obsahuje počty jedniček každé hodnoty. Tyto dvě hodnoty se pak pouze sečtou a je to.
Stále tomu nerozumiem. Ktoré premenná by mohla vypísať celkový súčet?
Součty jednotlivých bitů jsou v poli countArray, samotná čísla jsou v poli array.
Toto je zadanie:
"Druhá část programu vygeneruje 10.000.000 takových čísel a spočítá
jejich ciferné součty."
Asi som to nepochopil správne.
Myslím si, že treba dosiahnuť celkový súčet ciferných súčtov.
Podľa teba stačí, ak budú v poli uložené jednotlivé ciferné súčty.
To sú ale veľmi rozdielne výstupy.
Tak som trošku upravil tvoj program.
Pridal som premennú unsigned int vysledok a dal som ju sem:
FillNumberCounts(numberCounts);
for(int i = 0; i < size; i++)
{
unsigned short* bytes = (unsigned short*)&array[i];
//countArray[i] = numberCounts[bytes[0]] + numberCounts[bytes[1]];
vysledok += numberCounts[bytes[0]] + numberCounts[bytes[1]];
//PrintBinary(array[i]); cout<<" "<<dec<<(int)countArray[i]<<endl;
}
celkový čas sa znížil na 2 ms.
Nemusí být ani nikde uložené, stačí je spočítat.
Chces rici, ze ten vysledny soucet pro kazde cislo se nemusi vubec nikam ukladat, tedy ze tam staci mit pouze vyraz, ktery ten soucet vrati i kdyz ho nicemu nepriradi?
Ja som to pochopil tak, že treba sčítať súčty (teda binárne súčty)
všetkých vygenerovaných čísiel a to konečné číslo niekam uložiť. Len
nie je potrebné ho vypisovať.
Aj keď si myslím, že výpis konečného výsledku, ak sa urobí mimo merania
času, nemá vplyv na výsledok súťaže.
Má, protože když ten výsledek nikde nepoužiješ, tak kompilátor ten výpočet úplně přeskočí, pak se právě dostaneš na čas jako je 6 ms. Když si ten výsledek pak někde vypíšeš nebo tu proměnnou kdekoliv použiješ, i když mimo měřený úsek, tak uvidíš, že ten čas bude mnohem delší.
Som zvedavý na zajtra, ako to zvládnu v c#. Dúfam, že nejaký kód bude zverejnený.
Mě by spíše než celý kód zajímal algoritmus, protože já nikde nic nenašel, vycházel jsem pořád z toho základního, kde jenom posouváš bity a anduješ.
Možno sa dá použiť blok assembleru na ten algoritmus a ten určite bude veľmi rýchly.
Nevím jestli C# umí inline assembler.
Našiel som niečo: http://www.atrevido.net/…rmaLink.aspx?…
a toto: http://www.codeproject.com/…ric-Pointers
ale nie je to klasický asm. Toto je určite podstatne zložitejšie.
Luckin, ty by si vedel využiť v programe blok asm (JAS)?
U C/C++ záleží na kompilátoru, tuším, že pro Code::blocks funguje
tohle:
http://www.codeproject.com/…embly-in-C-C
Už mám pár vecí vyskúšaných. Ale dík.
Ide o to, že som sa rozhodol upraviť program tak, že tá dôležitá časť kódu bude riešená priamo, na nižšej úrovni.
a tým sa to maximálne skráti!
Pokud to napíšeš dobře tak zkrátí, ale nepočítej s tím že nějak zásadně, a hlavně, že se ti to tak snadno povede. C je dost nízkoúrovňový jazk a kompilátor optimalizuje celkem dobře.
Zobrazeno 39 zpráv z 39.