python - python 逆科拉兹猜想
问题描述
程序应该做的是采取步骤和一个数字,然后输出你有多少个独特的序列,正好有 xsteps
来创建number
。
有人知道我可以如何节省一些内存吗 - 因为我应该在 4 秒的限制内完成相当大的数字。
def IsaacRule(steps, number):
if number in IsaacRule.numbers:
return 0
else:
IsaacRule.numbers.add(number)
if steps == 0:
return 1
counter = 0
if ((number - 1) / 3) % 2 == 1:
counter += IsaacRule(steps-1, (number - 1) / 3)
if (number * 2) % 2 == 0:
counter += IsaacRule(steps-1, number*2)
return counter
IsaacRule.numbers = set()
print(IsaacRule(6, 2))
如果有人知道带有记忆功能的版本,我将不胜感激,现在它可以工作,但仍有改进的余地。
解决方案
基线:IsaacRule(50, 2)
需要 6.96 秒
0) 使用 LRU 缓存
这使代码花费更长的时间,并给出了不同的最终结果
1)消除if条件:(number * 2) % 2 == 0
toTrue
IsaacRule(50, 2)
耗时 0.679 秒。感谢 Pm2Ring 这个。
((number - 1) / 3) % 2 == 1
2)尽可能简化number % 6 == 4
并使用楼层划分:
IsaacRule(50, 2)
耗时 0.499s
真值表:
| n | n-1 | (n-1)/3 | (n-1)/3 % 2 | ((n-1)/3)%2 == 1 |
|---|-----|---------|-------------|------------------|
| 1 | 0 | 0.00 | 0.00 | FALSE |
| 2 | 1 | 0.33 | 0.33 | FALSE |
| 3 | 2 | 0.67 | 0.67 | FALSE |
| 4 | 3 | 1.00 | 1.00 | TRUE |
| 5 | 4 | 1.33 | 1.33 | FALSE |
| 6 | 5 | 1.67 | 1.67 | FALSE |
| 7 | 6 | 2.00 | 0.00 | FALSE |
代码:
def IsaacRule(steps, number):
if number in IsaacRule.numbers:
return 0
else:
IsaacRule.numbers.add(number)
if steps == 0:
return 1
counter = 0
if number % 6 == 4:
counter += IsaacRule(steps-1, (number - 1) // 3)
counter += IsaacRule(steps-1, number*2)
return counter
3) 使用集合重写代码
IsaacRule(50, 2)
耗时 0.381s
这让我们可以利用为集合所做的任何优化。基本上我在这里进行广度优先搜索。
4)打破循环,这样我们就可以跳过跟踪以前的状态。
IsaacRule(50, 2)
耗时 0.256s
我们只需要添加一个检查number != 1
以打破唯一已知的循环。这可以加快速度,但是如果您从 1 开始,则需要添加一个特殊情况。感谢 Paul 的建议!
START = 2
STEPS = 50
# Special case since we broke the cycle
if START == 1:
START = 2
STEPS -= 1
current_candidates = {START} # set of states that can be reached in `step` steps
for step in range(STEPS):
# Get all states that can be reached from current_candidates
next_candidates = set(number * 2 for number in current_candidates if number != 1) | set((number - 1) // 3 for number in current_candidates if number % 6 == 4)
# Next step of BFS
current_candidates = next_candidates
print(len(next_candidates))
推荐阅读
- swift - 如何使用类方法作为闭包而不在该方法/闭包中持有对 self 的强引用?
- google-maps - 如何修复 Android Studio 中不可转换的类型
- google-app-engine - ffmpeg 无法在谷歌应用引擎标准 nodejs 中正确执行
- ios - iOS 13 - FileManager url(forPublishingUbiquitousItemAt:expiration:) 不再工作
- mongodb - 如何在Mongo中减去两个日期
- python - Boyer moore 算法 - 计算所有匹配的子串
- awk - 合并文件在空字段中打印 0
- android - 如何在firebase中完成搜索,即在每个节点和子节点甚至子节点内(如果可用)
- jekyll - Jekyll 主题是否接收安全更新?
- ethereum - Web3 web3.eth.sendSignedTransaction 无效参数