作者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/cn.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