2016-12-16 136 views
0

我想解決有關Coursera上優先級隊列的這個算法問題,但他們網站上的分級人員總是說我的程序因時間限制超出錯誤而失敗。事實是,當我在我的PC上運行大量輸入(5000個線程,100000個作業)時,它可以順利運行並在不超過1秒的時間內打印出正確的結果。優先級隊列:並行處理

這是問題描述:

enter image description here

這是鏈接到我的代碼在Github上:https://gist.github.com/giantonia/3ddbacddc7bd58b220ab592f802d9602

任何幫助表示讚賞!

+0

你問全局代碼審查的東西,並沒有回答一個給定的問題陳述,和代碼示例你」重新給出一個完整的片段。這超出了stackoverflow的範圍,因爲它使答案難以寫出,而且您的問題太廣泛了。建議遵循給定的約束條件,並將ulimit設置爲512MB。 – zmo

回答

0

首先,我會建議在本地運行最大測試的解決方案(即n = 100000和m = 100000)(是的,5000和100000是大測試,但是你會在那裏停止嗎?爲什麼不呢?你使用最大可能的測試用例?)。

其次,存在至少兩個缺陷在您的解決方案:

  1. 它由一個增加的,而不是跳到下一個事件的時間:

    while len(jobs) > 0: 
        if threads[0][1] <= time: 
         record.append([threads[0][0], time]) 
         ... 
        else: 
         time += 1 
    

    它需要O(MAX_T)操作。如果最大時間是10^9,那太多了。

  2. jobs.pop(0)可能在O(n)工作(這取決於Python實現,但如果它像C++向量,這是許多口譯的情況下),這將產生在最壞的情況下O(n^2)操作。這也太多了。

解決方案中可能還有其他緩慢的部分(我立即看到了這兩個部分,所以我只寫了這些部分)。

我建議你重新設計算法,證明它的速度足夠快(提示:它應該是類似O((n + m) log n)的東西),並且只有在執行它之後。

0

代碼最弱的點以下時,

while len(jobs) > 0: 
    if threads[0][1] <= time: 
     ... 
    else: 
     time += 1 

這個循環將隨時間一起執行,而不是就業人數都要做。它需要O(MAX_T)成本!太慢了!

這是我對這個問題的解決方案。它需要O(N + MlgN))。

這個想法很簡單。

  1. 構造priority_queue以及最早的完成時間。
  2. 從priority_queue中選擇next_thread並更新其完成作業的時間。
  3. 將其插入優先級隊列

下面是代碼,

# 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]))