Otmar Ertl created MATH-1242: -------------------------------- Summary: 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 Attachments: 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)