这是一个创建于 139 天前的主题，其中的信息可能已经有所发展或是发生改变。
做外包，最近遇到个异想天开的甲方，想预测彩票数字。该甲方自称潜心研究彩票 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 毫秒的过程有没有优化的空间，但是看来看去也不知道该优化哪里。
目前我暂时不想考虑换语言之类的手段。
有没有算法大佬来聊聊这个场景该怎么办呢？
虽然这个甲方在我看来是异想天开，但是他提出的计算规则倒是没有漏洞，我本着反正只谁出钱谁上帝的原则，实现了出来，但是现在遇到了性能问题。
他的算法并不复杂，首先，甲方提供了 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 毫秒的过程有没有优化的空间，但是看来看去也不知道该优化哪里。
目前我暂时不想考虑换语言之类的手段。
有没有算法大佬来聊聊这个场景该怎么办呢？
15 条回复 • 2024-07-07 09:05:07 +08:00
 |
1
seers 139 天前 via iPhone
落库，空间换时间
|
 |
2
phrack 139 天前 via iPhone
不玩彩票的我根本看不懂。不是每一期开奖都是随机摇的数字吗？看以前的数据有什么用啊？
|
 |
3
52boobs 139 天前 via Android
常见几个优化思路，并行多线程，优化算法或简化模型来减少计算量，寻找合适的数据结构并存储有用的信息。你看着点用就是了。
|
 |
4
wxf666 139 天前
1. 以前算过的数据，为何要再算呢？
比如 Q15X ，直接拿上一期的 P15X 不行吗？为啥还要再遍历 96 次？ 再如 C618 ，之前 617 次的 A1 ，……，Q15X ，不是算出来了吗？直接用可以吗？ 2. 循环搜字符串 7W 次，就耗时 50 毫秒，是不是有点慢了？ 比如 Everything 正则搜几百万文件，基本都是按个键下去，就搜出来有多少结果了？ 3. 感觉你这堆描述，有耐心看的人不多。 你若放代码（关键算法你换个等慢的） + 数据，问为啥这么慢，应该会有大佬帮你调调看看？  |
 |
5
Juszoe 139 天前
从产品角度考虑，30 秒和 1 秒对客户的区别大吗？从描述来看，每期只会计算 1 次？
值得你花大代价来优化吗？如果你单纯当作算法题来做，那是挺好的。 我想到一个最简单的方案，是预先把这 618 期算好入库，以后每期增量入库一遍，计算 C618 的所需要的 A1 到 Q15X 直接就有了，用不着复杂的优化。 |
 |
6
abcbuzhiming OP |
|
7
abcbuzhiming OP @Juszoe 其实这是我自己在考虑要不要进行优化，客户那边，还没有进一步反馈。
它这个东西，不单单是算 618 期这么简单，是用户点击任意一期，你都得拿到这一期前 618 期的数据。 预先算题是不行的，因为历史记录已经高达 6935 期。要把这么多期都算出来，那可要不少时间。 可能上面有个人说的落盘是正道，我现在也想干脆把计算和展示分开算了，用户想重新算就点计算按钮然后等时间，平时就是展示历史数据，切换的也快 |
|
8
wxf666 139 天前
@abcbuzhiming #6
1. 存历史 A1 、……、C618 数据，有啥不好吗？ - 数据太大？ 每期 1KB ，1W 期也才 10MB 呀？ - 计算太慢？ 存历史后，每期只需 30 毫秒（ Q15X 节省 3.6W 次计算，C618 节省 4442W 次计算）， 1W 期只需 5 分钟呀？ - 附带 MySQL 太麻烦？ 带个 SQLite 单文件呗？这货才 1MB 。。 2. Everything 也是 for 循环遍历 file list 吧？ 否则《正则》搜索全部文件，能怎么《特化场景》呢？ |
|
9
Juszoe 139 天前
@abcbuzhiming #7
>> 用户点击任意一期，你都得拿到这一期前 618 期的数据。 我明白，但是直接拿历史数据的速度，好过重新再把前 618 期算出来吧，再结合这堆数据把当期一算就完事了。 你刚刚又提到一个展示历史数据的需求，那入库就是最合适的方案嘛。 |
 |
10
yidinghe 139 天前
这个。。。你看看能不能用 SQL 写。
|
 |
11
clf 139 天前
入库呀。难道彩票历史的数据还能变不成？
|
 |
12
NoOneNoBody 139 天前
java 不懂，但这个用 pandas 很容易写，性能的话，因为都是纯数字，可以用 numba 优化
A1,A2,Q15B Q15R P15B P15R 这些，只要当期结果出来，就可以计算，然后作为当期数据的附加字段一并存入数据库，以后就只是读取而已 现在就是不知道这个 C618 要算多复杂，反正从次数上看，计算量其实很少，而且是可以并发的 如果 C618 对每期来说也是定值的话，就是第 C618[n+1]计算出来后，C618[n]还是不变，那这个 C618 也是可以入库的，以后无需计算 基本上 pandas rolling 就可以 |
 |
13
lesismal 139 天前
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 期、计算每期时，把上述过程中建表的只需要删除临界的一期、加入需要的一期，所以这个过程中不需要重复建整个表，只是滚动删、增一期，整个流程的建表开销不需要太大 我不了解实际需求，以上仅供参考 |
 |
14
Sawyerhou 139 天前 via Android
换语言，落库，并发都是可行性很高的方法。
如果实在不愿意，那就试试 java 的矩阵库，比如 Joinery(不保证好用，得看文档确认一下)。 Q15B 循环就可替换为 sum(df[31:60]==x)， C618 也可类似优化。 纯循环没有索引和矩阵计算，优化起来不太容易， 手撸轮子也可，但不太有必要。 |
Select Language