首届NoCOUG国际SQL挑战赛

〇〇 · 发表于 2025-5-10 20:57

其实就是多项式乘法
face_value就是次数，概率就是系数。
扔2次，就是多项式的平方，3次就是立方...,新的次数就是face_value点数之和,对应的系数就是这个点数之和的概率
用numpy验证

import numpy as np
p1 = np.poly1d([1/4, 0,1/4,1/4,1/12,1/12,0,1/12])
print ("P1 : ", p1)
mul = np.polymul(p1, p1)
print("\n\npoly1D object : ")
print("squre Result : \n", mul)
mul = np.polymul(mul, p1)
print("\n\npoly1D object : ")
print("cube Result : \n", mul)

复制代码

输出

P1 : 7 5 4 3 2
0.25 x + 0.25 x + 0.25 x + 0.08333 x + 0.08333 x + 0.08333
poly1D object :
square Result :
14 12 11 10 9 8
0.0625 x + 0.125 x + 0.125 x + 0.1042 x + 0.1667 x + 0.1042 x
7 6 5 4 3 2
+ 0.125 x + 0.04861 x + 0.05556 x + 0.04861 x + 0.01389 x + 0.01389 x + 0.006944
poly1D object :
cube Result :
21 19 18 17 16
0.01562 x + 0.04688 x + 0.04688 x + 0.0625 x + 0.1094 x
15 14 13 12 11
+ 0.09375 x + 0.125 x + 0.09896 x + 0.1042 x + 0.08854 x
10 9 8 7 6
+ 0.05729 x + 0.05787 x + 0.03299 x + 0.02778 x + 0.01273 x
5 4 3 2
+ 0.008681 x + 0.006944 x + 0.001736 x + 0.001736 x + 0.0005787

复制代码

下面是sql计算的

SELECT face_value, SUM (probability) AS probability
FROM
(
SELECT
d1.face_value + d2.face_value AS face_value,
d1.probability * d2.probability AS probability
FROM die d1 CROSS JOIN die d2
)
GROUP BY face_value
┌────────────┬──────────────────────┐
│ face_value │ probability │
│ int32 │ double │
├────────────┼──────────────────────┤
│ 2 │ 0.0625 │
│ 4 │ 0.125 │
│ 5 │ 0.125 │
│ 6 │ 0.1041666679084301 │
│ 7 │ 0.1666666679084301 │
│ 8 │ 0.1041666679084301 │
│ 9 │ 0.1250000037252903 │
│ 10 │ 0.048611112870275974 │
│ 11 │ 0.05555555783212185 │
│ 12 │ 0.048611112870275974 │
│ 13 │ 0.01388888992369175 │
│ 14 │ 0.01388888992369175 │
│ 16 │ 0.006944444961845875 │
├────────────┴──────────────────────┤
│ 13 rows 2 columns │
└───────────────────────────────────┘

复制代码

〇〇 · 发表于 2025-5-10 21:02

本帖最后由〇〇于 2025-5-10 21:11 编辑

因为numpy多项式是x从7次到0次高到低排列，比原式1-8少1，所以平方算出来的值比sql少2，从14次到0次，用16-次数就是sql的面值，原式系数刚好是左右对称，所以从前往后看对应系数就可以了。

既然是多项式乘法，用FFT就容易想到了，https://zhuanlan.zhihu.com/p/76622485

〇〇 · 发表于 2025-5-10 21:39

本帖最后由〇〇于 2025-5-10 21:44 编辑

新版的numpy有多项式乘方的函数，直接用，注意x次数是从右向左的看的，不管算扔300次还是3000次都很快

from numpy.polynomial import polynomial as P
d=[1/12, 0,1/12,1/12,1/4,1/4,0,1/4]
>>> P.polypow(d, 2)
array([0.00694444, 0. , 0.01388889, 0.01388889, 0.04861111,
0.05555556, 0.04861111, 0.125 , 0.10416667, 0.16666667,
0.10416667, 0.125 , 0.125 , 0. , 0.0625 ])
>>> P.polypow(d, 3)
array([0.0005787 , 0. , 0.00173611, 0.00173611, 0.00694444,
0.00868056, 0.01273148, 0.02777778, 0.03298611, 0.05787037,
0.05729167, 0.08854167, 0.10416667, 0.09895833, 0.125 ,
0.09375 , 0.109375 , 0.0625 , 0.046875 , 0.046875 ,
0. , 0.015625 ])
>>> import time
>>> t=time.time();r=P.polypow(d, 300);print(len(r),time.time()-t)
2** 0.001355886459350586
>>> t=time.time();r=P.polypow(d, 3000);print(len(r),time.time()-t)
21001 0.038218021392822266

