C/C++ 使用 memoization 优化算法

memoization 是一种缓存计算结果,避免重复计算,用空间换时间的优化方式。

以常见的斐波那契数列计算为例:

#include <stdio.h>

#define COUNT_TIMES 10

int fib(int n)
{
    if (n == 0 || n == 1)
    {
        return 1;
    }
    else
    {
        return fib(n - 2) + fib(n - 1);
    }
}

int main()
{
    int i;
    for (i = 0; i < COUNT_TIMES; i++)
        printf("fib %dn", fib(i));
}

输出:

fib 1
fib 1
fib 2
fib 3
fib 5
fib 8
fib 13
fib 21
fib 34
fib 55

实际上,我们来看看其中的计算次数

#include <stdio.h>

#define COUNT_TIMES 10

int count;

int fib(int n)
{
    if (n == 0 || n == 1)
    {
        return 1;
    }
    else
    {
        count++;
        return fib(n - 2) + fib(n - 1);
    }
}

int main()
{
    int i, *mem;

    for (i = 0; i < COUNT_TIMES; i++)
    {
        printf("n %d 结果 %2d 计算次数 %dn", i, fib(i), count);
        count = 0;
    }
}

结果:

n 0 结果  1 计算次数 0
n 1 结果  1 计算次数 0
n 2 结果  2 计算次数 1
n 3 结果  3 计算次数 2
n 4 结果  5 计算次数 4
n 5 结果  8 计算次数 7
n 6 结果 13 计算次数 12
n 7 结果 21 计算次数 20
n 8 结果 34 计算次数 33
n 9 结果 55 计算次数 54

我们发现实际上计算的次数跟其结果相当,计算 n 的斐波那契数列其计算量就是 fib(n) – 1 次了。想想也是醉了。

那么让我们使用 memoization 来优化一下:

#include <stdio.h>
#include <stdlib.h>

#define COUNT_TIMES 10

int count;

int fib(int n, int *mem)
{
    // 如果没有缓存结果则进行计算,并把结果加入到缓存中
    if (mem[n] == -1)
    {
        mem[n] = fib(n - 1, mem) + fib(n - 2, mem);
        // 统计计算次数
        count++;
    }
    // 返回缓存结果
    return mem[n];
}

int main()
{
    int i, j, *mem;
    for (i = 0; i < COUNT_TIMES; i++)
    {
        // 申请一块内存来缓存结果
        mem = (int *)malloc(sizeof(int) * COUNT_TIMES);
        // 初始化其中的结果
        mem[0] = mem[1] = 1;
        for (j = 2; j < COUNT_TIMES; j++)
            mem[j] = -1;

        // 调用计算
        printf("n %d 结果 %2d 计算次数 %dn", i, fib(i, mem), count);

        count = 0; // 计算次数清零
        free(mem); // 释放用来缓存的内存
    }
}

优化之后,可以发现时间复杂度很轻松的变成 O(n) 了

n 0 结果  1 计算次数 0
n 1 结果  1 计算次数 0
n 2 结果  2 计算次数 1
n 3 结果  3 计算次数 2
n 4 结果  5 计算次数 3
n 5 结果  8 计算次数 4
n 6 结果 13 计算次数 5
n 7 结果 21 计算次数 6
n 8 结果 34 计算次数 7
n 9 结果 55 计算次数 8

优化之后,当 n = 15,速度大概是原版的1000倍,当 n = 27 速度大概是原来的 10000 倍了。应该说重复计算的计算量越大使用 memoization 获得的效果就越明显,不过实际应用中要考虑到其所消耗的内存是否值得,也就是看一个性价比吧。

最后去掉注释简单封装一下。

#include <stdio.h>
#include <stdlib.h>

#define COUNT_TIMES 10

int * init_mem() {
    int i, *mem;
    mem = (int *)malloc(sizeof(int) * COUNT_TIMES);
    mem[0] = mem[1] = 1;
    for (i = 2; i < COUNT_TIMES; i++)
        mem[i] = -1;
    return mem;
}

int fib(int n, int *mem)
{
    if (mem[n] == -1)
        mem[n] = fib(n - 1, mem) + fib(n - 2, mem);
    return mem[n];
}

int main()
{
    int i, *mem;

    for (i = 0; i < COUNT_TIMES; i++)
    {
        mem = init_mem();
        printf("fib %dn", fib(i, mem));
        free(mem);
    }
}

Advertisements

2 thoughts on “C/C++ 使用 memoization 优化算法

  1. 还留着递归调用吗?把递归调用也去掉,改成下面循环递推是不是还能省掉很多调用开销呢?
    mem[0] = mem[1] = 1;
    for (i = 2; i < COUNT_TIMES; i++)
    mem[i] =men[i-1]+mem[i-2];

发表评论

Fill in your details below or click an icon to log in:

WordPress.com 徽标

You are commenting using your WordPress.com account. Log Out /  更改 )

Google+ photo

You are commenting using your Google+ account. Log Out /  更改 )

Twitter picture

You are commenting using your Twitter account. Log Out /  更改 )

Facebook photo

You are commenting using your Facebook account. Log Out /  更改 )

Connecting to %s