An optimization technique where function calls are cached to avoid duplicate computations.
6
votes
1answer
90 views
C++: multi-function memoizator and multi-type container
I'm trying to write a multiple functions memoizator, I talked about it here.
The main problem is to create a container containing different and heterogenous functions.
I found a working solution, ...
2
votes
1answer
33 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 ...
3
votes
1answer
561 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 ...
3
votes
1answer
37 views
caching decorator
I came up with a caching decorator for pure functions. Is it ok? Could it be better/simpler/faster?
...
9
votes
3answers
284 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 ...
2
votes
1answer
53 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 ...
3
votes
1answer
144 views
Longest palindromic subsequence by memoization
I've written some code to solve the longest palindromic subsequence problem.
...
5
votes
1answer
434 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 ...
4
votes
2answers
70 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.
...
10
votes
2answers
291 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 ...
7
votes
2answers
227 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 ...
12
votes
1answer
263 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 ...
4
votes
2answers
115 views
5
votes
1answer
48 views
Levenshtein Distance with Haskell Vectors and Memoization
Is the following an effective way to implement the Levenshtein Distance with Haskell vectors?
...
2
votes
1answer
296 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.
...
1
vote
2answers
62 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
...
2
votes
0answers
69 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 ...
2
votes
2answers
2k views
4
votes
1answer
179 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 ...
3
votes
1answer
278 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 ...
4
votes
1answer
312 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
157 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 ...
12
votes
5answers
4k 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.
...
6
votes
1answer
1k views
Memoized Fibonacci
I went ahead and implemented a method to calculate Fibonacci numbers using memoization.
...
4
votes
2answers
154 views
6
votes
1answer
684 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:
...
3
votes
1answer
672 views
Iterative Collatz with memoization
I'm trying to write efficient code for calculating the chain-length of each number.
For example, ...
6
votes
2answers
410 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 ...
6
votes
3answers
205 views
6
votes
1answer
1k 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 ...
2
votes
2answers
921 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
3answers
573 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 ...
12
votes
1answer
520 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:
...
