今天读到一篇论文:
奥尼尔,梅丽莎·E.,“正版
埃拉托斯特尼筛法”, http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf杂志
函数式编程,已出版
剑桥大学出版社在线
2008 年 10 月 9 日
doi:10.1017/S0956796808007004。
它描述了一种使用优先级队列生成素数的算法:
sieve [] = []
sieve (x:xs) = x : sieve' xs (insertprime x xs PQ.empty)
where
insertprime p xs table = PQ.insert (p*p) (map (* p) xs) table
sieve' [] table = []
sieve' (x:xs) table
| nextComposite <= x = sieve' xs (adjust table)
| otherwise = x : sieve' xs (insertprime x xs table)
where
nextComposite = PQ.minKey table
adjust table
| n <= x = adjust (PQ.deleteMinAndInsert n' ns table)
| otherwise = table
where
(n, n':ns) = PQ.minKeyValue table
primes = sieve [2 .. ]
该算法乍一看似乎是正确的,但我不明白一件事:
它使用的 PQ 如何处理重复的最小优先级?
我手工做了一些模拟,发现可能会导致错误。
如果有人能解释一下,我将不胜感激您的帮助!
论文中这样描述了正在使用的优先级队列:
鉴于这些需求,优先级队列
是一个有吸引力的选择,特别是因为该数据结构本身支持多个
具有相同优先级的项目(按任意顺序出队)。
由于重复条目在算法中并不是真正有用,因此必须对其进行特殊处理。
The adjust
删除最小组合的函数不断调整优先级队列,直到可以确定最小元素的所有重复项都被删除:
adjust table
| n <= x = adjust (PQ.deleteMinAndInsert n_ ns table)
| otherwise = table
where ...
如果当前第一个元素(n
) 小到足以被删除,调整再次调用自身以检查剩余队列中的下一个元素。只有当没有剩余小元素时,它才会停止递归。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)