PTT數位生活區 / java

[問題] 資料的比較、插入、排序

看板java作者 (-.-)時間7年前 (2016/09/02 10:44), 7年前編輯推噓8(8推 0噓 46→)
留言54則, 7人參與, 最新討論串1/4 (看更多)
是這樣的，最近碰到了一個資料排序的問題 假設我有A、B兩個array的資料 資料(4,10)，是做一個動作持續4秒，後delay10秒 而A的array會先做而B會跟A的動作做比較如果B 如果B做一個動作和delay的時間比A的delay時間短 則可以插入到A的delay時間中，減少時間的浪費 而A的一個動作做完移至到B需要兩秒的時間(B移動到A也需要兩秒時間) 這個時間也要包含進去，需要達到密合的動作 沒辦法A或B的delay時間到了，卻還在做別的動作 A B -------------- -------------- | (4,10) | | (2,2) | -------------- -------------- | (4,10) | | (2,20) | -------------- -------------- | (2,5) | | (2,5) | -------------- -------------- 如果B可以插入到A中做排序則可以得到C得array C -------------- | (A,4) | -------------- | (B,2) | -------------- | (delay,2) | -------------- | (B,2) | -------------- | (A,4) | -------------- | (delay,10) | -------------- | (A,2) | -------------- | (delay,2) | -------------- | (B,2) | -------------- 反之，如果沒辦法排序的話則會得到A動作做完再做B動作的array 想請問各位高手...這有甚麼方法可以解決.. 我想了很久完全想不到有甚麼解決的辦法Orz. -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 60.250.82.82 ※ 文章網址: https://www.ptt.cc/bbs/java/M.1472784265.A.CE2.html
→
09/02 10:49, , 1F
看起來像os排程的問題
09/02 10:49, 1F
推
09/02 13:21, , 2F
思考中，請問由a移到b的過程中，b可以做事嗎
09/02 13:21, 2F
不行...a移動到b點後，b才能做事，且這時a需處於delay的時間或a已完成動作QQ
推
09/02 14:58, , 3F
不就是 b.runtime+4 < a.delay 就可以把 b 插進去？
09/02 14:58, 3F
那...B的delay時間呢...假設b的delay時間結束了但a的動作還沒做完這樣也不成立.. 因為沒辦法馬上執行b的動作..
推
09/02 15:15, , 4F
我寫好了，但是醜醜的需要重構，先把重構前的版本寄給你
09/02 15:15, 4F
→
09/02 15:16, , 5F
給我信箱吧~
09/02 15:16, 5F
→
09/02 15:17, , 6F
邏輯上是去塞A之間的slot，判斷能不能塞入0~到多個B的工
09/02 15:17, 6F
→
09/02 15:18, , 7F
作
09/02 15:18, 7F
大大 我寄信給你了QQ
→
09/02 15:39, , 8F
收到了 我研究看看 謝謝大大
09/02 15:39, 8F
大大會有問題..如果A動作的delay去做B動作...那B動作的delay時間也不能超過QQ 假設我給參數是這樣 schedule.addtask(new Task(2, 20, 'A')); schedule.addtask(new Task(8, 10, 'A')); schedule.addtask(new Task(10, 15, 'A')); schedule.addtask(new Task(12, 10, 'A')); taskBs.add(new Task(2, 2, 'B')); taskBs.add(new Task(12, 10, 'B')); taskBs.add(new Task(22, 3, 'B')); taskBs.add(new Task(12, 50, 'B')); 得到的結果是A B B A A A B B taskBs.add(new Task(12, 10, 'B')); 的delay只有10秒 可是他卻把 schedule.addtask(new Task(10, 15, 'A')); schedule.addtask(new Task(12, 10, 'A')); 都執行完了 這樣就超過B的delay10秒.. 所以應該得到的排序結果是A A A A B B B B才對QQ"
推
09/02 18:01, , 9F
b動作的delay也要卡喔？我以為這段是看結束時間加返回
09/02 18:01, 9F
→
09/02 18:01, , 10F
時間及好了，我晚點再修一下
09/02 18:01, 10F
推
09/02 18:12, , 11F
這樣b的動作跟delay有啥分別？可以把兩個變數加總當作一
09/02 18:12, 11F
→
09/02 18:12, , 12F
個嗎
09/02 18:12, 12F
b的動作需在a的delay內做..而a的動作需要再b的delay內做.. 而假如a的delay結束後，就要執行下一個a的動作不能因為在執行b的動作 就耽誤到a的動作..反之b也是如此 只要會耽誤到a或b的動作 就沒辦法去做排程QQ..
→
09/02 20:09, , 13F
我想了想你的需求，用heuristic的方式似乎無法解..
09/02 20:09, 13F
→
09/02 20:10, , 14F
有可能當下看這個工作可以排進去，但是往下做幾步後產生
09/02 20:10, 14F
→
09/02 20:10, , 15F
卡delay...
09/02 20:10, 15F
往下做幾步後卡delay??如果卡delay就是A做完在換B做.. 所以我的意思是兩個排完後才執行動作QQ...應該會有一個array來暫存正在排序的動作
→
09/02 20:33, , 16F
你的時間單位都是整數嗎?
09/02 20:33, 16F
→
09/02 20:35, , 17F
是的 都是整數……Orz
09/02 20:35, 17F
※ 編輯: gene07 (36.230.203.80), 09/02/2016 21:13:18
→
09/02 23:44, , 18F
多背包多物品。貪婪解應該可以，最佳解就。。
09/02 23:44, 18F
推
09/03 03:42, , 19F
為什麼執行後要延遲? 是持續執行嗎?
09/03 03:42, 19F
→
09/03 03:42, , 20F
這樣設計遲早DEAD LOCK
09/03 03:42, 20F
→
09/03 03:46, , 21F
這做即時排序就好了 一開始看A要先還是B先
09/03 03:46, 21F
→
09/03 03:47, , 22F
A執行時把B的清單拿來加在B後面
09/03 03:47, 22F
→
09/03 03:47, , 23F
B執行到最後面的時候把A的清單拿來加到後面
09/03 03:47, 23F
→
09/03 03:47, , 24F
反覆執行不就好了?
09/03 03:47, 24F
推
09/03 03:54, , 25F
我覺得你的問題可能是沒有主迴圈做時間檢測
09/03 03:54, 25F
→
09/03 03:55, , 26F
依我看至少要兩條執行緒
09/03 03:55, 26F
→
09/03 03:55, , 27F
主 + 執行 或是 主 + A執行 + B執行
09/03 03:55, 27F
推
09/03 04:00, , 28F
另外你的排序結果應該是A B A A A B B B 才對
09/03 04:00, 28F
→
09/03 04:00, , 29F
第一個B是可以排進去的
09/03 04:00, 29F
→
09/03 14:31, , 30F
可是b排進去的話 b的delay結束了 卻還在做a的事情 這樣就
09/03 14:31, 30F
→
09/03 14:31, , 31F
不行了……
09/03 14:31, 31F
→
09/03 14:38, , 32F
沒有吧 是你的規則不夠詳細還是我搞錯了什麼?
09/03 14:38, 32F
→
09/03 14:39, , 33F
B(2,2) 執行完 A還在DELAY中 沒有問題吧
09/03 14:39, 33F
→
09/03 14:40, , 34F
此時沒有可以插入的程序 就是等A1 DELAY完接著A2
09/03 14:40, 34F
→
09/03 14:42, , 35F
如果連A DELAY的時間都算執行時間 那麼你一開始把B
09/03 14:42, 35F
→
09/03 14:43, , 36F
插到A DELAY的時間區段來執行 我就搞不懂了
09/03 14:43, 36F
→
09/03 14:44, , 37F
如果沒有明確的說明規則 我們其它人只是在陪你鬼打牆
09/03 14:44, 37F
我的意思是.. (2, 20, 'A')-->A做完後delay20秒(20秒內會做:往B移動2秒+B動作2秒+B delay2秒+ B的第2個洞做12秒+回A的動作2秒) (2, 2, 'B') (12, 10, 'B')-->(因為這邊跑到A後需要兩秒 所以B delay只剩八秒) (8, 10, 'A') -->(而A若做完8秒的動作在+跑去B所需的兩秒就超過B所剩的8秒delay) 就沒辦法做排序了..
→
09/03 14:46, , 38F
原po的意思是，A不能被B delay，B也不能被A delay
09/03 14:46, 38F
→
09/03 14:47, , 39F
所以單獨對A或B來說根本不是分成多個工作，而是一整組固定
09/03 14:47, 39F
→
09/03 14:48, , 40F
時間在執行、固定時間可空出來的工作
09/03 14:48, 40F
→
09/03 14:54, , 41F
B(2,2)執行完馬上就該執行B(12,10)，然後B跑一半A的delay就
09/03 14:54, 41F
→
09/03 14:55, , 42F
會結束所以不行，其實這組參數B(2,2),B(12,10)勢必要一個
09/03 14:55, 42F
→
09/03 14:56, , 43F
他第一個A的DELAY不是20秒嗎?
09/03 14:56, 43F
→
09/03 14:58, , 44F
18單位的空間，只能插在A(2,20)，算是能很簡單計算的例子
09/03 14:58, 44F
→
09/03 15:00, , 45F
把B插在T2，之後在T40 A(10,15)要執行時，B正在B(22,3)執行
09/03 15:00, 45F
→
09/03 15:01, , 46F
中(T28~T50)，當然不行
09/03 15:01, 46F
→
09/03 15:02, , 47F
算錯，把B插在T4才對，上面是(T30~T52)
09/03 15:02, 47F
→
09/03 15:09, , 48F
基本上這個問題可以轉化成
09/03 15:09, 48F
→
09/03 15:18, , 49F
兩個序列比對，但是這樣時間複雜度太高了
09/03 15:18, 49F
→
09/03 15:24, , 50F
其實原問題的描述不太合理，整個序列是固定的，感覺根本沒
09/03 15:24, 50F
→
09/03 15:25, , 51F
有拿個別執行段來估算的空間，既不能延遲也不能提早
09/03 15:25, 51F
→
09/03 15:53, , 52F
原PO你這段解釋又多出一個問題，為什麼B(12,10)回A剛好接上
09/03 15:53, 52F
→
09/03 15:57, , 53F
..我又看錯了，所以在T30 A結束要等T32 B才能開始
09/03 15:57, 53F
→
09/03 15:57, , 54F
(T30~T52)插不進去
09/03 15:57, 54F
...是的 ※ 編輯: gene07 (36.230.203.80), 09/03/2016 15:59:03
‣ 更多 gene07 的文章
文章代碼(AID): #1NoEU9pY (java)
java 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 gene07 的文章
文章代碼(AID): #1NoEU9pY (java)