gpt4 book ai didi

python - 为什么这种并行合并算法不起作用?

转载 作者:塔克拉玛干 更新时间:2023-11-03 06:13:41 26 4
gpt4 key购买 nike

为什么这个并行合并算法不起作用?

对于给定的两个排序数组 A 和 B,我想设计一个并行算法将它们合并为一个排序数组 C。

我是引用下一页写的。

本质上它是一种可以并行或顺序执行的算法。我正在尝试暂时编写一个顺序合并算法。我该如何修复这个程序?

#coding: utf-8

def binary_search(x, A, left, right):
begin = left
end = right
while begin < end:
middle = (begin + end) / 2
if x <= A[middle]:
end = middle
else:
begin = middle + 1
return end

def merge(A, B, C, R1, R2, R3):
[[p1, r1], [p2, r2], [p3, r3]] = [R1, R2, R3]

m = r1 - p1
n = r2 - p2

if m < n: # ensure thet m >= n
A, B = B, A
m, n = n, m
[p1, r1], [p2, r2] = R2, R1

if m <= 0: # both empty?
return

q1 = (p1 + r1) / 2
q2 = binary_search(A[q1], B, p2, r2)
q3 = p3 + (q1 - p1) + (q2 - p2)
C[q3] = A[q1]

merge(A, B, C, [p1, q1-1], [p2, q2-1], [p3, q3])
merge(A, B, C, [q1+1, r1], [q2, r2], [q3+1, r3])

A = [2,3,7,8,11,16]
B = [1,5,7,10,15,19]

C = [0 for i in range(len(A)+len(B))]
merge(A, B, C, [0, len(A)-1], [0, len(B)-1], [0, len(C)-1])
print C

最佳答案

问题出在下面的语句

if m <= 0: # both empty?
return

您没有处理 1 个元素数组的合并。

以下代码有效并添加了一些解释更改的注释。这可能是一个起点。

#coding: utf-8
from math import ceil

def binary_search(x, A, left, right):
begin = left
end = right
while begin < end:
middle = (begin + end) / 2
if x <= A[middle]:
end = middle
else:
begin = middle + 1
return end

def merge(A, B, C, R1, R2, R3):
[[p1, r1], [p2, r2], [p3, r3]] = [R1, R2, R3]

m = r1 - p1
n = r2 - p2

if m < n: # ensure thet m >= n
A, B = B, A
m, n = n, m
[p1, r1], [p2, r2] = R2, R1

if m <= 0:
# 1 elements in both the array. Merge in proper order
if m == 0 and n == 0:
q3 = p3
if A[p1] < B[p1]:
C[q3] = A[p1]
C[q3+1] = B[p2]
else:
C[q3] = B[p2]
C[q3+1] = A[p1]
# 1 elements in A array.
elif m == 0:
C[p3] = A[p1]
return

q1 = (p1+r1)/2

q2 = binary_search(A[q1], B, p2, r2)
q3 = p3 + (q1 - p1) + (q2 - p2)
C[q3] = A[q1]

merge(A, B, C, [p1, q1-1], [p2, q2-1], [p3, q3])
merge(A, B, C, [q1+1, r1], [q2, r2], [q3+1, r3])

A = [2,3,7,8,11,16]
B = [1,5,7,10,15,19]
print A
print B
C = [0 for i in range(len(A)+len(B))]
merge(A, B, C, [0, len(A)-1], [0, len(B)-1], [0, len(C)-1])
print C

希望对您有所帮助!

关于python - 为什么这种并行合并算法不起作用?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/44579733/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com