Tag Info

Hot answers tagged memoization

17

A few things: Naming: It's neither Fibonaci, nor febonani, nor fibonanci it's fibonacci. Please get your names to reflect what you're actually talking about and not some disfigured mutation of it :( memoized OTOH is a relatively nice name, I'd probably prefer memoizedFibonacciNumbers, but that's a thing of preference Calculating: quoting wikipedia: ...

14

No, not $O(n)$. Not even close. I'll get back to this later though. First, the code: It's a little difficult to tell what your loop logic is. curr is getting incremented each time, but i isn't... whereas typically we'd use i as a loop index. I'd propose using i as the loop index, and then keeping a humble number count named count (or num_humbles or ...

9

Thanks to an answer to a similar question on StackOverflow (thanks @200_success), I improved the implementation of operator(). Using _memory.count is pretty inefficient compared to _memory.find since the latter will stop once the first corresponding key is found: auto operator()(Args... args) -> Ret { const auto t_args = std::make_tuple(args...); ...

8

This method is 'off': private static boolean isInFibonacciList(final int number) { return (number <= FIBONACCI_LIST.size() - 1); } That should probably be: private static boolean isInFibonacciList(final int number) { return number < FIBONACCI_LIST.size(); } which begs the question as to why the function is needed at all. Just have number &...

8

@Vogel612 has already mentioned all major defects and areas of improvement in your code. I want to talk about one more thing: Your package naming is horrible. You are using com.java.fib, please do not ever do that again, because: Although Java classes are prefixed with java.*, it still creates confusion as people might think this is a library class. In ...

7

Memoizing a generator is a good idea to save having to rerun it. There are a few ways to do it - one is to handle it the way you're handling it, by returning the cached result if it exists, otherwise returning and caching the new result. The first way, is to the the tee() method from itertools. Such as follows: from itertools import tee def run(): ...

7

Naming self.retry_times You retry retry_times - 1 times, in all your loops. Consider renaming this or removing the - 1's to make it more understandable. forget This remembers, always. It just doesn't lookup. Consider using a temporary variable or renaming this. RetryTypes This is a constant, not a class. This should be RETRY_TYPES. PEP8 Lines are to be ...

7

Regarding the memoization, here are two different ways to do this (for single-valued functions): import functools def memoize(func): cache = func.cache = {} @functools.wraps(func) def wrapper(n): if n not in cache: cache[n] = func(n) return cache[n] return wrapper def memodict(f): """ Memoization decorator ...

6

I don't know what's up with the spacing in the docstring, but fix it. Your memoize_all doesn't work with everything: memoize_all(int)(1) #>>> Traceback (most recent call last): #>>> ... #>>> AttributeError: type object 'int' has no attribute 'func_code' I suppose this doesn't bother you much, but it irks me ;). Consider for ...

6

Not much to say: your code works as advertised, code is readable, formatting is consistent. Things that could be better though: don't use raw arrays with new unless you absolutely have to. Prefer std::vector, it has a nice interface and manages its own memory. It also has a constructor that lets you fill it with a given value. std::vector<int> cache(...

6

This Code Review, so let us review your code, before proceeding to questions and optimisations. Code and style review Choose better names – According to python style guide, PEP8, you should use snake_case for variables and functions. In addition what does dp, acc stand for? And in general one should avoid single letter variables except in tight loops ...

6

It doesn't use 300 megabytes of heap, it peaks at a little over 20 megabytes. Total allocation is not peak allocation and Haskell has cheap short-lived allocations so total alloc isn't always a good heuristic for GC time or steady-state heap usage. The heap profiling stuff is giving data designed for tuning code rather than for analytics and total alloc is ...

6

You can achieve comparable performance without resorting to mutable state by using IntMap and carefully avoiding unnecessary computations. Let's start with the code below, which is actually the very first Haskell solution at your Pentagonal Number Theorem link: import Data.IntMap ((!), fromList, insert, findWithDefault) partition :: Int -> Integer ...

6

This looks very slick! I've tried it on a few things, and it speeds up very slow commands quite a bit. Less-slow commands, as you've noticed, are still a bit expensive. A few preliminary thoughts (I'll likely add more to this post as I spend more time looking at this): The largest lag time in reading from the cache in a given shell is the time spent ...

5

Class names should be nouns. I'd rename DoubleCheck to DoubleCheckedResource or something similar. ForgettableMemoizingSupplier should not allow null suppliers. You should check that and throw a NullPointerException. The name of the invalid method in the DoubleCheck class is ambiguous. Does it invalidate something or does it check that something is valid or ...

5

1. Review There's no docstring. What does memoize do, and how do I use it? The code uses str(args) + str(kwargs) as the cache key. But this means that, for example, the number 1 and the string "1" will collide. The code is not portable to Python 3, where there's no thread module. It's not clear to me why functools is only imported inside memoize, but ...

5

I'd say the main issue with your code is that you're confusing what the inner function is supposed to do: def inner(W, sol): if W == 0: return sol ## return result so far? if W in d: return d[W] ## return best result for W? Those are two different kinds of values. If you're just returning "smallest tuple for weight W", then W ==...

5

The review by Zac B is very nice, I have only minor comments on top of that about the implementation. Large scripts in here-documents Escaping \$ in large here-documents is troublesome and error prone. Indeed you forgot to escape something here, I let you spot it now ;-) local found=$(find "/tmp/._cache" \ -path "$cachepath/exit" -...

5

There's no reason to ascribe a type to memo. Don't expose the memoization logic outside the call. Instead, create a shim function that creates the memoization vector for you. You can then define the memoized function inside the shim function, preventing people from accidentally calling it. Since the memo variable isn't used after the top-most recursive call, ...

5

Why would you do such a thing? I understand that you wrote the Arithmetic Expression Compiler, and perhaps want to show it off. But who would ever want to write a function as simple as a Fibonacci sequence generater using three programming languages (AEC, Intel assembly, and C++) mixed together, and type way more code than it would take in either C++ or even ...

4

For generic memoization I pretty much always use scalaz Memo but when I compute sequences, I personally prefer using the standard Scala Stream. Stream naturally memoize every computed value. Your solution could be refactored as: lazy val fib = { def f(a: Int, b: Int): Stream[Int] = a #:: f(b, a + b) f(0, 1) } scala> fib.take(10) foreach println 0 ...

4

I don't like the fact that an enumeration with three elements has two named TRUE and FALSE. It sound like the enumeration is simply a boolean, and a third element is not expected. I think they should be called NEVER and ALWAYS or something similar. Those names allude to a possibility of more elements. The RetryType enum is actually not intuitive at all. ...

4

An easy way to detect a cycle is through the implementation of a disjoint set structure, sometimes called a Union-Find structure. You start with a source node and attempt to add a node to that set. If your Find() call for the source node and the other node returns the same root node, then a cycle world result if the nodes are unioned. UPDATE: You ...

4

1. Review There are no docstrings. What do these functions do? How do I call them? What do they return? The function odd_numbers_from could be implemented using itertools.count, like this: def odd_numbers_from(n): """Generate the odd numbers greater than or equal to n.""" return itertools.count(n + 1 - (n % 2), 2) But if you started with ...

4

Using the Python call stack to remember your state is very convenient and often results in shorter code, but it has a disadvantage: >>> collatz(5**38) Traceback (most recent call last): File "<stdin>", line 1, in <module> File "cr24195.py", line 3, in collatz d[n] = collatz(n * 3 + 1 if n & 1 else n/2) + 1 [... many lines ...

4

Well overall impression is the code is very condensed. Some white space may help. I am going to have to disagree with @vnp about the type names. Its pretty common to use short template type names. Common conventions T generic type C container K key, F functor. If you have a lot then fine you may give more description but the type should be generic. I don't ...

4

The simplistic answer, possibly not the most efficient answer, is simply to build a tuple result of the length, and the string, and then memoize that one. When trying with longer strings, it turns out that your version of the recursive version from the link is not complete. You didn't handle the len(s) == 2 case which led to index errors. With that fixed, ...

4

You could use an explicit memoizer rather than incorporating caching into your function. This will make your function easier to understand. You can use functools lru_cache if you are using Python3. You should evaluate based on truth, rather than length. len(s1) == 0 is 'bad'. You can use a turnery operator to reduce the repetition of your code. Your else can ...

4

I believe that might be too much stuff happening here, with a sole purpose of solving a rather simple problem: "I need an in-memory cache". The .NET standard library already has a cache class (System.Runtime.Caching.MemoryCache), so the only reason why you would want to replace it is if you tested it and found out that is doesn't fit your needs for certain ...

3

Template parameters are not informative. Better do something like #define Maptype typename #define Keytype typename #define Function typename template <Maptype M, Keytype K, Function F> I was seriously confused with fun. Better call it function. The code failed to compile on my system (GCC 4.7.3). First, auto function was missing a trailing return ...

Only top voted, non community-wiki answers of a minimum length are eligible