英文:
Iterating efficiently in NumPy where next iteration depends on previous
问题
我正在尝试使用NumPy模拟任意精度的二进制算术。作为一个简单的案例，我有一段代码（在基本的非NumPy Python中），它将一个二进制数加一，其中二进制数被表示为由最不重要位到最重要位的0和1的列表（因此它们从右到左读取为二进制数）:
def increment_bits(bits):
"""
Returns binary representation corresponding to bits + 1
where bits is a list of 0s and 1s.
>>> increment_bits([1, 1, 1, 0, 1]) # 23 + 1 == 24
[0, 0, 0, 1, 1]
>>> increment_bits([1, 1, 1]) # 7 + 1 == 8 <- an extra bit now needed
[0, 0, 0, 1]
"""
new_bits = bits[:]
for i, v in enumerate(new_bits):
if v:
new_bits[i] = 0
else:
new_bits[i] = 1
return new_bits
# if we have made it here, then there is a final "carry"
new_bits.append(1)
return new_bits
我的目标是使用NumPy实现相同的效果，但更快，但我对NumPy还不熟悉，不确定在NumPy数组上迭代以实现所需效果的最快（或最符合NumPy风格）方法。
英文:
I am trying to simulate arbitrary-precision binary arithmetic using NumPy. As a simple case, I have code (in basic, non-NumPy Python) that adds one to a binary number where binary numbers are represented as lists of 0s and 1s from least-to-most significant bits (so they read as binary numbers from right to left):
def increment_bits(bits):
"""
Returns binary representation corresponding to bits + 1
where bits is a list of 0s and 1s.
>>> increment_bits([1, 1, 1, 0, 1]) # 23 + 1 == 24
[0, 0, 0, 1, 1]
>>> increment_bits([1, 1, 1]) # 7 + 1 == 8 <- an extra bit now needed
[0, 0, 0, 1]
"""
new_bits = bits[:]
for i, v in enumerate(new_bits):
if v:
new_bits[i] = 0
else:
new_bits[i] = 1
return new_bits
# if we have made it here, then there is a final "carry"
new_bits.append(1)
return new_bits
My goal is to achieve the same effect, but faster, using NumPy, but I am new to NumPy and am not sure the fastest (or most NumPy-onic) way to iterate over a NumPy array to achieve the desired effect.
答案1
得分: 1
I agree with the commenters that Numpy array is not the way to go, but I wanted to give it a try nevertheless. The main idea was to cleverly create a mask for where to add a one by using the cumulative product. This would create an array of 1's until the first 0. We then need to shift by 1 and then set the 0th index to 1 so we add one to every index until after the first 0.
The hope was that maybe numpy had a faster than O(n) implementation of cumulative product, but the result was still slower than just iterating through the list. Also, there's always the overhead of converting to numpy array.
def numpy_bit(bits):
mask = np.cumprod(bits)
mask = np.roll(mask, 1)
mask[0] = 1
res = (bits + np.ones(len(bits)) * mask) % 2
if np.all(res == 0):
return np.append(res, 1)
else:
return res
英文:
I agree with the commenters that Numpy array is not the way to go, but I wanted to give it a try nevertheless. The main idea was to cleverly create a mask for where to add a one by using the cumulative product. This would create an array of 1's until the first 0. We then need to shift by 1 and then set the 0th index to 1 so we add one to every index until after the first 0.
The hope was that maybe numpy had a faster than O(n) implementation of cumulative product, but the result was still slower than just iterating through the list. Also, there's always the overhead of converting to numpy array.
def numpy_bit(bits):
mask = np.cumprod(bits)
mask = np.roll(mask, 1)
mask[0] = 1
res = (bits + np.ones(len(bits)) * mask) % 2
if np.all(res == 0):
return np.append(res, 1)
else:
return res
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论