复制代码

〇〇 · 发表于 2025-5-12 10:57

不用FFT，用快速幂算法也能提高一些效率，这就是原帖中出题者的解法，矩阵相乘，7次=4次+2次+1次，把连接次数按二进制位分解。

以下是Qwen 3按照我的提示给出的结果

import numpy as np
def poly_pow(poly, power):
"""
使用快速幂算法计算多项式的N次幂。
参数:
poly (array-like): 输入多项式，按升幂排列的系数列表或数组。
power (int): 非负整数，要计算的幂次。
返回:
result (np.ndarray): 结果多项式系数数组。
"""
result = np.array([1]) # 初始化为常数项 1（即多项式 1）
current = np.array(poly, dtype=float)
while power > 0:
if power % 2 == 1:
result = np.polymul(result, current) # result *= current
current = np.polymul(current, current) # current ^= 2
power //= 2
return result
# 示例用法：
if __name__ == "__main__":
poly = [1, 2] # 表示 1 + 2x
n = 5
res = poly_pow(poly, n)
print("结果多项式系数:", res)

复制代码

我测试了poly_pow，和polynomial.polypow速度差不多

〇〇 · 发表于 2025-5-12 15:30

无意中发现，newkid在《剑破冰山》一书中期待的写法在duckdb v1.1.3中已经实现了,这里用3E0代替了绑定变量:N

WITH recursive t(v,p,lvl) AS (
SELECT face_value v
,probability p
,1
FROM die
UNION ALL
SELECT d.face_value + t.v ---- 第N次投掷，面值为前N-1次的各种结果加上die表的六种可能面值
,SUM(d.probability * t.p) ---- 把相同的总面值的概率加起来
,MAX(t.lvl)+1
FROM die d,t
WHERE t.lvl<3E0
GROUP BY d.face_value + t.v ---- 按照总面值分组聚合，再做下一次递归
)
SELECT *
FROM t
WHERE lvl = 3E0;
┌───────┬───────────────────────┬───────┐
│ v │ p │ lvl │
│ int32 │ double │ int32 │
├───────┼───────────────────────┼───────┤
│ 10 │ 0.12499999999999999 │ 3 │
│ 18 │ 0.012731481481481479 │ 3 │
│ 15 │ 0.057870370370370364 │ 3 │
│ 11 │ 0.09895833333333333 │ 3 │
│ 16 │ 0.032986111111111105 │ 3 │
│ 22 │ 0.001736111111111111 │ 3 │
│ 5 │ 0.046875 │ 3 │
│ 17 │ 0.027777777777777776 │ 3 │
│ 9 │ 0.09375 │ 3 │
│ 14 │ 0.05729166666666666 │ 3 │
│ 24 │ 0.0005787037037037037 │ 3 │
│ 7 │ 0.0625 │ 3 │
│ 13 │ 0.08854166666666667 │ 3 │
│ 8 │ 0.10937499999999999 │ 3 │
│ 19 │ 0.008680555555555556 │ 3 │
│ 12 │ 0.10416666666666667 │ 3 │
│ 6 │ 0.046875 │ 3 │
│ 3 │ 0.015625 │ 3 │
│ 20 │ 0.006944444444444443 │ 3 │
│ 21 │ 0.001736111111111111 │ 3 │
├───────┴───────────────────────┴───────┤
│ 20 rows 3 columns │
└───────────────────────────────────────┘

复制代码

〇〇 · 发表于 2025-5-12 19:56

用快速幂法写了个双重递归，N=100和newkid的单次递归也差不多快，更多就精度不足了，全显示0

