[MATH-1242] Speed up KolmogorovSmirnovTest.monteCarloP()

• Type: Improvement
• Status: Closed
• Priority: Major
• Resolution: Fixed
• Fix Version/s: 4.0, 3.6
• Flags: Patch
• Assignee: Unassigned
• Reporter: Otmar Ertl
• Created: 25/Jun/15 18:38
• Updated: 25/Jan/16 20:27
• Resolved: 17/Jul/15 19:56

Description

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

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

and this is the output using the new implementation

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

Issue Links

• relates to: MATH-1179 kolmogorovSmirnovTest poor performance in monteCarloP method