Online PHP editor | perf for MZN0e

<?php /* Sample Input 100 9999 123456 1000000000 0 Sample Output 21 356 1684 438744 */ // n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34... // opsAddCountDown 0 0 1 0 1 0 2 1 0 2 1.... // opsAddCount 1 2 2 3 3 4 4 4 5 5 5.... // opsAddFut 1 2 2 3 3 4 4 4 5 5 5 6 6 6 6 7 7 7 7 8 8 8 8 9 9 9 9 9 10 10 10 10 10 11... // opsAdd +1 +2 . +2 . +3 . . +3 . . +4 . . . +4 . . . +4 . . . +5 . . . . +5 . . . . +5... // sum 1 3 3 5 5 8 8 8 11 11 11 15 15 15 15 19 19 19 19 23 23 23 23 28 28 28 28 28 33 33 33 33 33 38... // goto n(sum+1) 2 4 6 9 12 16 20 24 29 34 39... /** * * @author Starson Hochschild <starsonh@gmail.com> * */ abstract class golomb { /** * V2 - implement conditional array building and count * * @param int $n * @return NULL|number */ public static function f($n) { $n = (int)$n; if($n < 1) return null; $queueOpsAddCountDown = array(); $ops = 0; $opsAdd = 0; $opsAddCountDown = 0; $opsAddFuture = 0; $opsAddDone = true; $predictSum = true; $sum = 0; $sumFuture = 0; while ($sum < $n) { $opsAddDone = $opsAddCountDown == 0; // If we're done with this $opsAdd increment it, separated from the $opsAddDone block below on purpose if($opsAddDone) { $opsAdd++; } // Cache a future $opsAddCountDown if($predictSum) { $opsAddFuture++; $queueOpsAddCountDown[] = $opsAdd; // See if this will be enough to equal or overtake $n $sumFuture += $opsAddFuture * $opsAdd; $predictSum = $sumFuture < $n; } // If we're done with this $opsAdd grab a new $opsAddCountDown from $listOpsAddCountDown if($opsAddDone) { $opsAddCountDown = array_shift($queueOpsAddCountDown); } // Do the real work $sum += $opsAdd; $ops++; $opsAddCountDown--; } return $ops; } public static function fThisList($listN) { $listN = preg_split("/[\s,]+/", $listN); $fN = array(); foreach($listN as $n) $fN[$n] = self::f($n); return $fN; } } $listN = "1 2 3 4 5 6 7 8 9 10 11 12 100 9999 123456 1000000000 2000000000 2147483647"; $fn = 0; if(isset($_GET["listN"])) { $listN = $_GET["listN"]; $start = microtime(true); $fn = golomb::fThisList($listN); $end = microtime(true); } ?> <html> <head></head> <body> <form action="" method="get"> <i>f(<textarea name="listN" rows="15"><?php echo htmlentities($listN); ?></textarea>)</i><br /> <input type="submit" value="Calculate f(n)" /><br /><br /> <i>f(n) =</i> <pre><?php var_export($fn); ?></pre><br /> <?php if(isset($end)) { ?> Combined processing time: <?php echo $end - $start ?> seconds <?php } ?> </form> This page's source:<br /> <?php htmlentities(highlight_file(__FILE__)); ?> </body> </html> <?php /** * This is here for historical purposes. It shows the progression that lead to the method above. * @author Starson Hochschild <starsonh@gmail.com> * */ abstract class golombArchive { /** * V1.1 - added some memory management * Better, but still takes a lot of memory and crashes on large(r) numbers due to running out of memory * * @param int $n * @return NULL|number */ public static function fWithCleanup($n) { $n = (int)$n; if($n < 1) return null; $listFn = array(); $ops = 0; $sum = 0; for($cn = 0; $sum < $n; $cn++) { if($sum < $cn) { $ops++; $listFn[$cn] = $ops; $sum += $listFn[$ops]; // Cleanup unset($listFn[$ops]); if($ops % 4096 == 0) gc_collect_cycles(); } else { $listFn[$cn] = $ops; } } return $ops; } /** * V1 - a simple, "brute force" type of approach * Takes a lot of memory and crashes on large numbers due to running out of memory * * @param int $n * @return NULL|number */ public static function fBrute($n) { $listFn = array(); $n = (int)$n; if($n < 1) return null; $ops = 0; $sum = 0; for($cn = 0; $sum < $n; $cn++) { if($sum < $cn) { $ops++; $listFn[$cn] = $ops; $sum += $listFn[$ops]; } else { $listFn[$cn] = $ops; } } return $ops; } } ?>

