[程序员] 这种需要回顾过去数据的算法问题是不是回溯问题，如何优化速度？

[小天管理]

做外包，最近遇到个异想天开的甲方，想预测彩票数字。该甲方自称潜心研究彩票 30 年，一直手算，现在觉得数据量太大了，想用程序实现。
虽然这个甲方在我看来是异想天开，但是他提出的计算规则倒是没有漏洞，我本着反正只谁出钱谁上帝的原则，实现了出来，但是现在遇到了性能问题。

他的算法并不复杂，首先，甲方提供了 75 个数字字符串，每个字符串都是 4 个数字，诸如 0123 3578 之类的。我在这里称其为样本数据。

彩票的开奖数字，每期都是 5 位数字，它的算法里，把这 5 位数字拆开成 5 个，每个单独去和 75 个样本数据进行计算。

一个样本字符串 + 开奖拆开的数字，会生成一系列值，这些值我接下来会有详述，这就是一行记录(每个生成的值是一列)。

因为有 75 个字符串，所以就有 75 行，于是，一个被拆开的数字，会生成一张表格，这张表格有 75 行。
又因为每期开奖数字是 5 位，所以每期彩票的开奖数字最后都会有 5 张表。

生成值（表格的列）有以下部分：
A1：找上一期的开奖数字，计算上一期的开奖数字是否在对应行样本数据中出现过。
A2：当前开奖数字是否在样本数据中出现过？无论出现还是没出现状态，都从当前这期往之前的开奖记录回溯，如果状态和目前这期一致，就累加数值，直到出现一期和当前这一期不一样的状态，就终止(我大致看了一下平均遍历次数在 5 左右)。
Q15B：从当前期倒退 61 期，然后从此为起点遍历 30 期，只要这 30 期的开奖数字，命中了对应的样本数据，就+1 ，然后获得最终值。如果之前的期数不够，则该数据无效
Q15R：从当前期倒退 31 期，然后从此为起点遍历 30 期，只要这 30 期的开奖数字，命中了对应的样本数据，就+1 ，然后获得最终值。如果之前的期数不够，则该数据无效
P15B：从当前期倒退 16 期，然后从此为起点遍历 15 期，要要这 15 期的开奖数字，命中了对应的样本数据，就+1 ，然后获得最终值。如果之前的期数不够，则该数据无效。
P15R：从当前期倒退 31 期，然后从此为起点遍历 15 期，只要这 15 期的开奖数字，命中了对应的样本数据，就+1 ，然后获得最终值。如果之前的期数不够，则该数据无效，

P15X：把前面的 A1 ，A2 ，Q15B Q15R P15B P15R 以一个简单的排列规则后得到的分类数。
Q15X：就是上一期的 P15X （也就是把上一期的 P15X 算一遍出来，所以如果之前期数不够，那么这个数据算不出来
C618：这是性能罪魁祸首，先不在这里算，问题在下面讲，先跳过。

就此你可以看到，这个过程从 A1 到 P15R 往前遍历了 1 + 5 + 30 +30 + 15 +15 = 96 次。然后为了算出 Q15X ，又来了一遍，所以遍历了 192 次。问题是，这仅仅是一行（因为是和一个样本字符串在对比），而这个表有 75 行，于是这个循环对比的过程执行了 75 x192 = 14400
然后我们每期开奖数字有 5 位，也就是说每期有 5 张这样的表，因此是 14400 x 5 = 72000 次。

这个代码我用的语言是 Java 。循环 72000 次，每一次几乎都进行了对比运算和累加运算，对比运算很简单用的是字符串查找 indexOf 方法。根据我反复测试，程序在预热完毕完毕后，执行上述计算花费时间是 45-50 毫秒。

45-50 毫秒也不算长啊。本来到这里还没太奇葩的，但是接下来甲方就有骚操作想法了。还记得前面写的那个 C618 吗？甲方的意思是，从目前的这期开奖记录开始，往前倒退 618 期，以此为起点，计算从此开始到当期为止（共 617 期）的从 A1 到 Q15X 的全部值。然后把这 617 的 A1 到 Q15X 和当前期的 A1 到 Q15X 按一定规则对比，比中了就累计值。

于是上面那计算一次要 45-50 毫秒的操作，要算 617 次。。。算一次 30 秒就过去了。。。

我想了很久，也没想到该怎么优化这个问题，这妥妥的是 CPU 密集型运算，但是它的算法规则不复杂，甚至可以说相当简单，除了向前追溯的次数太多了之外，整个运算过程几乎的规则就是对比和累计，对比的规则也就是要么查有没有，要么相等不相等。。。

我一度想看看那个 72000 次花费 45-50 毫秒的过程有没有优化的空间，但是看来看去也不知道该优化哪里。
目前我暂时不想考虑换语言之类的手段。

有没有算法大佬来聊聊这个场景该怎么办呢？