Created
April 19, 2014 11:13
-
-
Save jacklynrose/11081403 to your computer and use it in GitHub Desktop.
Fast and memory efficient fib calculation based off Ray Hightower's memoization method but with better memory usage (http://rayhightower.com/blog/2014/04/12/recursion-and-memoization/)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| # Fibonacci numbers WITH memoization. | |
| # Initialize the memoization hash. | |
| @scratchpad = {} | |
| @max_fibo_size = 1_000_000_000_000 | |
| # Calculate the nth Fibonacci number, f(n). | |
| def fibo (n) | |
| val = if n <= 1 | |
| n | |
| elsif @scratchpad[n] != nil | |
| @scratchpad[n] | |
| else | |
| @scratchpad[n] = fibo(n-1) + fibo(n-2) | |
| end | |
| val | |
| end | |
| start = last_time = Time.now | |
| puts "%-13s | %-20s | %21s | %21s" % ['fib(n)', 'fib(n) length', '"lap" time', 'total time'] | |
| # Display the Fibonacci sequence. | |
| (1..@max_fibo_size).each do |number| | |
| result = fibo(number) | |
| if number % 100_000 == 0 | |
| puts "%-13d | %-20d | %21.10f | %21.10f" % [number, result.to_s.length, Time.now - last_time, Time.now - start] | |
| last_time = Time.now | |
| end | |
| # memory cleaning | |
| clean_count = 1000 | |
| if number % (clean_count || 50) == 0 | |
| @scratchpad.delete_if do |k, v| | |
| k < (number - 10) | |
| end | |
| clean_count -= 100 | |
| GC.start | |
| end | |
| end |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| On a Macbook Air, 1.6GHz i5, 4GB 1333 MHz DDR3, these were the results, keep in mind memory usage was only jumping up and down by about 100MB at the later points. Adding memory tracking to the results might be a nice addition, but I wasn't too fussed. | |
| fib(n) | fib(n) length | "lap" time | total time | |
| 100000 | 20899 | 0.6711800000 | 0.6712200000 | |
| 200000 | 41798 | 1.4236230000 | 2.0949410000 | |
| 300000 | 62696 | 2.2117460000 | 4.3067670000 | |
| 400000 | 83595 | 2.9075600000 | 7.2143990000 | |
| 500000 | 104494 | 3.5052390000 | 10.7197010000 | |
| 600000 | 125393 | 4.1065500000 | 14.8263210000 | |
| 700000 | 146291 | 4.8694530000 | 19.6958440000 | |
| 800000 | 167190 | 5.3894240000 | 25.0853370000 | |
| 900000 | 188089 | 6.1762100000 | 31.2616150000 | |
| 1000000 | 208988 | 7.0838860000 | 38.3455770000 | |
| 1100000 | 229887 | 7.9771220000 | 46.3227930000 | |
| 1200000 | 250785 | 8.8556020000 | 55.1784660000 | |
| 1300000 | 271684 | 9.2819300000 | 64.4604660000 | |
| 1400000 | 292583 | 10.0042190000 | 74.4647550000 | |
| 1500000 | 313482 | 11.4200230000 | 85.8848490000 | |
| 1600000 | 334380 | 19.7896170000 | 105.6745440000 | |
| 1700000 | 355279 | 19.8605040000 | 125.5351180000 | |
| 1800000 | 376178 | 22.9959830000 | 148.5311730000 | |
| 1900000 | 397077 | 24.2299470000 | 172.7611940000 | |
| 2000000 | 417975 | 26.8378020000 | 199.5990870000 | |
| 2100000 | 438874 | 25.9927830000 | 225.5919420000 | |
| 2200000 | 459773 | 28.4008180000 | 253.9928330000 | |
| 2300000 | 480672 | 28.7940970000 | 282.7870010000 | |
| 2400000 | 501570 | 29.2828760000 | 312.0699450000 | |
| 2500000 | 522469 | 32.9236840000 | 344.9937040000 | |
| 2600000 | 543368 | 33.4547460000 | 378.4485200000 | |
| 2700000 | 564267 | 31.9239960000 | 410.3725900000 | |
| 2800000 | 585166 | 32.2382960000 | 442.6109560000 | |
| 2900000 | 606064 | 34.0890400000 | 476.7000750000 | |
| 3000000 | 626963 | 36.3909580000 | 513.0911050000 | |
| 3100000 | 647862 | 36.6725440000 | 549.7637230000 | |
| 3200000 | 668761 | 38.9875430000 | 588.7513370000 | |
| 3300000 | 689659 | 40.2937750000 | 629.0451820000 | |
| 3400000 | 710558 | 41.4298560000 | 670.4751090000 | |
| 3500000 | 731457 | 41.3124930000 | 711.7876710000 | |
| 3600000 | 752356 | 42.1188530000 | 753.9065960000 | |
| 3700000 | 773254 | 54.8486630000 | 808.7553630000 | |
| 3800000 | 794153 | 44.3187000000 | 853.0741450000 | |
| 3900000 | 815052 | 45.8851530000 | 898.9593740000 | |
| 4000000 | 835951 | 48.5969450000 | 947.5564010000 | |
| 4100000 | 856849 | 48.7242510000 | 996.2807220000 | |
| 4200000 | 877748 | 49.3997300000 | 1045.6805220000 | |
| 4300000 | 898647 | 51.3350000000 | 1097.0155950000 | |
| 4400000 | 919546 | 52.5409690000 | 1149.5566320000 | |
| 4500000 | 940445 | 55.9916640000 | 1205.5483690000 | |
| 4600000 | 961343 | 55.5529590000 | 1261.1014000000 | |
| 4700000 | 982242 | 57.2026100000 | 1318.3040800000 | |
| 4800000 | 1003141 | 58.9713320000 | 1377.2754830000 | |
| 4900000 | 1024040 | 61.1155080000 | 1438.3910620000 | |
| 5000000 | 1044938 | 61.7297210000 | 1500.1208540000 | |
| 5100000 | 1065837 | 64.2228450000 | 1564.3437700000 | |
| 5200000 | 1086736 | 64.6556510000 | 1628.9994910000 | |
| 5300000 | 1107635 | 66.8015300000 | 1695.8010930000 | |
| 5400000 | 1128533 | 69.5491380000 | 1765.3503060000 | |
| 5500000 | 1149432 | 69.4005440000 | 1834.7509270000 | |
| 5600000 | 1170331 | 70.8520690000 | 1905.6030670000 | |
| 5700000 | 1191230 | 72.3932810000 | 1977.9964120000 | |
| 5800000 | 1212128 | 84.2181280000 | 2062.2146400000 | |
| 5900000 | 1233027 | 76.2510680000 | 2138.4657960000 | |
| 6000000 | 1253926 | 76.7570620000 | 2215.2229310000 | |
| 6100000 | 1274825 | 79.2525720000 | 2294.4755860000 | |
| 6200000 | 1295724 | 81.8460140000 | 2376.3216700000 | |
| 6300000 | 1316622 | 82.7099670000 | 2459.0317080000 | |
| 6400000 | 1337521 | 84.5187850000 | 2543.5505610000 | |
| 6500000 | 1358420 | 98.7259780000 | 2642.2766110000 | |
| 6600000 | 1379319 | 90.5337290000 | 2732.8104110000 | |
| 6700000 | 1400217 | 90.1910050000 | 2823.0014820000 | |
| 6800000 | 1421116 | 91.9817880000 | 2914.9833400000 | |
| 6900000 | 1442015 | 94.2419230000 | 3009.2253310000 | |
| 7000000 | 1462914 | 95.6597320000 | 3104.8851310000 | |
| 7100000 | 1483812 | 98.0150460000 | 3202.9002490000 | |
| 7200000 | 1504711 | 100.1612910000 | 3303.0616100000 | |
| 7300000 | 1525610 | 101.9747080000 | 3405.0363880000 | |
| 7400000 | 1546509 | 105.3058710000 | 3510.3423290000 | |
| 7500000 | 1567407 | 108.3341190000 | 3618.6765170000 | |
| 7600000 | 1588306 | 108.2226030000 | 3726.8991920000 | |
| 7700000 | 1609205 | 112.2643650000 | 3839.1636280000 | |
| 7800000 | 1630104 | 113.8652030000 | 3953.0289040000 | |
| 7900000 | 1651003 | 114.3012260000 | 4067.3302010000 | |
| 8000000 | 1671901 | 116.6008800000 | 4183.9311540000 | |
| 8100000 | 1692800 | 118.7781360000 | 4302.7093620000 | |
| 8200000 | 1713699 | 125.6885380000 | 4428.3979960000 | |
| 8300000 | 1734598 | 122.3463940000 | 4550.7444710000 | |
| 8400000 | 1755496 | 123.2608760000 | 4674.0054180000 | |
| 8500000 | 1776395 | 125.7767000000 | 4799.7821940000 | |
| 8600000 | 1797294 | 127.3217620000 | 4927.1040290000 | |
| 8700000 | 1818193 | 142.6963930000 | 5069.8004940000 | |
| 8800000 | 1839091 | 132.3448160000 | 5202.1453780000 | |
| 8900000 | 1859990 | 133.2586150000 | 5335.4040650000 | |
| 9000000 | 1880889 | 136.1275600000 | 5471.5316960000 | |
| 9100000 | 1901788 | 138.3854740000 | 5609.9172390000 | |
| 9200000 | 1922686 | 142.0560960000 | 5751.9734060000 | |
| 9300000 | 1943585 | 141.8788880000 | 5893.8523640000 | |
| 9400000 | 1964484 | 146.2905230000 | 6040.1429640000 | |
| 9500000 | 1985383 | 146.7824960000 | 6186.9255500000 | |
| 9600000 | 2006281 | 162.3883820000 | 6349.3140780000 | |
| 9700000 | 2027180 | 150.6406610000 | 6499.9548210000 | |
| 9800000 | 2048079 | 153.8561580000 | 6653.8110510000 | |
| 9900000 | 2068978 | 160.3674650000 | 6814.1786170000 | |
| 10000000 | 2089877 | 160.3539200000 | 6974.5326280000 | |
| 10100000 | 2110775 | 162.2257630000 | 7136.7584650000 | |
| 10200000 | 2131674 | 164.3632040000 | 7301.1217580000 | |
| 10300000 | 2152573 | 166.8829970000 | 7468.0048250000 | |
| 10400000 | 2173472 | 168.9921220000 | 7636.9970190000 | |
| 10500000 | 2194370 | 171.4993070000 | 7808.4963980000 | |
| 10600000 | 2215269 | 173.7570950000 | 7982.2535640000 | |
| 10700000 | 2236168 | 178.8824420000 | 8161.1360770000 | |
| 10800000 | 2257067 | 180.7242680000 | 8341.8604150000 | |
| 10900000 | 2277965 | 182.5922110000 | 8524.4526970000 | |
| 11000000 | 2298864 | 195.5978760000 | 8720.0506720000 | |
| 11100000 | 2319763 | 188.2496670000 | 8908.3004290000 | |
| 11200000 | 2340662 | 190.7901160000 | 9099.0906840000 | |
| 11300000 | 2361560 | 204.8128880000 | 9303.9036460000 | |
| 11400000 | 2382459 | 195.9118340000 | 9499.8155450000 | |
| 11500000 | 2403358 | 198.6109950000 | 9698.4266120000 | |
| 11600000 | 2424257 | 213.9461940000 | 9912.3729000000 | |
| 11700000 | 2445156 | 205.6800740000 | 10118.0530590000 | |
| 11800000 | 2466054 | 209.0088840000 | 10327.0620200000 | |
| 11900000 | 2486953 | 209.8021410000 | 10536.8642350000 | |
| 12000000 | 2507852 | 212.4198570000 | 10749.2841650000 | |
| 12100000 | 2528751 | 215.9069340000 | 10965.1911730000 | |
| 12200000 | 2549649 | 220.5192050000 | 11185.7104510000 | |
| 12300000 | 2570548 | 221.5003700000 | 11407.2108940000 | |
| 12400000 | 2591447 | 229.7355600000 | 11636.9465260000 | |
| 12500000 | 2612346 | 228.4625590000 | 11865.4091610000 | |
| 12600000 | 2633244 | 230.4370730000 | 12095.8463020000 | |
| 12700000 | 2654143 | 233.2925230000 | 12329.1388980000 | |
| 12800000 | 2675042 | 236.7446300000 | 12565.8836000000 | |
| 12900000 | 2695941 | 242.4511330000 | 12808.3349150000 | |
| 13000000 | 2716839 | 243.2051090000 | 13051.5402250000 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment