search

zhaonian / Air-Traffic-Controller

an extremely fast algorithm for large-scale online advertising optimization.
4 stars 1 forks source link

Profiling result shows 82% of the run time is spent in CDF calculation #2

Closed DaviesX closed 8 years ago

DaviesX commented 8 years ago 
INITIAL
eeny , eeny , 7.431093 , 0.900335 ; 4.0 , 0.637925 , 0.14892 , 0.382864 , 0.092765

meany , meany , 24.891589 , 0.910925 ; 4.0 , 0.593279 , 0.511503 , 0.284545 , 0.339193

miny , miny , 32.163439 , 0.727152 ; 4.0 , 0.271691 , 0.895381 , 0.312952 , 0.962457

moe , moe , 79.763438 , 0.179283 ; 4.0 , 0.213952 , 0.982373 , 0.253538 , 0.635217

alan , alan , 71.32961 , 0.930679 ; 4.0 , 0.117261 , 0.181536 , 0.901166 , 0.062637

Is admissible? False Expected value: 9.31651875059
MADE ADMISSIBLE
alan , alan , 71.32961 , 0.930679 ; 4.0 , 0.117261 , 0.181536 , 0.901166 , 0.062637

Is admissible? True Expected value: 68.3405504757
miny , miny , 32.163439 , 0.727152 ; 4.0 , 0.271691 , 0.895381 , 0.312952 , 0.962457

Is admissible? True Expected value: 68.3405504757
meany , meany , 24.891589 , 0.910925 ; 4.0 , 0.593279 , 0.511503 , 0.284545 , 0.339193

Is admissible? True Expected value: 68.3405504757
moe , moe , 79.763438 , 0.179283 ; 4.0 , 0.213952 , 0.982373 , 0.253538 , 0.635217

Is admissible? True Expected value: 68.3405504757
eeny , eeny , 7.431093 , 0.900335 ; 4.0 , 0.637925 , 0.14892 , 0.382864 , 0.092765

Is admissible? True Expected value: 68.3405504757
IMPROVED
NO BFS Improvement!
general , pass , 99.065588 , 0.521137 ; 4.0 , 0.671081 , 0.284618 , 0.665309 , 0.041733

general , pass , 99.065588 , 0.521137 ; 4.0 , 0.671081 , 0.284618 , 0.665309 , 0.041733

general , pass , 99.065588 , 0.521137 ; 4.0 , 0.671081 , 0.284618 , 0.665309 , 0.041733

alan , alan , 71.32961 , 0.930679 ; 4.0 , 0.117261 , 0.181536 , 0.901166 , 0.062637

eeny , eeny , 7.431093 , 0.900335 ; 4.0 , 0.637925 , 0.14892 , 0.382864 , 0.092765

Is admissible? False Expected value: 95.1110554001
BRUTE FORCE
general , pass , 99.065588 , 0.521137 ; 4.0 , 0.671081 , 0.284618 , 0.665309 , 0.041733

moe , moe , 79.763438 , 0.179283 ; 4.0 , 0.213952 , 0.982373 , 0.253538 , 0.635217

steve , pass , 77.528814 , 0.236376 ; 4.0 , 0.458126 , 0.621779 , 0.808786 , 0.65234

alan , alan , 71.32961 , 0.930679 ; 4.0 , 0.117261 , 0.181536 , 0.901166 , 0.062637

miny , miny , 32.163439 , 0.727152 ; 4.0 , 0.271691 , 0.895381 , 0.312952 , 0.962457