Version	System time (s)	User time (s)	Memory (MiB)
7.2.10	0.205	0.017	14.43
7.2.9	0.195	0.006	14.38
7.2.8	0.233	0.010	14.55
7.2.7	0.202	0.010	14.73
7.2.6	0.197	0.006	14.86
7.2.5	0.190	0.013	14.55
7.2.4	0.176	0.017	14.98
7.2.3	0.162	0.010	15.20
7.2.2	0.159	0.012	14.86
7.2.1	0.032	0.009	14.64
7.2.0	0.096	0.003	15.06
7.1.22	0.196	0.007	13.33
7.1.21	0.191	0.013	13.62
7.1.20	0.215	0.013	13.39
7.1.19	0.245	0.003	13.69
7.1.18	0.200	0.003	13.50
7.1.17	0.209	0.013	13.82
7.1.16	0.207	0.003	13.79
7.1.15	0.160	0.003	13.72
7.1.14	0.156	0.010	13.72
7.1.13	0.167	0.007	13.53
7.1.12	0.070	0.007	13.64
7.1.11	0.212	0.016	13.54
7.1.10	0.132	0.006	13.75
7.1.9	0.041	0.006	13.82
7.1.8	0.023	0.005	13.77
7.1.7	0.183	0.013	13.42
7.1.6	0.103	0.020	31.98
7.1.5	0.115	0.007	32.00
7.1.4	0.046	0.013	31.59
7.1.3	0.066	0.014	31.90
7.1.2	0.174	0.007	32.08
7.1.1	0.117	0.010	13.73
7.1.0	0.173	0.014	13.95
7.0.31	0.180	0.010	13.59
7.0.30	0.179	0.013	13.36
7.0.29	0.215	0.007	13.30
7.0.28	0.377	0.013	13.27
7.0.27	0.179	0.019	13.21
7.0.26	0.017	0.010	13.04
7.0.25	0.038	0.013	13.43
7.0.24	0.031	0.016	13.45
7.0.23	0.182	0.010	13.69
7.0.22	0.028	0.012	13.76
7.0.21	0.029	0.017	13.29
7.0.20	0.013	0.016	13.16
7.0.19	0.060	0.013	13.76
7.0.18	0.161	0.003	13.66
7.0.17	0.197	0.007	13.63
7.0.16	0.130	0.015	13.59
7.0.15	0.040	0.007	13.58
7.0.14	0.159	0.009	13.44
7.0.13	0.074	0.010	13.47
7.0.12	0.085	0.014	13.57
7.0.11	0.090	0.006	13.65
7.0.10	0.140	0.007	13.65
7.0.9	0.043	0.003	13.51
7.0.8	0.023	0.010	13.35
7.0.7	0.038	0.005	13.40
7.0.6	0.022	0.016	13.68
7.0.5	0.026	0.008	13.49
7.0.4	0.017	0.011	13.41
7.0.3	0.022	0.003	13.67
7.0.2	0.075	0.004	13.75
7.0.1	0.140	0.006	13.35
7.0.0	0.114	0.007	13.66
5.6.38	0.008	0.014	14.12
5.6.37	0.008	0.016	14.31
5.6.36	0.022	0.013	14.22
5.6.35	0.017	0.009	13.98
5.6.34	0.019	0.008	14.29
5.6.33	0.019	0.016	14.00
5.6.32	0.024	0.012	14.01
5.6.31	0.009	0.015	14.24
5.6.30	0.017	0.017	14.17
5.6.29	0.017	0.011	14.27
5.6.28	0.019	0.011	14.13
5.6.27	0.018	0.010	14.12
5.6.26	0.015	0.011	14.19
5.6.25	0.021	0.012	14.44
5.6.24	0.022	0.008	14.19
5.6.23	0.015	0.015	14.20
5.6.22	0.018	0.009	14.32
5.6.21	0.006	0.019	14.11
5.6.20	0.028	0.003	14.04
5.6.19	0.018	0.015	14.60
5.6.18	0.015	0.010	14.20
5.6.17	0.015	0.016	14.21
5.6.16	0.021	0.006	14.25
5.6.15	0.025	0.003	14.32
5.6.14	0.018	0.004	13.96
5.6.13	0.021	0.012	14.34
5.6.12	0.008	0.016	14.46
5.6.11	0.013	0.016	14.05
5.6.10	0.014	0.013	13.97
5.6.9	0.021	0.003	13.93
5.6.8	0.017	0.009	14.21
5.6.7	0.017	0.008	14.10
5.6.6	0.018	0.009	13.97
5.6.5	0.031	0.003	14.04
5.6.4	0.016	0.013	14.21
5.6.3	0.019	0.008	14.03
5.6.2	0.019	0.006	14.21
5.5.38	0.011	0.011	12.61
5.5.37	0.015	0.012	12.61
5.5.36	0.017	0.014	12.61
5.5.35	0.019	0.005	12.61
5.5.34	0.015	0.006	12.61
5.5.33	0.009	0.015	12.61
5.5.32	0.013	0.007	12.61
5.5.31	0.008	0.011	12.61
5.5.30	0.012	0.006	12.61
5.5.29	0.013	0.010	12.61
5.5.28	0.010	0.008	12.61
5.5.27	0.022	0.004	12.61
5.5.26	0.017	0.009	12.61
5.5.25	0.017	0.006	12.61
5.5.24	0.005	0.015	12.61
5.5.23	0.016	0.007	12.61
5.5.22	0.012	0.008	12.61
5.5.21	0.008	0.012	12.61
5.5.20	0.014	0.005	12.61
5.5.19	0.013	0.013	12.61
5.4.45	0.008	0.013	12.61
5.4.44	0.011	0.008	12.61
5.4.43	0.018	0.003	12.61
5.4.42	0.015	0.008	12.61
5.4.41	0.008	0.012	12.61
5.4.40	0.015	0.003	12.61
5.4.39	0.015	0.008	12.61
5.4.38	0.011	0.008	12.61
5.4.37	0.014	0.006	12.61
5.4.36	0.019	0.006	12.61
5.4.35	0.017	0.007	12.61

