作者gene07 (-.-)
看板java
標題Re: [問題] 資料的比較、插入、排序
時間Tue Sep 6 15:43:24 2016
※ 引述《cowbaying (是在靠北喔)》之銘言：
: schedule.addtask(new Task(2, 20, 'A1'));
: schedule.addtask(new Task(8, 10, 'A2'));
: schedule.addtask(new Task(10, 15, 'A3'));
: schedule.addtask(new Task(12, 10, 'A4'));
: taskBs.add(new Task(2, 2, 'B1')); (實際長度8)
: taskBs.add(new Task(12, 10, 'B2')); (實際長度26)
: taskBs.add(new Task(22, 3, 'B3')); (實際長度29)
: taskBs.add(new Task(12, 50, 'B4')); (實際長度66)
: A1 A2 A3 A4
: |>!---------|>>>>-----|>>>>>-------|>>>>>>-----
: |>-! |>>>>>>-----|>>>>>>>>>>>-|>>~~~
: B1 B2 B3 B4
: 我對這個機制的理解如上圖
: A是主要的
: B能否執行要看A延遲的時間是否足夠把B插入、執行、延遲跟切換回A的時間容納進去
: 原PO的文字描述實在是看不太懂
: 如果B的延遲時間會連帶延遲到A的時間
: 那麼根本不須排序了
: A執行完換B就好
我的意思是...
假設...
(4,10,'A1') | (2,2,'B1')
|
(4,10,'A2') | (2,20,'B2')
|
(2,5,'A3') | (2,5,'B3')
A1 A2
|>!--------------------------------------|>!-------
(往B,2秒)|>!------------------|>!---------------
B1 (B1做完delay 2s) B2 (B往A,2秒)
這樣剛好從A到B來回一次4秒+B1執行的兩秒和delay兩秒+B2的執行2秒
剛好可以插入到A1的delay10秒內...而B2的delay 20秒是從B回到A開始算
所以A2開始執行時B2 delay剩18秒..A2動作做完B2 delay剩14秒
A2 delay 10秒結束B2 delay剩10秒 A3動作做完B2 delay剩2秒
此時A移動到B剛好2秒 可以執行B3
應此就可以成功排序成 A1 B1 B2 A2 A3 B3
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 60.250.82.82
※ 文章網址: https://webptt.com/m.aspx?n=bbs/java/M.1473147809.A.FFB.html
1F：推 cowbaying: 我大概了解了 B的延遲可以切割 09/08 13:38
我完全沒有頭緒...~"~
2F：→ cowbaying: 你等我用FX寫一個有進度表的模擬程式給你看看吧 XD 09/08 18:51
魯弟我想到了一個方法，不知道這樣行不行....
(4,10,'A1') | (2,2,'B1')
|
(4,10,'A2') | (2,20,'B2')
|
(2,5,'A3') | (2,5,'B3')
創一個最後輸出的array
然後把執行動作和delay的時間都拆成1秒1秒去判斷
執行動作假設為1，delay動作為0
A1 (往B移兩秒) A2 (往B移兩秒) A3
1,1,1,1,1,1,0,0,0,0,0,0,1,1,1,1,1,1,1,1,0,0,0,0,0,1,1,1,1,0,0,0,0,0
(往A移動兩秒) (往A移動兩秒)
B1 B2 B3
1,1,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0
然後把A動作跟B動作去做 & 如果不行A就往後一格繼續跟B比較，
全部都等於0代表排序完成
※ 編輯: gene07 (36.230.202.56), 09/09/2016 22:25:29
3F：→ ssccg: 一秒一秒去比是對的，但是不用把輸出轉出來，用範圍去比 09/10 09:37
4F：→ ssccg: 但是就是我之前說的，如果輸入n個，每個值為k bit，這演算 09/10 09:43
5F：→ ssccg: 法複雜度是O(n^2 * 2^k)，雖然是對的... 09/10 09:44
6F：→ ssccg: 其實我一開始想到的作法就是 09/10 09:45
7F：→ ssccg: AAAAAA********AAAAAA********AAAA***(後面可補*****... 09/10 09:47
8F：→ ssccg: BBBBBBBB******************BBBB*** 09/10 09:48
9F：→ ssccg: 然後直接用string match的演算法去跑就好了 09/10 09:50