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

[abcbuzhiming]

做外包，最近遇到个异想天开的甲方，想预测彩票数字。该甲方自称潜心研究彩票 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 毫秒的过程有没有优化的空间，但是看来看去也不知道该优化哪里。
目前我暂时不想考虑换语言之类的手段。

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

[seers]

落库，空间换时间

[phrack]

不玩彩票的我根本看不懂。不是每一期开奖都是随机摇的数字吗？看以前的数据有什么用啊？

[52boobs]

常见几个优化思路，并行多线程，优化算法或简化模型来减少计算量，寻找合适的数据结构并存储有用的信息。你看着点用就是了。

[wxf666]

1. 以前算过的数据，为何要再算呢？

比如 Q15X ，直接拿上一期的 P15X 不行吗？为啥还要再遍历 96 次？

再如 C618 ，之前 617 次的 A1 ，……，Q15X ，不是算出来了吗？直接用可以吗？


2. 循环搜字符串 7W 次，就耗时 50 毫秒，是不是有点慢了？

比如 Everything 正则搜几百万文件，基本都是按个键下去，就搜出来有多少结果了？


3. 感觉你这堆描述，有耐心看的人不多。

你若放代码（关键算法你换个等慢的） + 数据，问为啥这么慢，应该会有大佬帮你调调看看？

[Juszoe]

从产品角度考虑，30 秒和 1 秒对客户的区别大吗？从描述来看，每期只会计算 1 次？

值得你花大代价来优化吗？如果你单纯当作算法题来做，那是挺好的。

我想到一个最简单的方案，是预先把这 618 期算好入库，以后每期增量入库一遍，计算 C618 的所需要的 A1 到 Q15X 直接就有了，用不着复杂的优化。

[abcbuzhiming]

@phrack 这位甲方自认为能从以前的数据里找到规律，所以他设计的算法有大量从以前的数据里追溯的


@wxf666
1.目前并没有“以前算过”这个概念，因为并没有把历史数据存盘，每次都是针对某一期开始算

2.循环搜 7w 次耗时 50ms ，我也觉得这有点慢，但是我现在实在想不出该优化哪里，对比字符串就是 "xxxx".indexof("xxxx")。并没有特别用什么，
EveryThing 啥的应该是用 C++的吧，它那应该是某种特化场景，我估计我肯定比不了。因为我这里面有大量 for 循环遍历 list ，

[abcbuzhiming]

@Juszoe 其实这是我自己在考虑要不要进行优化，客户那边，还没有进一步反馈。

它这个东西，不单单是算 618 期这么简单，是用户点击任意一期，你都得拿到这一期前 618 期的数据。

预先算题是不行的，因为历史记录已经高达 6935 期。要把这么多期都算出来，那可要不少时间。

可能上面有个人说的落盘是正道，我现在也想干脆把计算和展示分开算了，用户想重新算就点计算按钮然后等时间，平时就是展示历史数据，切换的也快

[wxf666]

@abcbuzhiming #6

1. 存历史 A1 、……、C618 数据，有啥不好吗？

- 数据太大？

每期 1KB ，1W 期也才 10MB 呀？

- 计算太慢？

存历史后，每期只需 30 毫秒（ Q15X 节省 3.6W 次计算，C618 节省 4442W 次计算），

1W 期只需 5 分钟呀？

- 附带 MySQL 太麻烦？

带个 SQLite 单文件呗？这货才 1MB 。。


2. Everything 也是 for 循环遍历 file list 吧？

否则《正则》搜索全部文件，能怎么《特化场景》呢？

[Juszoe]

@abcbuzhiming #7
>> 用户点击任意一期，你都得拿到这一期前 618 期的数据。
我明白，但是直接拿历史数据的速度，好过重新再把前 618 期算出来吧，再结合这堆数据把当期一算就完事了。
你刚刚又提到一个展示历史数据的需求，那入库就是最合适的方案嘛。

[yidinghe]

这个。。。你看看能不能用 SQL 写。

[clf]

入库呀。难道彩票历史的数据还能变不成？

[NoOneNoBody]

java 不懂，但这个用 pandas 很容易写，性能的话，因为都是纯数字，可以用 numba 优化

A1,A2,Q15B Q15R P15B P15R 这些，只要当期结果出来，就可以计算，然后作为当期数据的附加字段一并存入数据库，以后就只是读取而已
现在就是不知道这个 C618 要算多复杂，反正从次数上看，计算量其实很少，而且是可以并发的
如果 C618 对每期来说也是定值的话，就是第 C618[n+1]计算出来后，C618[n]还是不变，那这个 C618 也是可以入库的，以后无需计算

基本上 pandas rolling 就可以

[lesismal]

A1 这种直接查 map 就行了，无需遍历

### 查表法
1. A2 这种涉及顺序的，可以使用查表的方法：
开奖结果的 hash 值作为 mapA 的 key ，因为是 5 个数字而且彩票这种数字通常不大，一个 uint64 甚至 uint32 就足够做 hash 值了。每个奖期信息作为 value 并且排序后的数组作为 map 的 value 。如果用 c++，multimap 内部红黑树自动就是排好序的，不需要自己排序数组之类的

假设不同的下标为 targetIndex=0, 然后就只要查 map hash 值得到相同的、如果不等于 targetIndex 就找 targetIndex=当前 index+1 并查找下一个 hash 相同的。当然，如果遍历平均为 5 、开销也不大, 那这种可能不划算、根据实际测试情况、可以考虑就用遍历

2. Q15B/Q15R/P15B/P15R 这些，都可以用对应期段的数据建各自对应的表，然后直接查表就能计算出 key 对应的 value 数量，不需要遍历几十期、匹配上则+1 的方式去计算

这个过程中只建表一次，然后上面的 1/2/3 都是直接查 map 就出结果了

### C618
建表的过程可以同时根据期号做倒排索引，C618 回退 618 期、计算每期时，把上述过程中建表的只需要删除临界的一期、加入需要的一期，所以这个过程中不需要重复建整个表，只是滚动删、增一期，整个流程的建表开销不需要太大


我不了解实际需求，以上仅供参考

[Sawyerhou]

换语言，落库，并发都是可行性很高的方法。

如果实在不愿意，那就试试 java 的矩阵库，比如 Joinery(不保证好用，得看文档确认一下)。

Q15B 循环就可替换为 sum(df[31:60]==x)，
C618 也可类似优化。

纯循环没有索引和矩阵计算，优化起来不太容易，
手撸轮子也可，但不太有必要。

[Sawyerhou]

@Sawyerhou ps ，彩票预测估计是意义不大，

如果庄家不作弊，那么完全随机情况下预测不可能。
如果庄家作弊，他挑没人买或自己人买的号开奖，预测更不可能。