Is admissible? False Expected value: 85.5731972994
         147839911 function calls (147839910 primitive calls) in 1191.842 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000 1193.792 1193.792 <string>:1(<module>)
      126    0.000    0.000    0.000    0.000 <string>:2(_parse_args)
       20    0.000    0.000    0.001    0.000 Flight.py:100(toString)
  1310720    1.619    0.000    1.619    0.000 Flight.py:140(getPlacementToken)
  2772675    3.436    0.000    3.436    0.000 Flight.py:143(getFid)
  2772685    3.387    0.000    3.387    0.000 Flight.py:146(getReward)
  2772685    3.138    0.000    3.138    0.000 Flight.py:149(getProbability)
  2772685    3.124    0.000    3.124    0.000 Flight.py:152(getTimeMax)
  1310720    1.467    0.000    1.467    0.000 Flight.py:155(getNoDat)
  2772685    3.239    0.000    3.239    0.000 Flight.py:158(getTimeAverageFailure)
  2772685    3.048    0.000    3.048    0.000 Flight.py:161(getTimeAverageSuccess)
  2772685    3.348    0.000    3.348    0.000 Flight.py:170(getTimeStdDevFailure)
  2772685    3.101    0.000    3.101    0.000 Flight.py:173(getTimeStdDevSuccess)
        3    0.000    0.000    0.000    0.000 Flight.py:206(__eq__)
  1310735    5.712    0.000   53.512    0.000 Flight.py:26(__init__)
  1310720   32.045    0.000   46.821    0.000 Flight.py:35(copy_constructor)
       15    0.000    0.000    0.000    0.000 Flight.py:54(regular_constructor)
      126    0.002    0.000    0.070    0.001 Flight.py:62(isolatedSuccessCDF)
       63    0.002    0.000    0.073    0.001 Flight.py:67(compareTo)
        1    0.032    0.032    0.033    0.033 FlightCombinator.py:10(__init__)
    30241    0.346    0.000    0.458    0.000 FlightCombinator.py:21(has_next)
    30240    0.127    0.000    0.127    0.000 FlightCombinator.py:30(get_next)
   292391    3.324    0.000 1096.334    0.004 FlightPlan.py:108(getExpectedValue)
        8    0.000    0.000    0.032    0.004 FlightPlan.py:122(isAdmissible)
        1    0.000    0.000    0.007    0.007 FlightPlan.py:130(makeAdmissible)
   262142   10.456    0.000   66.284    0.000 FlightPlan.py:136(cloneFlightPlan)
   540127    1.382    0.000    1.792    0.000 FlightPlan.py:149(size)
    23886    0.033    0.000    0.033    0.000 FlightPlan.py:152(getAsList)
        1    0.000    0.000    0.007    0.007 FlightPlan.py:157(insertionSort)
   292386    1.135    0.000    1.135    0.000 FlightPlan.py:16(__init__)
   393210    0.625    0.000    0.625    0.000 FlightPlan.py:169(get)
   393210    0.613    0.000    0.613    0.000 FlightPlan.py:172(set)
   292391   85.138    0.000 1092.784    0.004 FlightPlan.py:61(getExpectedValueCDF)
        2    0.000    0.000    0.001    0.001 FlightPlanCoordinator.py:14(__init__)
    23881    0.677    0.000    2.374    0.000 FlightPlanCoordinator.py:153(subSeqShuffle)
      2/1    0.663    0.331  114.709  114.709 FlightPlanCoordinator.py:165(runBruteForce)
        1    0.000    0.000    0.034    0.034 FlightPlanCoordinator.py:199(ordSplit)
        1    0.000    0.000    0.000    0.000 FlightPlanCoordinator.py:205(<listcomp>)
        1    0.000    0.000    0.034    0.034 FlightPlanCoordinator.py:210(insertionSort)
        2    0.000    0.000    0.001    0.000 FlightPlanCoordinator.py:30(cloneCandidates)
        1    0.000    0.000 1078.972 1078.972 FlightPlanCoordinator.py:73(runSLS)
        1   13.869   13.869 1078.972 1078.972 FlightPlanCoordinator.py:84(sls)
        1    0.000    0.000 1193.792 1193.792 Main.py:22(main)
        1    0.000    0.000    0.000    0.000 Testing.py:15(__init__)
        1    0.001    0.001 1193.792 1193.792 Testing.py:277(runTestZero)
      126    0.000    0.000    0.002    0.000 _continuous_distns.py:135(_cdf)
  1461955   34.789    0.000   48.717    0.000 _continuous_distns.py:2701(_cdf)
  1462081   13.929    0.000   13.929    0.000 _continuous_distns.py:85(_norm_cdf)
  1462081  237.261    0.000  975.510    0.001 _distn_infrastructure.py:1615(cdf)
  1462081   40.140    0.000  402.459    0.000 _distn_infrastructure.py:547(argsreduce)
  1462081   65.203    0.000  256.659    0.000 _distn_infrastructure.py:572(<listcomp>)
  1462081   62.936    0.000   78.279    0.000 _distn_infrastructure.py:758(_argcheck)
  1462081    9.755    0.000   45.873    0.000 _methods.py:31(_any)
        1    0.000    0.000    0.000    0.000 _weakrefset.py:38(_remove)
  5848072   27.175    0.000  111.208    0.000 fromnumeric.py:1281(ravel)
  2924036    7.803    0.000   17.434    0.000 fromnumeric.py:1370(nonzero)
  1462081    3.109    0.000    3.109    0.000 fromnumeric.py:1452(shape)
  1462081   10.826    0.000   84.452    0.000 fromnumeric.py:1762(any)
  2924036    8.710    0.000   24.248    0.000 fromnumeric.py:51(take)
  2924036   38.567    0.000  191.456    0.000 function_base.py:1278(extract)
  4386243   12.116    0.000   43.337    0.000 function_base.py:1326(place)
 13158225   56.997    0.000  150.730    0.000 numeric.py:392(asarray)
  4386117   21.704    0.000   59.251    0.000 numeric.py:462(asanyarray)
   621620    3.871    0.000   10.971    0.000 random.py:170(randrange)
    53799    0.181    0.000    1.114    0.000 random.py:214(randint)
   621620    5.012    0.000    7.100    0.000 random.py:220(_randbelow)
        2    0.000    0.000    0.001    0.001 random.py:84(__init__)
        2    0.000    0.000    0.001    0.001 random.py:93(seed)
  1462081   31.848    0.000  104.327    0.000 shape_base.py:8(atleast_1d)
  4386243   31.222    0.000   31.222    0.000 {built-in method _insert}
       93    0.000    0.000    0.000    0.000 {built-in method abs}
 17544342  131.280    0.000  131.280    0.000 {built-in method array}
        1    0.000    0.000 1193.792 1193.792 {built-in method exec}
    60482    0.066    0.000    0.066    0.000 {built-in method factorial}
        2    0.000    0.000    0.000    0.000 {built-in method from_bytes}
  1462083    1.334    0.000    1.334    0.000 {built-in method isinstance}
  7729214    6.092    0.000    6.092    0.000 {built-in method len}
  2923910    5.548    0.000    5.548    0.000 {built-in method log}
    23886    0.051    0.000    0.051    0.000 {built-in method max}
    23882    0.087    0.000    0.087    0.000 {built-in method min}
  4385865    9.460    0.000    9.460    0.000 {built-in method pow}
       33    0.002    0.000    0.002    0.000 {built-in method print}
  1461955    2.350    0.000    2.350    0.000 {built-in method sqrt}
        2    0.001    0.001    0.001    0.001 {built-in method urandom}
  1462081    6.056    0.000    6.056    0.000 {built-in method zeros}
        2    0.000    0.000    0.000    0.000 {function Random.seed at 0x769ba780}
  1462081    6.877    0.000   52.751    0.000 {method 'any' of 'numpy.ndarray' objects}
  4234774    4.254    0.000    4.254    0.000 {method 'append' of 'list' objects}
   621620    0.570    0.000    0.570    0.000 {method 'bit_length' of 'int' objects}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
        1    0.000    0.000    0.000    0.000 {method 'discard' of 'set' objects}
      254    0.001    0.000    0.001    0.000 {method 'extend' of 'list' objects}
       20    0.001    0.000    0.001    0.000 {method 'format' of 'str' objects}
  1221328    1.518    0.000    1.518    0.000 {method 'getrandbits' of '_random.Random' objects}
  2924036    9.631    0.000    9.631    0.000 {method 'nonzero' of 'numpy.ndarray' objects}
   262141    0.323    0.000    0.323    0.000 {method 'random' of '_random.Random' objects}
  5848072   18.536    0.000   18.536    0.000 {method 'ravel' of 'numpy.ndarray' objects}
  1462081   36.119    0.000   36.119    0.000 {method 'reduce' of 'numpy.ufunc' objects}
        3    0.000    0.000    0.000    0.000 {method 'remove' of 'list' objects}
  2924036   27.677    0.000   27.677    0.000 {method 'reshape' of 'numpy.ndarray' objects}
        2    0.000    0.000    0.000    0.000 {method 'reverse' of 'list' objects}
    23881    0.228    0.000    0.228    0.000 {method 'shuffle' of 'mtrand.RandomState' objects}
  2924036   15.537    0.000   15.537    0.000 {method 'take' of 'numpy.ndarray' objects}
DaviesX commented 8 years ago

Profiler shows 92% of the time (1096.334s) is spent in getExpectedValueCDF, where scipy's CDF calculation takes up 82% of the run time (975.51s), deeming it the main cause of the slowness. Both SLS and Brute Force methods suffer from this computation. An O(1) lookup table is necessary even though we may sacrifice precision for performance trade-off.

zhaonian commented 8 years ago

💯