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