Version

System time (s)

User time (s)

Memory (MiB)

7.2.10

0.205

0.017

14.43

7.2.9

0.195

0.006

14.38

7.2.8

0.233

0.010

14.55

7.2.7

0.202

0.010

14.73

7.2.6

0.197

0.006

14.86

7.2.5

0.190

0.013

14.55

7.2.4

0.176

0.017

14.98

7.2.3

0.162

0.010

15.20

7.2.2

0.159

0.012

14.86

7.2.1

0.032

0.009

14.64

7.2.0

0.096

0.003

15.06

7.1.22

0.196

0.007

13.33

7.1.21

0.191

0.013

13.62

7.1.20

0.215

0.013

13.39

7.1.19

0.245

0.003

13.69

7.1.18

0.200

0.003

13.50

7.1.17

0.209

0.013

13.82

7.1.16

0.207

0.003

13.79

7.1.15

0.160

0.003

13.72

7.1.14

0.156

0.010

13.72

7.1.13

0.167

0.007

13.53

7.1.12

0.070

0.007

13.64

7.1.11

0.212

0.016

13.54

7.1.10

0.132

0.006

13.75

7.1.9

0.041

0.006

13.82

7.1.8

0.023

0.005

13.77

7.1.7

0.183

0.013

13.42

7.1.6

0.103

0.020

31.98

7.1.5

0.115

0.007

32.00

7.1.4

0.046

0.013

31.59

7.1.3

0.066

0.014

31.90

7.1.2

0.174

0.007

32.08

7.1.1

0.117

0.010

13.73

7.1.0

0.173

0.014

13.95

7.0.31

0.180

0.010

13.59

7.0.30

0.179

0.013

13.36

7.0.29

0.215

0.007

13.30

7.0.28

0.377

0.013

13.27

7.0.27

0.179

0.019

13.21

7.0.26

0.017

0.010

13.04

7.0.25

