優先度キュー：並列処理

Question

私はCourseraの優先度キューに関するこのアルゴリズム上の問題を解決しようとしていますが、Webサイトのグレーダーは時間制限を超えてプログラムが失敗したと言っています。実際には、私は巨大な入力（5000スレッド、100000ジョブ）で私のPC上で実行すると、スムーズに動作し、1秒以内に正しい結果を印刷するということです。

これは、問題の説明です：https://gist.github.com/giantonia/3ddbacddc7bd58b220ab592f802d9602

すべてのヘルプ感謝：

これはGithubの上の私のコードへのリンクです！

Answer 1

まず、ローカルで最大テスト（n = 100000、m = 100000）でソリューションを実行することをお勧めします（ええ、5000と100000は大きなテストですが、そこで停止しますか？可能な限り最大のテストケースを使用しますか？）。

は第二に、あなたのソリューションに少なくとも2つの欠陥がある：

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^2)操作を得ている、（それはPythonの実装に依存しますが、それは多くの通訳のためのケースであるC++ベクトル、同じように動作している場合）O(n)に働くかもしれません。それはあまりにも多くです。

解決策には他の遅い部分があるかもしれません（私はこれらの2つを直ちに見たので、それらについて書きました）。

アルゴリズムを再設計し、それが十分速い（ヒント：O((n + m) log n)のようなものであることを証明する）ことをお勧めします。

Answer 2

あなたのコードの最大の弱点は、以下である、

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

このループは、時間と一緒に実行されます、いないジョブの数が行う必要があります。それはO（MAX_T）のコストが必要です！遅すぎる！

これは私のこの問題に関する解決策です。それはO（N + MlgN）を必要とする）。

アイデアはかなりシンプルです。

1. 完了するのが最も早い時期に優先度キューを作成します。
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]))