[
https://issues.apache.org/jira/browse/MATH-1242?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Thomas Neidhart updated MATH-1242:
----------------------------------
Attachment: modified.patch
Hi Otmar,
I have reviewed your patch and I can confirm that the results are correct. The
speed improvements are impressive, and your approach is very clever, although
it took me a while to understand it.
Please find attached a modified version of your patch that slightly changes the
calculation of the KS statistic to match it with the way it is done in the
kolmogorovSmirnovStatistic method and for easier understanding of myself.
Furthermore, the loop now starts at index 1, as the first iteration always
resulted in a curD calculated as 0. This further improves the performance a
little bit.
Does this makes sense to you?
> 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: modified.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)
