Uploaded image for project: 'Commons Math'
  1. Commons Math
  2. MATH-1242

Speed up KolmogorovSmirnovTest.monteCarloP()

    Details

    • Type: Improvement
    • Status: Closed
    • Priority: Major
    • Resolution: Fixed
    • Affects Version/s: None
    • Fix Version/s: 4.0, 3.6
    • Labels:
      None
    • Flags:
      Patch

      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
      

        Attachments

        1. bug_fix_and_unit_test.patch
          6 kB
          Otmar Ertl
        2. modified.patch
          4 kB
          Thomas Neidhart
        3. patch
          0.7 kB
          Otmar Ertl
        4. patch
          5 kB
          Otmar Ertl

          Issue Links

            Activity

              People

              • Assignee:
                Unassigned
                Reporter:
                Otmar Ertl Otmar Ertl
              • Votes:
                0 Vote for this issue
                Watchers:
                3 Start watching this issue

                Dates

                • Created:
                  Updated:
                  Resolved: