Article View: pl.comp.lang.c
Article #310051Re: Optymalizacja kodu
From: M.M.
Date: Thu, 02 Jan 2020 05:14
Date: Thu, 02 Jan 2020 05:14
354 lines
19788 bytes
19788 bytes
On Sunday, December 29, 2019 at 8:00:28 PM UTC+1, Wojciech Muła wrote:
> On Friday, December 27, 2019 at 8:45:01 AM UTC+1, M.M. wrote:
> > On Thursday, December 26, 2019 at 9:57:09 AM UTC+1, Wojciech Muła wrote:
> > > Sprawdź, jak się sprawuje ten algorytm https://lemire.me/blog/2019/07/03/a-fast-16-bit-random-number-generator/
> >
> > Mam pytanie, czy można mieć kod tego generatora w swoich programach? Jest
> > jakaś licencja?
>
> https://github.com/lemire/Code-used-on-Daniel-Lemire-s-blog/blob/master/README.md
>
> "Unless otherwise stated, I make no copyright claim on this code: you may consider it to be in the public domain.
>
> Don't bother forking this code: just steal it."
>
> w.
Uwaga: Czasy są poglądowe, bo komputer był obciążony. Zarodki są inne niż
wyświetlone.
Tutaj pełen test generatora wyhash64 na dieharderze, widać że zaliczony:
time ./MRndCPP2 | dieharder -g200 -a -k2
#=============================================================================#
# dieharder version 3.31.1 Copyright 2003 Robert G. Brown #
#=============================================================================#
rng_name |rands/second| Seed |
stdin_input_raw| 2.24e+07 |2577951266|
#=============================================================================#
test_name |ntup| tsamples |psamples| p-value |Assessment
#=============================================================================#
diehard_birthdays| 0| 100| 100|0.81026922| PASSED
diehard_operm5| 0| 1000000| 100|0.98679548| PASSED
diehard_rank_32x32| 0| 40000| 100|0.71416552| PASSED
diehard_rank_6x8| 0| 100000| 100|0.51696514| PASSED
diehard_bitstream| 0| 2097152| 100|0.63316532| PASSED
diehard_opso| 0| 2097152| 100|0.96492817| PASSED
diehard_oqso| 0| 2097152| 100|0.83902928| PASSED
diehard_dna| 0| 2097152| 100|0.25207588| PASSED
diehard_count_1s_str| 0| 256000| 100|0.52915716| PASSED
diehard_count_1s_byt| 0| 256000| 100|0.95076645| PASSED
diehard_parking_lot| 0| 12000| 100|0.90388634| PASSED
diehard_2dsphere| 2| 8000| 100|0.28100768| PASSED
diehard_3dsphere| 3| 4000| 100|0.88633340| PASSED
diehard_squeeze| 0| 100000| 100|0.26057188| PASSED
diehard_sums| 0| 100| 100|0.09292146| PASSED
diehard_runs| 0| 100000| 100|0.43772796| PASSED
diehard_runs| 0| 100000| 100|0.02237980| PASSED
diehard_craps| 0| 200000| 100|0.69281661| PASSED
diehard_craps| 0| 200000| 100|0.56674609| PASSED
marsaglia_tsang_gcd| 0| 10000000| 100|0.23008321| PASSED
marsaglia_tsang_gcd| 0| 10000000| 100|0.87485793| PASSED
sts_monobit| 1| 100000| 100|0.33312220| PASSED
sts_runs| 2| 100000| 100|0.93844784| PASSED
sts_serial| 1| 100000| 100|0.20273716| PASSED
sts_serial| 2| 100000| 100|0.09850698| PASSED
sts_serial| 3| 100000| 100|0.75334509| PASSED
sts_serial| 3| 100000| 100|0.57132578| PASSED
sts_serial| 4| 100000| 100|0.99728968| WEAK
sts_serial| 4| 100000| 100|0.86993019| PASSED
sts_serial| 5| 100000| 100|0.69177051| PASSED
sts_serial| 5| 100000| 100|0.88240774| PASSED
sts_serial| 6| 100000| 100|0.68852405| PASSED
sts_serial| 6| 100000| 100|0.11358621| PASSED
sts_serial| 7| 100000| 100|0.99123468| PASSED
sts_serial| 7| 100000| 100|0.07363269| PASSED
sts_serial| 8| 100000| 100|0.77877807| PASSED
sts_serial| 8| 100000| 100|0.48870919| PASSED
sts_serial| 9| 100000| 100|0.28300283| PASSED
sts_serial| 9| 100000| 100|0.56293370| PASSED
sts_serial| 10| 100000| 100|0.69074909| PASSED
sts_serial| 10| 100000| 100|0.73542549| PASSED
sts_serial| 11| 100000| 100|0.07321933| PASSED
sts_serial| 11| 100000| 100|0.58896333| PASSED
sts_serial| 12| 100000| 100|0.28161926| PASSED
sts_serial| 12| 100000| 100|0.92644298| PASSED
sts_serial| 13| 100000| 100|0.05086176| PASSED
sts_serial| 13| 100000| 100|0.27981417| PASSED
sts_serial| 14| 100000| 100|0.22519486| PASSED
sts_serial| 14| 100000| 100|0.77315819| PASSED
sts_serial| 15| 100000| 100|0.01165574| PASSED
sts_serial| 15| 100000| 100|0.02665459| PASSED
sts_serial| 16| 100000| 100|0.26242221| PASSED
sts_serial| 16| 100000| 100|0.43830761| PASSED
rgb_bitdist| 1| 100000| 100|0.31452766| PASSED
rgb_bitdist| 2| 100000| 100|0.39767941| PASSED
rgb_bitdist| 3| 100000| 100|0.82520370| PASSED
rgb_bitdist| 4| 100000| 100|0.69802529| PASSED
rgb_bitdist| 5| 100000| 100|0.60286533| PASSED
rgb_bitdist| 6| 100000| 100|0.76287425| PASSED
rgb_bitdist| 7| 100000| 100|0.48130619| PASSED
rgb_bitdist| 8| 100000| 100|0.67608036| PASSED
rgb_bitdist| 9| 100000| 100|0.78947721| PASSED
rgb_bitdist| 10| 100000| 100|0.16690659| PASSED
rgb_bitdist| 11| 100000| 100|0.08735874| PASSED
rgb_bitdist| 12| 100000| 100|0.25206410| PASSED
rgb_minimum_distance| 2| 10000| 1000|0.00146107| WEAK
rgb_minimum_distance| 3| 10000| 1000|0.98873968| PASSED
rgb_minimum_distance| 4| 10000| 1000|0.95856433| PASSED
rgb_minimum_distance| 5| 10000| 1000|0.80685775| PASSED
rgb_permutations| 2| 100000| 100|0.20047125| PASSED
rgb_permutations| 3| 100000| 100|0.66596447| PASSED
rgb_permutations| 4| 100000| 100|0.50658066| PASSED
rgb_permutations| 5| 100000| 100|0.72548917| PASSED
rgb_lagged_sum| 0| 1000000| 100|0.86970338| PASSED
rgb_lagged_sum| 1| 1000000| 100|0.22662204| PASSED
rgb_lagged_sum| 2| 1000000| 100|0.27081183| PASSED
rgb_lagged_sum| 3| 1000000| 100|0.40143564| PASSED
rgb_lagged_sum| 4| 1000000| 100|0.92310721| PASSED
rgb_lagged_sum| 5| 1000000| 100|0.22827856| PASSED
rgb_lagged_sum| 6| 1000000| 100|0.56825732| PASSED
rgb_lagged_sum| 7| 1000000| 100|0.56570034| PASSED
rgb_lagged_sum| 8| 1000000| 100|0.51714557| PASSED
rgb_lagged_sum| 9| 1000000| 100|0.98392710| PASSED
rgb_lagged_sum| 10| 1000000| 100|0.27250657| PASSED
rgb_lagged_sum| 11| 1000000| 100|0.95516885| PASSED
rgb_lagged_sum| 12| 1000000| 100|0.58962187| PASSED
rgb_lagged_sum| 13| 1000000| 100|0.23946733| PASSED
rgb_lagged_sum| 14| 1000000| 100|0.17323052| PASSED
rgb_lagged_sum| 15| 1000000| 100|0.21578945| PASSED
rgb_lagged_sum| 16| 1000000| 100|0.22688738| PASSED
rgb_lagged_sum| 17| 1000000| 100|0.26143583| PASSED
rgb_lagged_sum| 18| 1000000| 100|0.51841646| PASSED
rgb_lagged_sum| 19| 1000000| 100|0.94883960| PASSED
rgb_lagged_sum| 20| 1000000| 100|0.80882001| PASSED
rgb_lagged_sum| 21| 1000000| 100|0.94493061| PASSED
rgb_lagged_sum| 22| 1000000| 100|0.82077584| PASSED
rgb_lagged_sum| 23| 1000000| 100|0.45537077| PASSED
rgb_lagged_sum| 24| 1000000| 100|0.87466395| PASSED
rgb_lagged_sum| 25| 1000000| 100|0.83690335| PASSED
rgb_lagged_sum| 26| 1000000| 100|0.26485784| PASSED
rgb_lagged_sum| 27| 1000000| 100|0.96001824| PASSED
rgb_lagged_sum| 28| 1000000| 100|0.12250941| PASSED
rgb_lagged_sum| 29| 1000000| 100|0.36885207| PASSED
rgb_lagged_sum| 30| 1000000| 100|0.91444238| PASSED
rgb_lagged_sum| 31| 1000000| 100|0.87605244| PASSED
rgb_lagged_sum| 32| 1000000| 100|0.52384561| PASSED
rgb_kstest_test| 0| 10000| 1000|0.56713236| PASSED
dab_bytedistrib| 0| 51200000| 1|0.69832879| PASSED
dab_dct| 256| 50000| 1|0.83845186| PASSED
Preparing to run test 207. ntuple = 0
dab_filltree| 32| 15000000| 1|0.47593522| PASSED
dab_filltree| 32| 15000000| 1|0.10222342| PASSED
Preparing to run test 208. ntuple = 0
dab_filltree2| 0| 5000000| 1|0.10419158| PASSED
dab_filltree2| 1| 5000000| 1|0.21159375| PASSED
Preparing to run test 209. ntuple = 0
dab_monobit2| 12| 65000000| 1|0.83878560| PASSED
real 58m32.504s
user 58m19.365s
sys 5m29.716s
Tuta około 2tys testów w programem pract_rand, widać że dwa rozkłady
wypadły jako bardzo rzadkie (prawdopodobieństwo około kilku stu-tysięcznych),
pract_rand oznaczył te testy jako średnio podejrzane:
time ./MRndCPP | ../../PractRand/RNG_test stdin
RNG_test using PractRand version 0.93
RNG = RNG_stdin, seed = 0xad8296e3
test set = normal, folding = standard(unknown format)
rng=RNG_stdin, seed=0xad8296e3
length= 128 megabytes (2^27 bytes), time= 2.6 seconds
no anomalies in 151 test result(s)
rng=RNG_stdin, seed=0xad8296e3
length= 256 megabytes (2^28 bytes), time= 5.8 seconds
Test Name Raw Processed Evaluation
[Low1/8]BCFN(2+1,13-4,T) R= +8.4 p = 1.3e-3 unusual
...and 161 test result(s) without anomalies
rng=RNG_stdin, seed=0xad8296e3
length= 512 megabytes (2^29 bytes), time= 11.3 seconds
no anomalies in 171 test result(s)
rng=RNG_stdin, seed=0xad8296e3
length= 1 gigabyte (2^30 bytes), time= 21.8 seconds
Test Name Raw Processed Evaluation
BCFN(2+1,13-1,T) R= -9.8 p =1-2.1e-5 mildly suspicious
...and 182 test result(s) without anomalies
rng=RNG_stdin, seed=0xad8296e3
length= 2 gigabytes (2^31 bytes), time= 41.9 seconds
Test Name Raw Processed Evaluation
BCFN(2+1,13-0,T) R= -9.5 p =1-4.6e-5 mildly suspicious
...and 193 test result(s) without anomalies
rng=RNG_stdin, seed=0xad8296e3
length= 4 gigabytes (2^32 bytes), time= 80.4 seconds
no anomalies in 203 test result(s)
rng=RNG_stdin, seed=0xad8296e3
length= 8 gigabytes (2^33 bytes), time= 159 seconds
no anomalies in 215 test result(s)
rng=RNG_stdin, seed=0xad8296e3
length= 16 gigabytes (2^34 bytes), time= 314 seconds
no anomalies in 226 test result(s)
rng=RNG_stdin, seed=0xad8296e3
length= 32 gigabytes (2^35 bytes), time= 621 seconds
no anomalies in 235 test result(s)
^C
real 19m50.004s
user 19m19.332s
sys 0m38.718s
Tutaj dłuży test programem pract_rand: Jeden test mało
prawdopodobny 1-8.7e-5, ale pract_rand oznaczył go tylko
jako unusual.
time ./MRndCPP2 | ../../PractRand/RNG_test stdin
RNG_test using PractRand version 0.93
RNG = RNG_stdin, seed = 0xdbda558d
test set = normal, folding = standard(unknown format)
rng=RNG_stdin, seed=0xdbda558d
length= 128 megabytes (2^27 bytes), time= 2.5 seconds
no anomalies in 151 test result(s)
rng=RNG_stdin, seed=0xdbda558d
length= 256 megabytes (2^28 bytes), time= 5.8 seconds
no anomalies in 162 test result(s)
rng=RNG_stdin, seed=0xdbda558d
length= 512 megabytes (2^29 bytes), time= 11.4 seconds
Test Name Raw Processed Evaluation
[Low1/8]FPF-14+6/16:cross R= +4.4 p = 3.9e-4 unusual
...and 170 test result(s) without anomalies
rng=RNG_stdin, seed=0xdbda558d
length= 1 gigabyte (2^30 bytes), time= 23.5 seconds
no anomalies in 183 test result(s)
rng=RNG_stdin, seed=0xdbda558d
length= 2 gigabytes (2^31 bytes), time= 45.1 seconds
no anomalies in 194 test result(s)
rng=RNG_stdin, seed=0xdbda558d
length= 4 gigabytes (2^32 bytes), time= 88.9 seconds
no anomalies in 203 test result(s)
rng=RNG_stdin, seed=0xdbda558d
length= 8 gigabytes (2^33 bytes), time= 178 seconds
no anomalies in 215 test result(s)
rng=RNG_stdin, seed=0xdbda558d
length= 16 gigabytes (2^34 bytes), time= 355 seconds
no anomalies in 226 test result(s)
rng=RNG_stdin, seed=0xdbda558d
length= 32 gigabytes (2^35 bytes), time= 762 seconds
Test Name Raw Processed Evaluation
[Low4/32]Gap-16:B R= -4.2 p =1-1.7e-3 unusual
...and 234 test result(s) without anomalies
yyuyrng=RNG_stdin, seed=0xdbda558d
length= 64 gigabytes (2^36 bytes), time= 1759 seconds
no anomalies in 247 test result(s)
rng=RNG_stdin, seed=0xdbda558d
length= 128 gigabytes (2^37 bytes), time= 3845 seconds
Test Name Raw Processed Evaluation
BCFN(2+4,13-0,T) R= -9.0 p =1-8.7e-5 unusual
...and 257 test result(s) without anomalies
rng=RNG_stdin, seed=0xdbda558d
length= 256 gigabytes (2^38 bytes), time= 6752 seconds
no anomalies in 267 test result(s)
rng=RNG_stdin, seed=0xdbda558d
length= 512 gigabytes (2^39 bytes), time= 12607 seconds
no anomalies in 279 test result(s)
rng=RNG_stdin, seed=0xdbda558d
length= 1 terabyte (2^40 bytes), time= 24343 seconds
no anomalies in 290 test result(s)
Poniżej test mojej lekkiej modyfikacji generatora wyhash64, widać
że tylko jeden test ma prawdopodobieństwo 3.0e-3, co na 1-2tys
testów właśnie raz powinno się zdarzyć. Niestety moja modyfikacja
jest wielokrotnie wolniejsza od oryginału, cały program generujący
liczby jest 4 razy wolniejszy:
./MRndCPP | ../../PractRand/RNG_test stdin
RNG_test using PractRand version 0.93
RNG = RNG_stdin, seed = 0xff13eeed
test set = normal, folding = standard(unknown format)
rng=RNG_stdin, seed=0xff13eeed
length= 128 megabytes (2^27 bytes), time= 2.9 seconds
no anomalies in 151 test result(s)
rng=RNG_stdin, seed=0xff13eeed
length= 256 megabytes (2^28 bytes), time= 6.7 seconds
no anomalies in 162 test result(s)
rng=RNG_stdin, seed=0xff13eeed
length= 512 megabytes (2^29 bytes), time= 13.1 seconds
no anomalies in 171 test result(s)
rng=RNG_stdin, seed=0xff13eeed
length= 1 gigabyte (2^30 bytes), time= 25.3 seconds
no anomalies in 183 test result(s)
rng=RNG_stdin, seed=0xff13eeed
length= 2 gigabytes (2^31 bytes), time= 48.8 seconds
no anomalies in 194 test result(s)
rng=RNG_stdin, seed=0xff13eeed
length= 4 gigabytes (2^32 bytes), time= 94.4 seconds
Test Name Raw Processed Evaluation
[Low4/32]DC6-9x1Bytes-1 R= +5.9 p = 3.0e-3 unusual
...and 202 test result(s) without anomalies
rng=RNG_stdin, seed=0xff13eeed
length= 8 gigabytes (2^33 bytes), time= 187 seconds
no anomalies in 215 test result(s)
rng=RNG_stdin, seed=0xff13eeed
length= 16 gigabytes (2^34 bytes), time= 368 seconds
no anomalies in 226 test result(s)
rng=RNG_stdin, seed=0xff13eeed
length= 32 gigabytes (2^35 bytes), time= 801 seconds
no anomalies in 235 test result(s)
rng=RNG_stdin, seed=0xff13eeed
length= 64 gigabytes (2^36 bytes), time= 1825 seconds
no anomalies in 247 test result(s)
rng=RNG_stdin, seed=0xff13eeed
length= 128 gigabytes (2^37 bytes), time= 3980 seconds
no anomalies in 258 test result(s)
rng=RNG_stdin, seed=0xff13eeed
length= 256 gigabytes (2^38 bytes), time= 6931 seconds
no anomalies in 267 test result(s)
rng=RNG_stdin, seed=0xff13eeed
length= 512 gigabytes (2^39 bytes), time= 12961 seconds
no anomalies in 279 test result(s)
rng=RNG_stdin, seed=0xff13eeed
length= 1 terabyte (2^40 bytes), time= 25046 seconds
no anomalies in 290 test result(s)
Technical Details
Message-ID:
<7671450d-1832-4773-aa58-9b2a47dea911@googlegroups.com>Path:
mbox-mo1.pugleaf.net!news-archive.icm.edu.pl!news.icm.edu.pl!newsfeed.pionier.net.pl!feeder.erje.net!2.eu.feeder.erje.net!feeder5.feed.usenet.farm!feed.usenet.farm!feeder.usenetexpress.com!tr1.iad1.usenetexpress.com!border1.nntp.dca1.giganews.com!nntp.giganews.com!g89no4770593qtd.0!news-out.google.com!w29ni416qtc.0!nntp.google.com!g89no4770589qtd.0!postnews.google.com!google-groups.googlegroups.com!not-for-mailReferences:
<ed3041b7-c05f-43f3-887a-9a12a9633741@googlegroups.com> <2104ea83-5daa-4752-9a63-ed3346a14082@googlegroups.com> <82f8e967-0d0e-4bae-b005-aacb301b2349@googlegroups.com> <c635fa1a-0b40-4790-8155-5b92fd4682e9@googlegroups.com>Show Full Headers
Complete Article Headers
X-Received: by 2002:ac8:5048:: with SMTP id h8mr57606925qtm.328.1577942093336; Wed, 01 Jan 2020 21:14:53 -0800 (PST) X-Received: by 2002:a0d:e9c2:: with SMTP id s185mr56744512ywe.25.1577942093108; Wed, 01 Jan 2020 21:14:53 -0800 (PST) Path: mbox-mo1.pugleaf.net!news-archive.icm.edu.pl!news.icm.edu.pl!newsfeed.pionier.net.pl!feeder.erje.net!2.eu.feeder.erje.net!feeder5.feed.usenet.farm!feed.usenet.farm!feeder.usenetexpress.com!tr1.iad1.usenetexpress.com!border1.nntp.dca1.giganews.com!nntp.giganews.com!g89no4770593qtd.0!news-out.google.com!w29ni416qtc.0!nntp.google.com!g89no4770589qtd.0!postnews.google.com!google-groups.googlegroups.com!not-for-mail Newsgroups: pl.comp.lang.c Date: Wed, 1 Jan 2020 21:14:52 -0800 (PST) In-Reply-To: <c635fa1a-0b40-4790-8155-5b92fd4682e9@googlegroups.com> Complaints-To: groups-abuse@google.com Injection-Info: google-groups.googlegroups.com; posting-host=77.254.46.242; posting-account=xjvq9QoAAAATMPC2X3btlHd_LkaJo_rj NNTP-Posting-Host: 77.254.46.242 References: <ed3041b7-c05f-43f3-887a-9a12a9633741@googlegroups.com> <2104ea83-5daa-4752-9a63-ed3346a14082@googlegroups.com> <82f8e967-0d0e-4bae-b005-aacb301b2349@googlegroups.com> <c635fa1a-0b40-4790-8155-5b92fd4682e9@googlegroups.com> User-Agent: G2/1.0 MIME-Version: 1.0 Message-ID: <7671450d-1832-4773-aa58-9b2a47dea911@googlegroups.com> Subject: Re: Optymalizacja kodu From: "M.M." <mmarszik@gmail.com> Injection-Date: Thu, 02 Jan 2020 05:14:53 +0000 Lines: 410 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit