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

["Thomas Neidhart (JIRA)" <ji...@apache.org>]

     [ https://issues.apache.org/jira/browse/MATH-1242?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Thomas Neidhart resolved MATH-1242.
-----------------------------------
       Resolution: Fixed
    Fix Version/s: 3.6
                   4.0

Fixed in the following commits:

 * 4.0: 6d7ee38ceed6b496d70502e276f80be6de618014
 * 3.6: 6209faba243293c9192ba47e027aed46966b86d7

Thanks for the report and patch!

> 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: 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)