[ https://issues.apache.org/jira/browse/MATH-1242?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Otmar Ertl resolved MATH-1242. ------------------------------ Resolution: Fixed > Speed up KolmogorovSmirnovTest.monteCarloP() > -------------------------------------------- > > Key: MATH-1242 > URL: https://issues.apache.org/jira/browse/MATH-1242 > Project: Commons Math > Issue Type: Improvement > Reporter: Otmar Ertl > Fix For: 4.0, 3.6 > > Attachments: bug_fix_and_unit_test.patch, modified.patch, patch, patch > > > The advantages of the new implementation are: > * It has linear run-time complexity because sorting of data is avoided > * Consumes less than half random numbers (min(n,m) instead of (n+m)) > * Allocates less memory > The speed-up can be verified using the testTwoSampleMonteCarloPerformance() > unit test. Here is the output on my machine of the test using the old > monteCarloP() implementation > {noformat} > n=2, m=5000, time=16.894s > n=3, m=3333, time=11.917s > n=4, m=2500, time=8.69s > n=5, m=2000, time=7.38s > n=6, m=1666, time=6.235s > n=7, m=1428, time=5.472s > n=8, m=1250, time=4.517s > n=9, m=1111, time=4.246s > n=10, m=1000, time=3.797s > n=11, m=909, time=3.502s > n=12, m=833, time=3.249s > n=13, m=769, time=3.0s > n=14, m=714, time=2.816s > n=15, m=666, time=2.669s > n=16, m=625, time=2.44s > n=17, m=588, time=2.443s > n=18, m=555, time=2.349s > n=19, m=526, time=2.219s > n=20, m=500, time=2.135s > n=21, m=476, time=2.022s > n=22, m=454, time=1.952s > n=23, m=434, time=1.907s > n=24, m=416, time=1.823s > n=25, m=400, time=1.793s > n=26, m=384, time=1.783s > n=27, m=370, time=1.655s > n=28, m=357, time=1.602s > n=29, m=344, time=1.549s > n=30, m=333, time=1.513s > n=31, m=322, time=1.492s > n=32, m=312, time=1.382s > n=33, m=303, time=1.391s > n=34, m=294, time=1.383s > n=35, m=285, time=1.454s > n=36, m=277, time=1.433s > n=37, m=270, time=1.402s > n=38, m=263, time=1.374s > n=39, m=256, time=1.286s > n=40, m=250, time=1.334s > n=41, m=243, time=1.328s > n=42, m=238, time=1.306s > n=43, m=232, time=1.316s > n=44, m=227, time=1.273s > n=45, m=222, time=1.304s > n=46, m=217, time=1.265s > n=47, m=212, time=1.254s > n=48, m=208, time=1.243s > n=49, m=204, time=1.236s > n=50, m=200, time=1.237s > n=51, m=196, time=1.201s > n=52, m=192, time=1.227s > n=53, m=188, time=1.179s > n=54, m=185, time=1.162s > n=55, m=181, time=1.163s > n=56, m=178, time=1.16s > n=57, m=175, time=1.167s > n=58, m=172, time=1.168s > n=59, m=169, time=1.169s > n=60, m=166, time=1.167s > n=61, m=163, time=1.171s > n=62, m=161, time=1.183s > n=63, m=158, time=1.132s > n=64, m=156, time=1.127s > n=65, m=153, time=1.153s > n=66, m=151, time=1.139s > n=67, m=149, time=1.107s > n=68, m=147, time=1.103s > n=69, m=144, time=1.118s > n=70, m=142, time=1.124s > n=71, m=140, time=1.12s > n=72, m=138, time=1.143s > n=73, m=136, time=1.146s > n=74, m=135, time=1.143s > n=75, m=133, time=1.141s > n=76, m=131, time=1.138s > n=77, m=129, time=1.137s > n=78, m=128, time=1.1s > n=79, m=126, time=1.111s > n=80, m=125, time=1.109s > n=81, m=123, time=1.145s > n=82, m=121, time=1.135s > n=83, m=120, time=1.122s > n=84, m=119, time=1.132s > n=85, m=117, time=1.137s > n=86, m=116, time=1.133s > n=87, m=114, time=1.115s > n=88, m=113, time=1.123s > n=89, m=112, time=1.121s > n=90, m=111, time=1.134s > n=91, m=109, time=1.145s > n=92, m=108, time=1.156s > n=93, m=107, time=1.153s > n=94, m=106, time=1.137s > n=95, m=105, time=1.134s > n=96, m=104, time=1.147s > n=97, m=103, time=1.151s > n=98, m=102, time=1.147s > n=99, m=101, time=1.181s > n=100, m=100, time=1.189s > {noformat} > and this is the output using the new implementation > {noformat} > n=2, m=5000, time=0.602s > n=3, m=3333, time=0.4s > n=4, m=2500, time=0.192s > n=5, m=2000, time=0.163s > n=6, m=1666, time=0.144s > n=7, m=1428, time=0.129s > n=8, m=1250, time=0.115s > n=9, m=1111, time=0.117s > n=10, m=1000, time=0.11s > n=11, m=909, time=0.106s > n=12, m=833, time=0.11s > n=13, m=769, time=0.102s > n=14, m=714, time=0.104s > n=15, m=666, time=0.103s > n=16, m=625, time=0.094s > n=17, m=588, time=0.102s > n=18, m=555, time=0.106s > n=19, m=526, time=0.106s > n=20, m=500, time=0.151s > n=21, m=476, time=0.118s > n=22, m=454, time=0.12s > n=23, m=434, time=0.123s > n=24, m=416, time=0.126s > n=25, m=400, time=0.127s > n=26, m=384, time=0.13s > n=27, m=370, time=0.132s > n=28, m=357, time=0.135s > n=29, m=344, time=0.137s > n=30, m=333, time=0.14s > n=31, m=322, time=0.143s > n=32, m=312, time=0.133s > n=33, m=303, time=0.149s > n=34, m=294, time=0.162s > n=35, m=285, time=0.156s > n=36, m=277, time=0.157s > n=37, m=270, time=0.16s > n=38, m=263, time=0.168s > n=39, m=256, time=0.148s > n=40, m=250, time=0.184s > n=41, m=243, time=0.175s > n=42, m=238, time=0.175s > n=43, m=232, time=0.179s > n=44, m=227, time=0.186s > n=45, m=222, time=0.186s > n=46, m=217, time=0.188s > n=47, m=212, time=0.192s > n=48, m=208, time=0.195s > n=49, m=204, time=0.199s > n=50, m=200, time=0.21s > n=51, m=196, time=0.205s > n=52, m=192, time=0.208s > n=53, m=188, time=0.24s > n=54, m=185, time=0.22s > n=55, m=181, time=0.218s > n=56, m=178, time=0.222s > n=57, m=175, time=0.225s > n=58, m=172, time=0.229s > n=59, m=169, time=0.231s > n=60, m=166, time=0.235s > n=61, m=163, time=0.239s > n=62, m=161, time=0.241s > n=63, m=158, time=0.245s > n=64, m=156, time=0.234s > n=65, m=153, time=0.252s > n=66, m=151, time=0.254s > n=67, m=149, time=0.257s > n=68, m=147, time=0.26s > n=69, m=144, time=0.264s > n=70, m=142, time=0.266s > n=71, m=140, time=0.281s > n=72, m=138, time=0.274s > n=73, m=136, time=0.276s > n=74, m=135, time=0.279s > n=75, m=133, time=0.282s > n=76, m=131, time=0.286s > n=77, m=129, time=0.288s > n=78, m=128, time=0.279s > n=79, m=126, time=0.296s > n=80, m=125, time=0.298s > n=81, m=123, time=0.301s > n=82, m=121, time=0.304s > n=83, m=120, time=0.307s > n=84, m=119, time=0.31s > n=85, m=117, time=0.325s > n=86, m=116, time=0.318s > n=87, m=114, time=0.319s > n=88, m=113, time=0.323s > n=89, m=112, time=0.326s > n=90, m=111, time=0.328s > n=91, m=109, time=0.331s > n=92, m=108, time=0.349s > n=93, m=107, time=0.339s > n=94, m=106, time=0.34s > n=95, m=105, time=0.344s > n=96, m=104, time=0.347s > n=97, m=103, time=0.349s > n=98, m=102, time=0.353s > n=99, m=101, time=0.368s > n=100, m=100, time=0.358s > {noformat} -- This message was sent by Atlassian JIRA (v6.3.4#6332)