我想解決有關Coursera上優先級隊列的這個算法問題,但他們網站上的分級人員總是說我的程序因時間限制超出錯誤而失敗。事實是,當我在我的PC上運行大量輸入(5000個線程,100000個作業)時,它可以順利運行並在不超過1秒的時間內打印出正確的結果。優先級隊列:並行處理
這是問題描述:
這是鏈接到我的代碼在Github上:https://gist.github.com/giantonia/3ddbacddc7bd58b220ab592f802d9602
任何幫助表示讚賞!
我想解決有關Coursera上優先級隊列的這個算法問題,但他們網站上的分級人員總是說我的程序因時間限制超出錯誤而失敗。事實是,當我在我的PC上運行大量輸入(5000個線程,100000個作業)時,它可以順利運行並在不超過1秒的時間內打印出正確的結果。優先級隊列:並行處理
這是問題描述:
這是鏈接到我的代碼在Github上:https://gist.github.com/giantonia/3ddbacddc7bd58b220ab592f802d9602
任何幫助表示讚賞!
首先,我會建議在本地運行最大測試的解決方案(即n = 100000和m = 100000)(是的,5000和100000是大測試,但是你會在那裏停止嗎?爲什麼不呢?你使用最大可能的測試用例?)。
其次,存在至少兩個缺陷在您的解決方案:
它由一個增加的,而不是跳到下一個事件的時間:
while len(jobs) > 0:
if threads[0][1] <= time:
record.append([threads[0][0], time])
...
else:
time += 1
它需要O(MAX_T)
操作。如果最大時間是10^9,那太多了。
jobs.pop(0)
可能在O(n)
工作(這取決於Python實現,但如果它像C++向量,這是許多口譯的情況下),這將產生在最壞的情況下O(n^2)
操作。這也太多了。
解決方案中可能還有其他緩慢的部分(我立即看到了這兩個部分,所以我只寫了這些部分)。
我建議你重新設計算法,證明它的速度足夠快(提示:它應該是類似O((n + m) log n)
的東西),並且只有在執行它之後。
代碼最弱的點以下時,
while len(jobs) > 0:
if threads[0][1] <= time:
...
else:
time += 1
這個循環將隨時間一起執行,而不是就業人數都要做。它需要O(MAX_T)成本!太慢了!
這是我對這個問題的解決方案。它需要O(N + MlgN))。
這個想法很簡單。
下面是代碼,
# python3
def parent_key_cal(key):
if key % 2 == 0:
parent_key = key//2
else:
parent_key = (key - 1)//2
return parent_key
def swap(alist, key1, key2):
temp = alist[key1]
alist[key1] = alist[key2]
alist[key2] = temp
def return_min_key(alist, parent, left, right, criteria):
min_value = parent
if alist[parent][criteria] > alist[left][criteria]:
min_value = left
if right != -1 and alist[min_value][criteria] > alist[right][criteria]:
min_value = right
elif alist[parent][criteria] < alist[left][criteria]:
if right != -1 and alist[min_value][criteria] > alist[right][criteria]:
min_value = right
return min_value
def shift_up(alist, key):
while key > 1:
parent = parent_key_cal(key)
if alist[parent][1] != alist[key][1]:
if alist[parent][1] > alist[key][1]:
swap(alist, parent, key)
key = parent
else:
break
else:
if alist[parent][0] > alist[key][0]:
swap(alist, parent, key)
key = parent
else:
break
def shift_down(alist, key):
if 2*key >= len(alist):
return
parent = key
left = 2*key
right = 2*key + 1
if right >= len(alist):
if (alist[parent] == alist[left]) == True:
min_value = return_min_key(alist, parent, left, -1, 0)
else:
min_value = return_min_key(alist, parent, left, -1, 1)
else:
if (alist[parent] == alist[left] == alist[right]) == True:
min_value = return_min_key(alist, parent, left, right, 0)
else:
min_value = return_min_key(alist, parent, left, right, 1)
if min_value != parent:
swap(alist, parent, min_value)
shift_down(alist, min_value)
def min_heap(alist):
# Index 0 element is dummy. minimum element's index is 1
min = alist[1]
alist.pop(1)
# Maintain heap structure
parent_last_element = parent_key_cal(len(alist)-1)
for key in reversed(range(1, parent_last_element + 1)):
shift_down(alist, key)
return min
def heap_insert(alist, value):
alist.append(value)
shift_up(alist, len(alist)-1)
line1 = input().split()
n = int(line1[0])
m = int(line1[1])
jobs = list(map(int, input().split()))
threads = []
for i in range(n):
threads.append([i, 0])
# Insert dummy element to make heap calculation easier
threads.insert(0,[-1,-1])
record = []
# O(M)
while len(jobs) > 0:
# Allocate a job to a thread and record it this moment
# "threads" is min_heap along with time to finish a allocated job. 0 -> thread order, 1 -> time to finish the job
next_thread = min_heap(threads) # O(lgN)
record.append([next_thread[0], next_thread[1]])
# Updated poped thread as much as time to finish the next job
next_thread[1] += jobs.pop(0)
# Insert this into min_heap
heap_insert(threads, next_thread)
for i in range(len(record)):
print(str(record[i][0]) + ' ' + str(record[i][1]))
你問全局代碼審查的東西,並沒有回答一個給定的問題陳述,和代碼示例你」重新給出一個完整的片段。這超出了stackoverflow的範圍,因爲它使答案難以寫出,而且您的問題太廣泛了。建議遵循給定的約束條件,並將ulimit設置爲512MB。 – zmo