3n + 1 问题——引发的缓存思考

Dear 丶 2023-08-17 17:21 53阅读 0赞

# 3n + 1 问题——引发的缓存思考 #

### 文章目录 ###

*  3n + 1 问题——引发的缓存思考
 *  问题描述
 *  方法 1（实时计算）
 *  方法 2（结果缓存）
 *  方法 3（过程缓存）
 *  最后

# 问题描述 #

有这样一个规律：对任意大于 1 的自然数 n，如果 n 为奇数，将其变化为 3n + 1；如果 n 为偶数，将其变化为 n/2。经过若干次变化后，一定会使 n 变为 1。

如果 n = 5：

*  5 -> 16 -> 8 -> 4 -> 2 -> 1

如果 n = 3:

*  3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1

现在，输入一个整数 n，请计算出总的变化次数。例：n = 5，l = 5；n = 3，l = 7。（l 表示变化次数）

# 方法 1（实时计算） #

最简单处理方式是**递归**。由于每一次 n/2 或者 3n-1 操作后，变化次数 l 会加 1，可以得出公式模型为：**f(n) = f(n-1) + 1**。递归函数必须有出口，当 n = 1 时，会进入 1 -> 4 -> 2 -> 1 -> 4 … 这样的死循环。所以**出口条件是 n <= 1**。最终得到代码如下。

size_t solve_3nplus1(size_t n)
    { 
        if (n <= 1)
            return 0;
    
        return solve_3nplus1( (n%2 == 0) ? n/2 : 3*n+1 ) + 1;
    }

使用：

int main()
    { 
        cout << solve_3nplus1(3) << endl;
        cout << solve_3nplus1(5) << endl;
    }
    
    /* 输出：*/
    7
    5

# 方法 2（结果缓存） #

事实上，你会发现 方法1 是一种实时计算。也就是说，第一次 n = 3 的时候，程序会 **3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1**，第二次 n = 3 的时候，程序还是会 **3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1**，于是这中间多了许多重复计算。

提升程序效率的一种、众所周知的方式是**缓存**。常见的缓存处理方式是，在核心处理逻辑（solve\_3nplus1）之上，套一层缓存逻辑（solve\_3nplus1\_cache）。缓存层负责将计算结果保存下来，每次外部接口请求时，缓存层会先去缓存里看看，“我有没有计算过 n = 3 呀”，有就直接将结果返回；没有，那么调用 solve\_3nplus1 计算出结果。向外部返回结果的同时，拷贝一份结果放在缓存里。

完整代码如下：

/* 计算逻辑 */
    size_t solve_3nplus1(size_t n)
    { 
        if (n <= 1)
            return 0;
    
        return solve_3nplus1( (n%2 == 0) ? n/2 : 3*n+1 ) + 1;
    }
    /* 缓存逻辑 */
    size_t solve_3nplus1_cache(vector<size_t>& v, size_t n)
    { 
        size_t l = 0;
        
        /* 避免越界访问 */
        while (n >= v.size()) { 
            n = (n%2 == 0) ? n/2 : 3*n+1;
            ++l;
        }
    
        if (v[n] == 0) { 
            cout << "实时计算... n = " << n << endl;
            v[n] = solve_3nplus1(n);
        }
        else
            cout << "缓存中取得... n = " << n << endl;
    
        return v[n] + l;
    }

用简单的测试用例进行功能测试：

int main()
    { 
        vector<size_t> v(6);
        cout << solve_3nplus1_cache(v, 3) << endl;
        cout << solve_3nplus1_cache(v, 5) << endl;
        cout << solve_3nplus1_cache(v, 3) << endl;
    }
    
    /* 输出：*/
    实时计算... n = 3
    7
    实时计算... n = 5
    5
    缓存中取得... n = 3
    7

瞧上去功能是实现了，但是哪里不对劲。得捋捋：

*  **3 -> 1**变化中，完整过程是：3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1。
 *  **5 -> 1**变化中，完整过程是：5 -> 16 -> 8 -> 4 -> 2 -> 1。

看得出，n = 3 与 n = 5 时有部分是重合的，更准确说，n = 3 包含了 n = 5。结论显而易见：**程序还是在做重复计算**。这是因为，上述代码仅仅对计算结果缓存，而非计算过程。

# 方法 3（过程缓存） #

3n + 1 问题显然是符合过程缓存的，因为过程中产生的数据能够推导出目标结果（这句话会不会太抽象？总之结合 n = 3、n = 5 就能明了许多）。

size_t solve_3nplus1_cache(vector<size_t>& v, size_t n);
    
    size_t solve_3nplus1(vector<size_t>& v, size_t n)
    { 
        v[1] = 1;  /* 设置出口 */
        return solve_3nplus1_cache(v, n) - 1;  /* 由于v[1]=1, 所以最后需要减1 */
    }
    
    size_t solve_3nplus1_cache(vector<size_t>& v, size_t n)
    { 
        size_t l = 0;
        /* 防越界 */
        while (n >= v.size()) { 
            n = (n%2 == 0) ? n/2 : 3*n+1;
            ++l;
        }
    
        if (v[n] == 0)
            v[n] = solve_3nplus1_cache(v, (n%2 == 0) ? n/2 : 3*n+1) + 1;
        else if (n != 1)  /* 避免 n = 1 的影响 */
            cout << "从缓存中取得... n = " << n << endl;
        return v[n] + l;
    }

与 方法2 的不同之处是，方法3 把递归过程中计算出来的所有数据都保存下来，而不是只保留最终结果。

测试代码：

int main()
    { 
        vector<size_t> v(20);
    
        cout << solve_3nplus1(v, 3) << endl;
        cout << solve_3nplus1(v, 5) << endl;
        cout << solve_3nplus1(v, 3) << endl;
    
        cout << "v[i] = ";
        for (int i=0; i<v.size(); ++i) { 
            cout << v[i] << " ";
        }
        cout << endl;
    }
    
    /* 输出：*/
    7
    从缓存中取得... n = 5
    5
    从缓存中取得... n = 3
    7
    v[i] = 0 1 2 8 3 6 0 0 4 0 7 0 0 0 0 0 5 0 0 0
                 *   *

*  **注：容器 v 中存储的次数 l 要比实际值大 1。**

方法3 比 方法2 在缓存上做得更极致。但是不可避免的是，方法3 中，缓存层与业务层基本耦合在一起，代码可阅读性较差。虽说不是不可以优化，但对程序员的编码能力要求更高了。

# 最后 #

3n + 1 问题可以说是一个很简单的问题，但在过程中引发的“缓存”思想却很重要。

—— 其实更像是无聊人的胡思乱想而已！但少闲人如吾一人者耳……