英文:
Collatz Sequence in Python. Any improvements?
问题
我在Python编程方面相对新手,这是我在Stack Overflow上的第一篇帖子。有人能告诉我这段代码是否对Python中的Collatz序列足够健壮吗?谢谢
英文:
I am relatively new in programming in Python and this is my fist post in Stack Overflow. Can someone tell me if this code is full proof for Collatz Sequence in Python. Thanks
def collatz(number):
while True:
if number % 2 == 0:
number = number // 2
else:
number = 3 * number + 1
print(number)
if number == 1:
break
while True:
try:
number = int(input("Enter a positive non-zero integer: "))
if number <= 0:
print("Please enter a positive non-zero integer.")
else:
collatz(number)
break
except ValueError:
print("Please enter a valid integer.")
To check I have tried with negative integer, 0 and 1 and string as an input.
答案1
得分: 1
一些建议。
首先,你应该意识到,通过尝试很多起始数字并展示每个数字最终都能达到1,你永远无法证明(所有起始数字最终都会达到1)。你只能获得一个强烈的期望,它确实对所有正整数成立。
你可能想返回输入达到1所需的步骤数。
然后,你可以打印[collatz(k) for k in range(20)]
来检查它是否正常工作。
如果一切都好,你可能想尝试计时[collatz(k) for k in range(10_000)]
,这样你可以调整算法以提高速度(如果你愿意)。
我会将核心代码写得更像:
def collatz(k: int):
assert k > 0
counter = 0
while k != 1:
k = k // 2 if k % 2 == 0 else 3 * k + 1
counter += 1
return counter
最后,你可能有兴趣使用类似numba
的东西来实现大幅度(>>100x)的加速。你会从中学到一个东西,即Python不适用于紧密的低级循环。当你执行u += 1
时,背后发生了很多事情。如果你用C语言写相同的代码,你会注意到极大的性能差异。像numba
这样的技术可以实现接近于C语言的速度。
英文:
A few tips.
Firstly, you should realize that you'll never achieve a proof (that all starting numbers eventually reach 1) by trying a lot of starting numbers and showing that each reaches 1. You'll simply achieve a strong expectation that it does indeed hold true for all positive integers.
You may want to return the number of steps taken for an input to reach 1.
Then you can print [collatz(k) for k in range(20)]
to check that it's working.
If all good so far, you may want to try timing [collatz(k) for k in range(10_000)]
, which would let you tweak the algo for speed (if you like).
I'd write the core code more like:
def collatz(k:Int):
assert k > 0
counter = 0
while k != 1:
k = k // 2 if k % 2 == 0 else 3 * k + 1
counter += 1
return counter
Finally you might be interested to use something like numba
to achive a massive (>>100x) speedup. One thing you'll learn from this is that Python is not geared towards tight low-level looping. A lot is happening behind the scenes when you u += 1
. If you write the same code in C, you'll notice an extreme performance difference. A tech such as numba
can achieve close-to-C speeds.
答案2
得分: 0
问题的确有点模糊。代码永远不能成为 Collatz 推测的数学证明。但如果你的意思是这段代码可以用来测试某个数字是否符合 Collatz 推测,那么是的,你的代码是正确的。这个推测是一个简单的循环,你做得很对。
理论上,你可以将代码写得更简洁、更快(但请注意,这段代码已经足够快了)。其他一些小的改进包括:
def collatz(number):
while number != 1:
if number & 1 == 0:
number >>= 1
else:
number = 3 * number + 1
print(number)
while True:
try:
number = int(input("输入一个正整数:"))
if number <= 0:
print("请输入一个正整数。")
else:
collatz(number)
break
except ValueError:
print("请输入一个有效的整数。")
这使用了位运算符:&
(用于检查偶数),去掉了一个 if 语句,并使用了位移运算符:>>
。对于巨大的数字,你可能不想打印这些数字。
英文:
The question is indeed what vague. The code can never be a mathematical proof of the presumption from Collatz. But if you mean if this code can be used to test if a certain number holds the presumption of Collatz. Than yes your code is correct to test this.This presumtion is a easy loop and you are doing that right.
In theory you could make it a bit compacter and faster (but note that the code is already fast enough). Other minor improvements are:
def collatz(number):
while number != 1:
if number & 1 == 0:
number >>= 1
else:
number = 3 * number + 1
print(number)
while True:
try:
number = int(input("Enter a positive non-zero integer: "))
if number <= 0:
print("Please enter a positive non-zero integer.")
else:
collatz(number)
break
except ValueError:
print("Please enter a valid integer.")
This uses uses a bitwise operator: & (for checking the even number), removes an if statement and uses bit-shifting operator: >>
And with enormous numbers you probably don't want to print the numbers
答案3
得分: 0
而不是使用 while True,可以使用一个在猜想错误时可以退出的条件。有两种方式可以证明猜想错误:1)序列循环到先前看过的数字,2)它逐渐扩展到无穷大而不收敛回到1。
对于第二种情况,你不能做太多事情(除非你能事先证明可以计算出最大迭代次数或最大步长)。对于第一种情况,你可以在进行的过程中将数字存储在一个集合中,并检查新值是否在集合中。
def collatz(number):
seen = set()
while number != 1 and number not in seen:
seen.add(number)
if number % 2:
number = 3 * number + 1
else:
number //= 2
# print(number)
return number == 1 # 如果达到1返回True,否则返回False
英文:
Instead of while True, could use a condition that CAN exit when/if the conjecture is wrong. There are two ways the conjecture could be proven wrong: 1) the sequence loops to a previously seen number 2) it progressively expands to infinity without converging back to 1.
There is not much you can do for the second one (unless you can prove that a maximum number of iterations of maximum step value can be computed beforehand). for the first one, you can store numbers in a set as you go and check new values against the set.
def collatz(number):
seen = set()
while number != 1 and number not in seen:
seen.add(number)
if number % 2:
number = 3 * number + 1
else:
number //= 2
# print(number)
return number == 1 # true if 1 reach, False otherwise
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论