0.038

0.013

13.43

7.0.24

0.031

0.016

13.45

7.0.23

0.182

0.010

13.69

7.0.22

0.028

0.012

13.76

7.0.21

0.029

0.017

13.29

7.0.20

0.013

0.016

13.16

7.0.19

0.060

0.013

13.76

7.0.18

0.161

0.003

13.66

7.0.17

0.197

0.007

13.63

7.0.16

0.130

0.015

13.59

7.0.15

0.040

0.007

13.58

7.0.14

0.159

0.009

13.44

7.0.13

0.074

0.010

13.47

7.0.12

0.085

0.014

13.57

7.0.11

0.090

0.006

13.65

7.0.10

0.140

0.007

13.65

7.0.9

0.043

0.003

13.51

7.0.8

0.023

0.010

13.35

7.0.7

0.038

0.005

13.40

7.0.6

0.022

0.016

13.68

7.0.5

0.026

0.008

13.49

7.0.4

0.017

0.011

13.41

7.0.3

0.022

0.003

13.67

7.0.2

0.075

0.004

13.75

7.0.1

0.140

0.006

13.35

7.0.0

0.114

0.007

13.66

5.6.38

0.008

0.014

14.12

5.6.37

0.008

0.016

14.31

5.6.36

0.022

0.013

14.22

5.6.35

0.017

0.009

13.98

5.6.34

0.019

0.008

14.29

5.6.33

0.019

0.016

14.00

5.6.32

0.024

0.012

14.01

5.6.31

0.009

0.015

14.24

5.6.30

0.017

14.17

5.6.29

0.017

0.011

14.27

5.6.28

0.019

0.011

14.13

5.6.27

0.018

0.010

14.12

5.6.26

0.015

0.011

14.19

5.6.25

0.021

0.012

14.44

5.6.24

0.022

0.008

14.19

5.6.23

0.015

14.20

5.6.22

0.018

0.009

14.32

5.6.21

0.006

0.019

14.11

5.6.20

0.028

0.003

14.04

5.6.19

0.018

0.015

14.60

5.6.18

0.015

0.010

14.20

5.6.17

0.015

0.016

14.21

5.6.16

0.021

0.006

14.25

5.6.15

0.025

0.003

14.32

5.6.14

0.018

0.004

13.96

5.6.13

0.021

0.012

14.34

5.6.12

0.008

0.016

14.46

5.6.11

0.013

0.016

14.05

5.6.10

0.014

0.013

13.97

5.6.9

0.021

0.003

13.93

5.6.8

0.017

0.009

14.21

5.6.7

0.017

0.008

14.10

5.6.6

0.018

0.009

13.97

5.6.5

0.031

0.003

14.04

5.6.4

0.016

0.013

14.21

5.6.3

0.019

0.008

14.03

5.6.2

0.019

0.006

14.21

5.5.38

0.011

12.61

5.5.37

0.015

0.012

12.61

5.5.36

0.017

0.014

12.61

5.5.35

0.019

0.005

12.61

5.5.34

0.015

0.006

12.61

5.5.33

0.009

0.015

12.61

5.5.32

0.013

0.007

12.61

5.5.31

0.008

0.011

12.61

5.5.30

0.012

0.006

12.61

5.5.29

0.013

0.010

12.61

5.5.28

0.010

0.008

12.61

5.5.27

0.022

0.004

12.61

5.5.26

0.017

0.009

12.61

5.5.25

0.017

0.006

12.61

5.5.24

0.005

0.015

12.61

5.5.23

0.016

0.007

12.61

5.5.22

0.012

0.008

12.61

5.5.21

0.008

0.012

12.61

5.5.20

0.014

0.005

12.61

5.5.19

0.013

12.61

5.4.45

0.008

0.013

12.61

5.4.44

0.011

0.008

12.61

5.4.43

0.018

0.003

12.61

5.4.42

0.015

0.008

12.61

5.4.41

0.008

0.012

12.61

5.4.40

0.015

0.003

12.61

5.4.39

0.015

0.008

12.61

5.4.38

0.011

0.008

12.61

5.4.37

0.014

0.006

12.61

5.4.36

0.019

0.006

12.61

5.4.35

0.017

0.007

12.61