Is this considered memoisation?

In optimising some code recently, we ended up performing what I think is a "type" of memoisation but I'm not sure we should be calling it that. The pseudo-code below is not the actual algorithm (since we have little need for factorials in our application, and posting said code is a firing offence) but it should be adequate for explaining my question. This was the original:

def factorial (n):
    if n == 1 return 1
    return n * factorial (n-1)

Simple enough, but we added fixed points so that large numbers of calculations could be avoided for larger numbers, something like:

def factorial (n):
    if n == 1 return 1
    if n == 10 return 3628800
    if n == 20 return 2432902008176640000
    if n == 30 return 265252859812191058636308480000000
    if n == 40 return 815915283247897734345611269596115894272000000000
    # And so on.

    return n * factorial (n-1)

This, of course, meant that 12! was calculated as 12 * 11 * 3628800 rather than the less efficient 12 * 11 * 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1.

But I'm wondering whether we should be calling this memoisation since that seems to be defined as remembering past results of calculations and using t开发者_如何学JAVAhem. This is more about hard-coding calculations (not remembering) and using that information.

Is there a proper name for this process or can we claim that memoisation extends back not just to calculations done at run-time but also those done at compile-time and even back to those done in my head before I even start writing the code?

I'd call it pre-calculation rather than memoization. You're not really remembering any of the calculations you've done in the process of calculating a final answer for a given input, rather you're pre-calculating some fixed number of answers for specific inputs. Memoization as I understand it is really more akin to "caching" a set of results as you calculate them for later reuse. If you were to store each value calculated so that you didn't need to recalculate it again later, that would be memoization. Your solution differs in that you never store any "calculated" results from your program, only the fixed points that have been pre-calculated. With memoization if you reran the function with an input different than one of the pre-calculated ones it would not have to recalculate the result, it would simply reuse it.

Whether or not you are hard coding the results in, this is still memoization because you have already calculated results that you are expecting to calculate again. Now this may come in the form of run-time, or compile time.. but either way, it's memoization.

Memoization is done at run-time. You are optimizing at compile time. So, it is not.

See for example ... Wikipedia

Or ...

1. Memoization The term memoization was coined by Donald Michie (1968) to refer to the process by which a function is made to automatically remember the results of previous computations. The idea has become more popular in recent years with the rise of functional languages; Field and Harrison (1988) devote a whole chapter to it. The basic idea is just to keep a table of previously computed input/result pairs.

Peter Norvig University of California (the bold is mine)

Link

def memoisation(f):
    dct = {}
    def myfunction(x):
        if x not in dct:            
            dct[x] = f(x)
        return dct[x]
    return myfunction

@memoisation
def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)

def nb_appels(n):
    if n==0 or n==1:
        return 0
    else:
        return  1 + nb_appels(n-1) + 1 + nb_appels(n-2)


print(fibonacci(13))
print ('nbappel',nb_appels(13))