Mitä mieltä olette tämän tehokkuudesta? Ja miten sen saisi vähemmän alustariippuvammaksi? Tämä ei kai välttämättä toimi kaikilla koneilla? Käyttöä varten pitää olla satunnaistiedosto esim. jpeg kuvasta suurimmalla iso-arvolla otettuna. Eikös 0,1 megan ja 100 megan taulukosta luku ole yhtä nopeaa? Mitä mieltä olette siitä ideasta ja satunnaislukujen laadusta?
Vaihtoehtoisia toteutuksia on poiskommentoitu.
Pienempi_kuin ja suurempi_kuin pitää korvata editorin korvaustoiminnolla.
Ennen oliota, xor-yhdistämis-funktio:
long unsigned int xoryh(long unsigned int a, long unsigned int b, long unsigned int c)
{
long unsigned int rsa;
bitsetpienempi_kuin32lusuurempi_kuin ra( a );
bitsetpienempi_kuin32lusuurempi_kuin omr( b );
bitsetpienempi_kuin32lusuurempi_kuin bk2( c );
ra=(ra^=omr)^=bk2;
rsa=ra.to_ulong( );
return rsa;
}
class orand
{
public:
long unsigned int alusta(fstream &sat);
long unsigned int an();
void nol(long unsigned int s);
private:
long unsigned int k_, rsat_, k2_;
vectorpienempi_kuinunsigned intsuurempi_kuin svec_;
bitsetpienempi_kuin32lusuurempi_kuin omr_;
bitsetpienempi_kuin32lusuurempi_kuin ra_;
bitsetpienempi_kuin32lusuurempi_kuin bk2_;
union
{
long unsigned int ink;
unsigned char chk[4];
} unk_;
long unsigned int kok_, vkok_;
};
long unsigned int orand::alusta(fstream &sat)
{
sat.seekg(0, ios::end);
kok_=sat.tellg();
for(k_=0 ; k_pienempi_kuinkok_ ; k_ )
{
sat.seekg(k_);
sat suurempi_kuinsuurempi_kuin noskipws suurempi_kuinsuurempi_kuin unk_.chk[k_%4];
if(k_%4==3) svec_.push_back(unk_.ink);
}
k_=0;
vkok_=svec_.size();
k2_=(vkok_/4)*3;
return vkok_;
}
long unsigned int orand::an()
{
k_ ;
if(k_==vkok_) { k_=0; k2_--; if(k2_pienempi_kuinvkok_/4) k2_=(vkok_/4)*3; }
rsat_=rand( );
/* bitsetpienempi_kuin32lusuurempi_kuin ra_( rsat_ );
bitsetpienempi_kuin32lusuurempi_kuin omr_( svec_.at(k_) );
bitsetpienempi_kuin32lusuurempi_kuin bk2_( svec_.at(k2_) );
// omr_=(omr_^=bk2_);
ra_=(ra_^=omr_)^=bk2_;
rsat_=ra_.to_ulong( );
return rsat_;*/
return xoryh(rsat_, svec_.at(k_), svec_.at(k2_) );
}
void orand::nol(long unsigned int s)
{
k_=s%vkok_;
}
Oma rand-olio
12
397
Vastaukset
- Harrastaja591
includet jäi, ne on kai: iostream, fstream, vector, cstdlib ja bitset
ja:
using namespace std; - 15
"Mitä mieltä olette tämän tehokkuudesta?"
Jos haluat tehdä hirmunopean, hankkiudu eroon kerto-, jako- ja modulolaskuista.
Kääntäjä osaa luultavasti optimoida nuo bitset-tyyppimuunnokset ja funktiokutsun (xoryh), jotka ilman optimointeja näyttävät turhalta kuormalta. Mutta silti: miksi et vaan xorraisi suoraan:
return rsat_ ^ svec_.at(k_) ^ svec_.at(k2_);
"Eikös 0,1 megan ja 100 megan taulukosta luku ole yhtä nopeaa?"
Ei. Esimerkki: lue kaikki taulukon tavut kertaalleen satunnaisessa järjestyksessä. 100 megan taulukosta tavut tulevat keskimäärin huomattavasti hitaammin kuin 0,1 megan taulukosta. Arvaatko syyn?- Harrastaja591
"Ei. Esimerkki: lue kaikki taulukon tavut kertaalleen satunnaisessa järjestyksessä. 100 megan taulukosta tavut tulevat keskimäärin huomattavasti hitaammin kuin 0,1 megan taulukosta. Arvaatko syyn?"
Erityyppistä muistia fyysisesti, useimmissa tietokoneissa? Arvaus saattaa olla väärä. Ja joku on saattanut koota erilaisen tietokoneen. Entä jos sama tai eri ohjelma on jo varannut 2 gigaa muistia 4 gigasta? Ja onko joku koko kynnys minkä jälkeen alkion haku ei enää hidastu? Näiden luulisi riippuvan myös käyttöjärjestelmästä ja linux-jakelusta ja siitä onko prosessori-ytimiä 1 vai useampi.
Tarkoitin muuten sekä c-taulukkoa [koko] että vectoria. Onko niillä eroa tässä suhteessa?
Missä linux-jakelussa omat ohjelmat toimivat nopeimmin?
Vaikka olisi monta ydintä, voiko omaa ohjelmaa hidastaa se jos samaan aikaan katsoo firefoxilla videoita tai saman ohjelman toinen instanssi/ olio (vai miten se pitää sanoa?) on käynnissä eri datalla? Harrastaja591 kirjoitti:
"Ei. Esimerkki: lue kaikki taulukon tavut kertaalleen satunnaisessa järjestyksessä. 100 megan taulukosta tavut tulevat keskimäärin huomattavasti hitaammin kuin 0,1 megan taulukosta. Arvaatko syyn?"
Erityyppistä muistia fyysisesti, useimmissa tietokoneissa? Arvaus saattaa olla väärä. Ja joku on saattanut koota erilaisen tietokoneen. Entä jos sama tai eri ohjelma on jo varannut 2 gigaa muistia 4 gigasta? Ja onko joku koko kynnys minkä jälkeen alkion haku ei enää hidastu? Näiden luulisi riippuvan myös käyttöjärjestelmästä ja linux-jakelusta ja siitä onko prosessori-ytimiä 1 vai useampi.
Tarkoitin muuten sekä c-taulukkoa [koko] että vectoria. Onko niillä eroa tässä suhteessa?
Missä linux-jakelussa omat ohjelmat toimivat nopeimmin?
Vaikka olisi monta ydintä, voiko omaa ohjelmaa hidastaa se jos samaan aikaan katsoo firefoxilla videoita tai saman ohjelman toinen instanssi/ olio (vai miten se pitää sanoa?) on käynnissä eri datalla?"Missä linux-jakelussa omat ohjelmat toimivat nopeimmin?"
Siinä missä uusin kääntäjä ja optimoiduimmat kirjastot. Todennäköisesti Gentoolla saat eniten irti koneesta kun käännät sen omalle koneellesi optimoiden. Toinen voisi olla Arch.- TRRY
Harrastaja591 kirjoitti:
"Ei. Esimerkki: lue kaikki taulukon tavut kertaalleen satunnaisessa järjestyksessä. 100 megan taulukosta tavut tulevat keskimäärin huomattavasti hitaammin kuin 0,1 megan taulukosta. Arvaatko syyn?"
Erityyppistä muistia fyysisesti, useimmissa tietokoneissa? Arvaus saattaa olla väärä. Ja joku on saattanut koota erilaisen tietokoneen. Entä jos sama tai eri ohjelma on jo varannut 2 gigaa muistia 4 gigasta? Ja onko joku koko kynnys minkä jälkeen alkion haku ei enää hidastu? Näiden luulisi riippuvan myös käyttöjärjestelmästä ja linux-jakelusta ja siitä onko prosessori-ytimiä 1 vai useampi.
Tarkoitin muuten sekä c-taulukkoa [koko] että vectoria. Onko niillä eroa tässä suhteessa?
Missä linux-jakelussa omat ohjelmat toimivat nopeimmin?
Vaikka olisi monta ydintä, voiko omaa ohjelmaa hidastaa se jos samaan aikaan katsoo firefoxilla videoita tai saman ohjelman toinen instanssi/ olio (vai miten se pitää sanoa?) on käynnissä eri datalla?> > 100 megan taulukosta tavut tulevat keskimäärin huomattavasti hitaammin kuin 0,1 megan taulukosta. Arvaatko syyn?
> Erityyppistä muistia fyysisesti, useimmissa tietokoneissa?
Tämän voisi hyvällä tahdolla tulkita oikeaksikin vastaukseksi. :)
Syy suorituskykyeroihin seuraa siitä, miten hyvin prosessorin välimuisti pystyy nopeuttamaan muistihakuja. Sen merkitys voi olla täysin eri kertaluokkaa kuin käyttöjärjestelmistä tai niiden kirjastoversioista seuraavat nopeuserot.
Havainnollistan muistin käyttötavan merkitystä testiohjelmalla. Jos ajat ohjelman komentoriviparametrilla 100, se varaa 100 megatavua muistia. Ohjelma täyttää muistin kunkin tavun arvoilla 0, 1, 2, ... 254, 255, 0, 1, 2, ... jne.
Ohjelma toteuttaa kaksi muistin täyttötapaa: nopean ja hitaan. Nopea tapa täyttää muistialueen järjestyksessä alusta loppuun, hidas tapa täyttää muistia 4096 tavun välein tavu kerrallaan monesta kohdasta "rinnakkain". Huomaa, että kooditasolla täyttötavat eroavat toisistaan vain sisäkkäisten for-silmukoiden järjestyksessä. Muistia täyttävä rivi "p[x] = p[x - 1] 1" suoritetaan yhtä monta kertaa kummassakin täyttötavassa. Paluuarvoksi ohjelma palauttaa kolmannesta 4096:n tavun lohkosta arvon 200 ihan vain osoitukseksi siitä, että tulos on sama.
/* Muistintäyttötesti. [email protected], 2010. */
#include
#include
int main(int argc, char **argv) {
long long koko = 1024*1024*atoi(argv[1]);
char *p = 0;
long long sivun_pohja = 0;
long long kohta = 0;
p = (char*)malloc(koko);
if (p == 0) {
printf("%d tavun varaaminen muistista ei onnistunut.\n", koko);
exit(1);
}
printf("varattiin muistia %d Mt\n", koko/1024/1024);
/* Kaksi tapaa täyttää muisti. Kommentoi aina toinen pois. */
/* nopea */
for (sivun_pohja = 0; sivun_pohja < koko; sivun_pohja = 4096) {
for (kohta = 1; kohta < 4096; kohta ) {
p[sivun_pohja kohta] = p[sivun_pohja kohta - 1] 1;
}
}
/* hidas
for (kohta = 1; kohta < 4096; kohta ) {
for (sivun_pohja = 0; sivun_pohja < koko; sivun_pohja = 4096) {
p[sivun_pohja kohta] = p[sivun_pohja kohta - 1] 1;
}
}
*/
return p[4040 2*4096];
}
Ajoin ohjelmaa näin: gcc test.c && time ./a.out 100; echo $?
Omalla koneellani (3 GHz AMD Phenom II, Debian) nopea tapa täyttää muistialueen (100 Mt) noin 0,7 sekunnissa, ja hidas tapa noin 5,1 sekunnissa. Ero on yli 7-kertainen. Yhdellä megatavulla täyttötavat ovat lähes yhtä nopeat, mutta 500 Mt:lla nopeusero on lähes 10-kertainen. Tämä osoittaa senkin, että 0,1 Mt:n taulukosta tavut löytyvät keskimäärin nopeammin kuin 100 Mt:n taulukosta.
Tarkaksi syyksi nopeuseroon epäilen prosessien loogisia muistiosoitteita fyysisiksi muistiosoitteiksi muuttavan TLB:n käyttäytymisen. Kun muisti täytetään järjestyksessä, peräkkäiset kirjoitus- ja lukukerrat osuvat lähes aina samalle muistisivulle (x86-arkkitehtuurissa tavallisesti 4096 tavua). Tällöin muistiosoitteen muunnos voidaan tehdä suoraan TLB:n tiedoilla. Tämä kestää tavallisesti vain yhden kellojakson.
Kun taas prosessin muistiavaruus on suuri ja sitä käsitellään sieltä täältä, kuten hidas täyttötapa tekee, kaikki prosessin käyttämät muistisivut eivät mahdu TLB:hen, jolloin muistiosoitteen muunnos voikin kestää jopa kymmeniä kellojaksoja. - TRRY
TRRY kirjoitti:
> > 100 megan taulukosta tavut tulevat keskimäärin huomattavasti hitaammin kuin 0,1 megan taulukosta. Arvaatko syyn?
> Erityyppistä muistia fyysisesti, useimmissa tietokoneissa?
Tämän voisi hyvällä tahdolla tulkita oikeaksikin vastaukseksi. :)
Syy suorituskykyeroihin seuraa siitä, miten hyvin prosessorin välimuisti pystyy nopeuttamaan muistihakuja. Sen merkitys voi olla täysin eri kertaluokkaa kuin käyttöjärjestelmistä tai niiden kirjastoversioista seuraavat nopeuserot.
Havainnollistan muistin käyttötavan merkitystä testiohjelmalla. Jos ajat ohjelman komentoriviparametrilla 100, se varaa 100 megatavua muistia. Ohjelma täyttää muistin kunkin tavun arvoilla 0, 1, 2, ... 254, 255, 0, 1, 2, ... jne.
Ohjelma toteuttaa kaksi muistin täyttötapaa: nopean ja hitaan. Nopea tapa täyttää muistialueen järjestyksessä alusta loppuun, hidas tapa täyttää muistia 4096 tavun välein tavu kerrallaan monesta kohdasta "rinnakkain". Huomaa, että kooditasolla täyttötavat eroavat toisistaan vain sisäkkäisten for-silmukoiden järjestyksessä. Muistia täyttävä rivi "p[x] = p[x - 1] 1" suoritetaan yhtä monta kertaa kummassakin täyttötavassa. Paluuarvoksi ohjelma palauttaa kolmannesta 4096:n tavun lohkosta arvon 200 ihan vain osoitukseksi siitä, että tulos on sama.
/* Muistintäyttötesti. [email protected], 2010. */
#include
#include
int main(int argc, char **argv) {
long long koko = 1024*1024*atoi(argv[1]);
char *p = 0;
long long sivun_pohja = 0;
long long kohta = 0;
p = (char*)malloc(koko);
if (p == 0) {
printf("%d tavun varaaminen muistista ei onnistunut.\n", koko);
exit(1);
}
printf("varattiin muistia %d Mt\n", koko/1024/1024);
/* Kaksi tapaa täyttää muisti. Kommentoi aina toinen pois. */
/* nopea */
for (sivun_pohja = 0; sivun_pohja < koko; sivun_pohja = 4096) {
for (kohta = 1; kohta < 4096; kohta ) {
p[sivun_pohja kohta] = p[sivun_pohja kohta - 1] 1;
}
}
/* hidas
for (kohta = 1; kohta < 4096; kohta ) {
for (sivun_pohja = 0; sivun_pohja < koko; sivun_pohja = 4096) {
p[sivun_pohja kohta] = p[sivun_pohja kohta - 1] 1;
}
}
*/
return p[4040 2*4096];
}
Ajoin ohjelmaa näin: gcc test.c && time ./a.out 100; echo $?
Omalla koneellani (3 GHz AMD Phenom II, Debian) nopea tapa täyttää muistialueen (100 Mt) noin 0,7 sekunnissa, ja hidas tapa noin 5,1 sekunnissa. Ero on yli 7-kertainen. Yhdellä megatavulla täyttötavat ovat lähes yhtä nopeat, mutta 500 Mt:lla nopeusero on lähes 10-kertainen. Tämä osoittaa senkin, että 0,1 Mt:n taulukosta tavut löytyvät keskimäärin nopeammin kuin 100 Mt:n taulukosta.
Tarkaksi syyksi nopeuseroon epäilen prosessien loogisia muistiosoitteita fyysisiksi muistiosoitteiksi muuttavan TLB:n käyttäytymisen. Kun muisti täytetään järjestyksessä, peräkkäiset kirjoitus- ja lukukerrat osuvat lähes aina samalle muistisivulle (x86-arkkitehtuurissa tavallisesti 4096 tavua). Tällöin muistiosoitteen muunnos voidaan tehdä suoraan TLB:n tiedoilla. Tämä kestää tavallisesti vain yhden kellojakson.
Kun taas prosessin muistiavaruus on suuri ja sitä käsitellään sieltä täältä, kuten hidas täyttötapa tekee, kaikki prosessin käyttämät muistisivut eivät mahdu TLB:hen, jolloin muistiosoitteen muunnos voikin kestää jopa kymmeniä kellojaksoja.ainakin nuo jäi pois, kun suomi24 söi koodia.
- bpdm
TRRY kirjoitti:
> > 100 megan taulukosta tavut tulevat keskimäärin huomattavasti hitaammin kuin 0,1 megan taulukosta. Arvaatko syyn?
> Erityyppistä muistia fyysisesti, useimmissa tietokoneissa?
Tämän voisi hyvällä tahdolla tulkita oikeaksikin vastaukseksi. :)
Syy suorituskykyeroihin seuraa siitä, miten hyvin prosessorin välimuisti pystyy nopeuttamaan muistihakuja. Sen merkitys voi olla täysin eri kertaluokkaa kuin käyttöjärjestelmistä tai niiden kirjastoversioista seuraavat nopeuserot.
Havainnollistan muistin käyttötavan merkitystä testiohjelmalla. Jos ajat ohjelman komentoriviparametrilla 100, se varaa 100 megatavua muistia. Ohjelma täyttää muistin kunkin tavun arvoilla 0, 1, 2, ... 254, 255, 0, 1, 2, ... jne.
Ohjelma toteuttaa kaksi muistin täyttötapaa: nopean ja hitaan. Nopea tapa täyttää muistialueen järjestyksessä alusta loppuun, hidas tapa täyttää muistia 4096 tavun välein tavu kerrallaan monesta kohdasta "rinnakkain". Huomaa, että kooditasolla täyttötavat eroavat toisistaan vain sisäkkäisten for-silmukoiden järjestyksessä. Muistia täyttävä rivi "p[x] = p[x - 1] 1" suoritetaan yhtä monta kertaa kummassakin täyttötavassa. Paluuarvoksi ohjelma palauttaa kolmannesta 4096:n tavun lohkosta arvon 200 ihan vain osoitukseksi siitä, että tulos on sama.
/* Muistintäyttötesti. [email protected], 2010. */
#include
#include
int main(int argc, char **argv) {
long long koko = 1024*1024*atoi(argv[1]);
char *p = 0;
long long sivun_pohja = 0;
long long kohta = 0;
p = (char*)malloc(koko);
if (p == 0) {
printf("%d tavun varaaminen muistista ei onnistunut.\n", koko);
exit(1);
}
printf("varattiin muistia %d Mt\n", koko/1024/1024);
/* Kaksi tapaa täyttää muisti. Kommentoi aina toinen pois. */
/* nopea */
for (sivun_pohja = 0; sivun_pohja < koko; sivun_pohja = 4096) {
for (kohta = 1; kohta < 4096; kohta ) {
p[sivun_pohja kohta] = p[sivun_pohja kohta - 1] 1;
}
}
/* hidas
for (kohta = 1; kohta < 4096; kohta ) {
for (sivun_pohja = 0; sivun_pohja < koko; sivun_pohja = 4096) {
p[sivun_pohja kohta] = p[sivun_pohja kohta - 1] 1;
}
}
*/
return p[4040 2*4096];
}
Ajoin ohjelmaa näin: gcc test.c && time ./a.out 100; echo $?
Omalla koneellani (3 GHz AMD Phenom II, Debian) nopea tapa täyttää muistialueen (100 Mt) noin 0,7 sekunnissa, ja hidas tapa noin 5,1 sekunnissa. Ero on yli 7-kertainen. Yhdellä megatavulla täyttötavat ovat lähes yhtä nopeat, mutta 500 Mt:lla nopeusero on lähes 10-kertainen. Tämä osoittaa senkin, että 0,1 Mt:n taulukosta tavut löytyvät keskimäärin nopeammin kuin 100 Mt:n taulukosta.
Tarkaksi syyksi nopeuseroon epäilen prosessien loogisia muistiosoitteita fyysisiksi muistiosoitteiksi muuttavan TLB:n käyttäytymisen. Kun muisti täytetään järjestyksessä, peräkkäiset kirjoitus- ja lukukerrat osuvat lähes aina samalle muistisivulle (x86-arkkitehtuurissa tavallisesti 4096 tavua). Tällöin muistiosoitteen muunnos voidaan tehdä suoraan TLB:n tiedoilla. Tämä kestää tavallisesti vain yhden kellojakson.
Kun taas prosessin muistiavaruus on suuri ja sitä käsitellään sieltä täältä, kuten hidas täyttötapa tekee, kaikki prosessin käyttämät muistisivut eivät mahdu TLB:hen, jolloin muistiosoitteen muunnos voikin kestää jopa kymmeniä kellojaksoja.Entä L1 ja L2 cache, prosessorin sisällä ja ulkona?
Mistä tietää mikä data menee niihin erityisen nopeisiin muisteihin ja varaako muut ohjelmat ne?
Olen itse ihan tyytyväinen rand() funktioon kun otan siemenluvun kellon mukaan ja pyrin käyttämään eniten merkitseviä bittejä.
En ole ainakaan vielä tarvinnut parempaa satunnaisuutta.- aapeli.
Tarkoiti kai vähiten merkitseviä?
aapeli. kirjoitti:
Tarkoiti kai vähiten merkitseviä?
En. En siis harrasta jakojäännöksellä sen satunnaisluvunlaskemista vaan jakamalla RAND_MAX:lla. Ainakin ennen joissakin toteutuksissa oli satunnaisluvut parempia.
- aapeli.
M-Kar kirjoitti:
En. En siis harrasta jakojäännöksellä sen satunnaisluvunlaskemista vaan jakamalla RAND_MAX:lla. Ainakin ennen joissakin toteutuksissa oli satunnaisluvut parempia.
aivan totta, sekoilin tuosta siemenluvun käytöstä
- nopia keino
Satunnaislukuja saa nopeasti veikkauksen sivuilta. Valitse sieltä jokin vekkauksen arpomista lottoriveistä: sen lähemmäksi konesatunnaisuutta et millään pääse
Ketjusta on poistettu 0 sääntöjenvastaista viestiä.
Luetuimmat keskustelut
Aivosyöpää sairastava Olga Temonen TV:ssä - Viimeinen Perjantai-keskusteluohjelma ulos
Näyttelijä-yrittäjä Olga Temonen sairastaa neljännen asteen glioomaa eli aivosyöpää, jota ei ole mahdollista leikata. Hä912910Pelotelkaa niin paljon kuin sielu sietää.
Mutta ei mene perille asti. Miksi Venäjä hyökkäisi Suomeen? No, tottahan se tietenkin on jos Suomi joka ei ole edes soda2991686Mikä saa ihmisen tekemään tällaista?
Onko se huomatuksi tulemisen tarve tosiaan niin iso tarve, että nuoruuttaan ja tietämättömyyttään pilataan loppuelämä?2461557- 871391
IL - VARUSMIEHIÄ lähetetään jatkossa NATO-tehtäviin ulkomaille!
Suomen puolustuksen uudet linjaukset: Varusmiehiä suunnitellaan Nato-tehtäviin Puolustusministeri Antti Häkkänen esittel4021384Nyt kun Pride on ohi 3.0
Edelliset kaksi ketjua tuli täyteen. Pidetään siis edelleen tämä asia esillä. Raamattu opettaa johdonmukaisesti, että4001307Kiitos nainen
Kuitenkin. Olet sitten ajanmerkkinä. Tuskin enää sinua näen ja huomasitko, että olit siinä viimeisen kerran samassa paik21089Esko Eerikäinen tatuoi kasvoihinsa rakkaan nimen - Kärkäs kommentti "Ritvasta" lävähti somessa
Ohhoh! Esko Eerikäinen on ottanut uuden tatuoinnin. Kyseessä ei ole mikä tahansa kuva minne tahansa, vaan Eerikäisen tat381037Hyväksytkö sinä sen että päättäjämme ei rakenna rauhaa Venäjän kanssa?
Vielä kun sota ehkäpä voitaisiin välttää rauhanponnisteluilla niin millä verukkeella voidaan sanoa että on hyvä asia kun329874Miksi Purra-graffiti ei nyt olekkaan naisvihaa?
"Pohtikaapa reaktiota, jos vastaava graffiti olisi tehty Sanna Marinista", kysyy Tere Sammallahti. Helsingin Suvilahden257855