with recursive
t(v,p,lvl)AS materialized (
SELECT face_value v
,probability p
,1
FROM die
UNION ALL
SELECT d.v + t.v ---- 第N次投掷，面值为前N-1次的各种结果加上die表的六种可能面值
,SUM(d.p * t.p) ---- 把相同的总面值的概率加起来
,MAX(t.lvl)*2
FROM t d,t
WHERE t.lvl<100
GROUP BY d.v + t.v ---- 按照总面值分组聚合，再做下一次递归
),t1 as materialized (select *,dense_rank()over(order by lvl)rk from t where lvl & 100<>0)
, t2(v, p, rk) as materialized (select 0 v, 1::double p, 0 rk
union all
select t1.v + t2.v, sum(t1.p * t2.p),max(t1.rk)from t1,t2 where t1.rk=t2.rk+1 GROUP BY t1.v + t2.v)
select v,p from t2 where rk=(select max(rk) from t2)
order by 1;
│ 797 │ 1.207467347241364e-106 │
│ 798 │ 1.207467347241364e-106 │
│ 800 │ 1.207467347241364e-108 │
├───────┴─────────────────────────┤
│ 699 rows (40 shown) 2 columns │
└─────────────────────────────────┘
Run Time (s): real 0.050 user 0.046875 sys 0.000000
WITH recursive t(v,p,lvl) AS (
SELECT face_value v
,probability p
,1
FROM die
UNION ALL
SELECT d.face_value + t.v ---- 第N次投掷，面值为前N-1次的各种结果加上die表的六种可能面值
,SUM(d.probability * t.p) ---- 把相同的总面值的概率加起来
,MAX(t.lvl)+1
FROM die d,t
WHERE t.lvl<100
GROUP BY d.face_value + t.v ---- 按照总面值分组聚合，再做下一次递归
)
SELECT *
FROM t
WHERE lvl = 100
order by 1;
│ 797 │ 1.2074673472413608e-106 │ 100 │
│ 798 │ 1.2074673472413608e-106 │ 100 │
│ 800 │ 1.2074673472413604e-108 │ 100 │
├───────┴─────────────────────────┴───────┤
│ 699 rows (40 shown) 3 columns │
└─────────────────────────────────────────┘
Run Time (s): real 0.103 user 0.203125 sys 0.000000

复制代码

newkid · 发表于 2025-5-12 23:53

你还在玩这个？我记得用11g的递归SQL就可以高效解决了。

newkid · 发表于 2025-5-12 23:59

刚刚才看到你有几个帖子被审核。
Oracle的递归SQL不能用聚合，但是允许用分析函数，所以可以变通实现。

〇〇 · 发表于 2025-5-13 06:10

newkid 发表于 2025-5-12 23:59
刚刚才看到你有几个帖子被审核。Oracle的递归SQL不能用聚合，但是允许用分析函数，所以可以变通实现。

对，我记得后来挖雷还是什么题目中你用了。
写书的时候还不行

回到文档看看递归WITH的限制。文档中说，递归成员不可以包含以下元素：
1. DISTINCT 关键字或 GROUP BY 子句
2. model 子句
3. 聚合函数。而分析函数允许在SELECT中使用。
4. 引用了当前query_name的子查询
5. 把当前query_name作为右边的外连接。
1和3其实是一回事。这个限制使得我们无法在递归过程中通过聚合减少中间结果。限制3说可以用分析函数，但实际的试验结果会报错：
WITH t(n) AS (
SELECT 1 FROM DUAL
UNION ALL
SELECT 1+MAX(n) OVER() FROM t
WHERE n<3
)
SELECT * FROM t;
SELECT * FROM t
*
ERROR at line 7:
ORA-32486: unsupported operation in recursive branch of recursive WITH clause
限制4造成的后果是：如果我已经找到了一个答案，无法告诉ORACLE停止遍历其他的枝条。
我期望的写法是：
WITH t(...) AS (
SELECT ...
UNION ALL
SELECT ...
FROM t,...
WHERE ... AND NOT EXISTS (SELECT 1 FROM t WHERE 找到答案的条件) --- 这个子查询不允许出现t
如果哪一天这些限制能够去除，这个递归WITH功能将会好玩很多。
限制5说不可以用于外连接，但是我试了一下并不报错：

复制代码

〇〇 · 发表于 2025-5-13 09:25

oracle 19c 递归with 还是那么多限制，
https://docs.oracle.com/en/datab ... 6142A51C6__I2077142
连mysql有的方面都比他限制少
https://docs.oracle.com/cd/E17952_01/mysql-8.0-en/with.html

oracle 19c用分析函数，N=30还可以，300就算不动了，可能要加提示

SQL> WITH t(v,p,lvl,rn) AS (
SELECT face_value v
,probability p
,1
,1
FROM die
UNION ALL
SELECT d.face_value + t.v ---- 第N次投掷，面值为前N-1次的各种结果加上die表的六种可能面值
,SUM(d.probability * t.p)over(partition BY d.face_value + t.v) ---- 把相同的总面值的概率加起来
,(t.lvl)+1 ,row_number()over(partition BY d.face_value + t.v order by 1)
FROM die d,t
WHERE t.lvl<30 and t.rn=1
---- 按照总面值分组聚合，再做下一次递归
)
select count(*) from(
SELECT v,sum(p)p
FROM t
WHERE lvl = 30 and rn=1
group by v)
; 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
COUNT(*)
----------
209
Elapsed: 00:00:00.49
------N=300
ERROR at line 20:
ORA-0**3: user requested cancel of current operation
Elapsed: 00:00:22.09

复制代码