An optimization technique where function calls are cached to avoid duplicate computations.
12
votes
5answers
5k views
Dynamic programming with Fibonacci
I have written the following code using a dynamic programming technique. Can I use ArrayList here? Please let me know if I can improve this code.
...
12
votes
1answer
548 views
Utility functions for supporting memoization for functions
I've got a couple of utility functions to support memoization for functions with anywhere between 0 to 8 arguments:
...
12
votes
1answer
416 views
Detecting cycles in a directed graph without using mutable sets of nodes
I recently came across the classic algorithm for detecting cycles in a directed graph using recursive DFS. This implementation makes use of a stack to track nodes currently being visited and an extra ...
11
votes
2answers
402 views
Memoizing decorator that can retry
I have some tasks that I'd like to memoize because they connect to a rather slow network and have to wait for the data. Unfortunately this network can be a little finnicky and we get occasional ...
9
votes
3answers
500 views
Find the Nth number divisible by only 2,3,5, or 7
I recently participated in a small friendly competition and this was one of the questions:
A number whose only prime factors are 2, 3, 5 or 7 is called a humble
number. The first 20 humble ...
7
votes
2answers
362 views
Thread-safe memoizer
I have searched around but I was not able to find a complete implementation of the memoize pattern in a multithreaded context. It's the first time playing with thread synchronization. The code seems ...
7
votes
2answers
451 views
Helper class to memoize DateFormats application-wide
Premise
Consider the following method:
static String formatMyDate(Date date) {
return new SimpleDateFormat("yyyy-MM-dd").format(date);
}
It's often ...
7
votes
1answer
2k views
Ability to forget the memoized supplier value
Guava has a feature request which is asking to provide the ability to forget memoized value on a given supplier.
On top on that I needed another functionality where if during the calculation of ...
7
votes
0answers
137 views
Multi-function memoizator and multi-type container
I'm trying to write a multiple functions memoizator, which I've talked about here. The main problem is creating a container containing different and heterogenous functions.
I found a working solution,...
6
votes
1answer
2k views
Memoized Fibonacci
I went ahead and implemented a method to calculate Fibonacci numbers using memoization.
...
6
votes
1answer
2k views
Recursive Memoized Fibonacci in C++
I was reading an article on Wikipedia about memoization, so I wanted to try and apply it. I am fairly new to this subject, so I thought I'd start small. Does the program use memoization correctly? Is ...
6
votes
1answer
763 views
Generic pure functions memoization
I like to create tools for memoization since it can sometimes be useful. I recently created a generic tool for memoizing the results of pure functions.
Here is an example of how it works:
...
6
votes
3answers
279 views
6
votes
1answer
42 views
Locating the largest Collatz Sequence with memoization
Inspired by this question I wrote a memoized form of the collatz sequence calculator.
The idea was to cache the sequence lengths for as many sequences as possible, from 0 to some value. I managed to (...
5
votes
2answers
135 views
Calculating the count of integer partitions of a number (uses stateful vectors internally)
I've written a Haskell function to count the number of partitions of an integer - it's basically an implementation of the same algorithm as this one, using Euler's Pentagonal Number Theorem:
$$P(n) = ...
5
votes
2answers
170 views
5
votes
3answers
87 views
Memoizing decorator with retries, part 2
A while ago I asked this question Memoizing decorator that can retry and then promptly forgot about it. I more recently saw Python decorator for retrying w/exponential backoff and wanted to add ...
5
votes
1answer
59 views
Levenshtein Distance with Haskell Vectors and Memoization
Is the following an effective way to implement the Levenshtein Distance with Haskell vectors?
...
4
votes
2answers
433 views
Memoization with factorial in Python
I wrote a Python module to learn about memoization, and I have some questions on what I did.
How pythonic is this?
Does it make a difference if I used a class attribute instead of a function ...
4
votes
1answer
628 views
Memoized Collatz sequence
Here is one of my programs that utilized memoization and array to improve performance and memory usage. The performance seems satisfactory but the memory usage is ridiculous and I can't figure out ...
4
votes
2answers
115 views
Memoized implementation of change-making algorithm
Recently, I wrote a simple program to solve the change-making problem. Rather than the tabular dynamic programming solution (described in the link), I tried to write a solution that uses memoization.
...
4
votes
2answers
199 views
4
votes
1answer
257 views
Universal memoization decorator
I've just written a simple caching / memoization python decorator. It's purpose is to cache what the function returns for all the arguments combinations it's been ever invoked with.
So, if, say, we ...
4
votes
1answer
320 views
Longest palindromic subsequence by memoization
I've written some code to solve the longest palindromic subsequence problem.
...
4
votes
1answer
528 views
Python caching generator
Is this the correct way to cache a generator in Python, without iterating over it right away (for example using list() over it)?
...
4
votes
1answer
90 views
Multiplying two- or three-dimensional arrays with broadcasting
Background
Disclaimer: Skip if you are not interested in the background. The code is far far simpler than this.
The problem is more about programming than math. Here is the definition of ...
4
votes
1answer
186 views
Comparison of Fibonacci (Multinacci) Functions in Python3
After coming up with a formula on this Stack Overflow question, defeating recursion limits and finding a few new ways of calculating these numbers (as per this Stack Overflow question), I decided that ...
3
votes
1answer
1k views
Iterative Collatz with memoization
I'm trying to write efficient code for calculating the chain-length of each number.
For example, ...
3
votes
1answer
45 views
caching decorator
I came up with a caching decorator for pure functions. Is it ok? Could it be better/simpler/faster?
...
3
votes
1answer
345 views
Google CodeJam Round D APAC Test
Problem A:
Vincenzo decides to make cube IV but only has the budget to make a square maze. Its a perfect maze, every room is in the form of a square and there are 4 doors (1 on each side of the ...
2
votes
2answers
992 views
Python memoization decorator
I have spent all night whipping up this recipe. It's my first Python decorator. I feel like I have a full understanding of how decorators work now and I think I came up with a good object-oriented ...
2
votes
1answer
183 views
Implementation of Longest Common Subsequence
So I implemented the LCS algorithm once using a 2-D matrix to store values while the other one used a python dictionary. I found the dictionary implementation was easier to implement and was a more ...
2
votes
2answers
2k views
2
votes
1answer
526 views
Memoization of Fibonacci using generic Int => Int helper
I'm trying to understand memoization using Scala. I took the Fibonacci sequence as an example because of the high cost of recursively computing numbers in the sequence without memoization.
...
2
votes
3answers
633 views
Memoization-based puzzle solution - sums in a triangle
I am trying to solve a problem at Codechef. As I am new to programming, I am not familiar with dynamic programming. However, I do know the basics of recursion and memoization. Hence I implemented a ...
2
votes
1answer
47 views
Memoization via template
This is kind of follow up of this question on stack overflow...
I wrote the following to utilize memoization for functions that take a single parameter and return a value:
...
2
votes
1answer
51 views
Find offset that minimizes squared difference between two vectors of different size
I am working on a project where the hotspot is some code that is supposed to find an offset, such that the squared differences between a reference vector and a given vector becomes minimal. The core ...
2
votes
2answers
34 views
Memoizing decorator with retries - now with backoff added! (Part 3)
A continuation of Memoizing decorator with retries, part 2, and related to http://codereview.stackexchange.com/a/133493/47529. I liked my decorator before, but especially in my original use case of a ...
2
votes
1answer
49 views
Optimally allocating a resource with time-varying demand and cost
I'm working on the following DP which finds the optimal way to allocate a resource. At each time step I can either allocate (0.2 resources) at cost C or not in which case the storage is reduced by the ...
2
votes
0answers
70 views
Making a default value a property
I recently asked a question on StackOverflow, looking for a way to more easily turn a class attribute into a @property, but only if no other value has been provided ...
1
vote
1answer
37 views
Binary Option Pricing using Card Game
I shuffle a deck of cards(with an equal number of red and black
cards) and start dealing them face up.
After any card you can say “stop”, at which point I pay you $1 for
every red card dealt and ...
1
vote
2answers
85 views
Lazy properties for the angle and length of a line segment
The code below shows the pattern I use to manage properties in my classes when I have the following requirements:
Some properties are slow to calculate and are rarely used, so I want them to be lazy
...
