[理工] 104成大電通 資結

看板Grad-ProbAsk作者 (隨便就好)時間5年前 (2019/02/23 19:03), 編輯推噓6(6推 0噓 24→)
留言30則, 2人參與, 5年前最新討論串1/1
https://i.imgur.com/BoXvyWT.jpg
https://i.imgur.com/lSNOKDT.jpg
請問K1和K2是什麼？ 我看不是很懂題目的意思QQ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 180.217.147.84 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1550919839.A.140.html
→
02/23 21:29, 5年前 , 1F
同問 看不懂 雖然前面有兩篇問過了不過都沒講到重點的樣子.
02/23 21:29, 1F
→
02/23 21:29, 5年前 , 2F
.. data record的長度到底是什麼
02/23 21:29, 2F
推
02/23 22:15, 5年前 , 3F
個人淺見，母題題意是用K1, K2 作為 data 的索引，可以
02/23 22:15, 3F
→
02/23 22:15, 5年前 , 4F
想像成 K 是座號而 data 是同學名字，樓上有疑問的 data
02/23 22:15, 4F
→
02/23 22:15, 5年前 , 5F
長度就類似名字長度。 data 和對應的 K 是綁在一起的，
02/23 22:15, 5F
→
02/23 22:15, 5年前 , 6F
排序用 K 來排，但實際上目的是要整理 data set，可以想
02/23 22:15, 6F
→
02/23 22:15, 5年前 , 7F
像成我們要把一個班級的同學排成一列需要有座號的協助去
02/23 22:15, 7F
→
02/23 22:15, 5年前 , 8F
對應，至於怎麼排序就是子題要問的問題，另外要注意母體
02/23 22:15, 8F
→
02/23 22:15, 5年前 , 9F
有聲明沒特別講的話各子題的 K 是互不相關的
02/23 22:15, 9F
推
02/23 22:37, 5年前 , 10F
那為什麼4-6答案是D E和F不行嗎 data長度會讓E和F不好實施
02/23 22:37, 10F
→
02/23 22:37, 5年前 , 11F
嗎
02/23 22:37, 11F
推
02/23 23:02, 5年前 , 12F
呃我不知道答案，純粹分享想法你加減參考，不敢說我一定
02/23 23:02, 12F
→
02/23 23:02, 5年前 , 13F
對，有錯再請指教。這題 data 的數量滿多的，如果一個 s
02/23 23:02, 13F
→
02/23 23:02, 5年前 , 14F
et 裡面稍微多塞一點東西(例如 data 長一點之類)就可能
02/23 23:02, 14F
→
02/23 23:02, 5年前 , 15F
會超出一個 page，這時候如果要 swap 兩個不同 page 內
02/23 23:02, 15F
→
02/23 23:02, 5年前 , 16F
的資料就會很耗時，因此像 quick sort 這種需要從兩端去
02/23 23:02, 16F
→
02/23 23:02, 5年前 , 17F
追蹤的算法勢必會有上面的問題。另一方面，merge sort
02/23 23:02, 17F
→
02/23 23:02, 5年前 , 18F
因為不是 in-place，也就是要把整份資料庫複製一份在外
02/23 23:02, 18F
→
02/23 23:02, 5年前 , 19F
面才能執行，這也是很花資源的行為。heap sort 同 quick
02/23 23:02, 19F
→
02/23 23:02, 5年前 , 20F
sort，heap sort 通常用 array 之類這種連續的資料結構
02/23 23:02, 20F
→
02/23 23:02, 5年前 , 21F
，也就是說在調整子樹中，一直往下找可能會穿越 page，
02/23 23:02, 21F
→
02/23 23:02, 5年前 , 22F
而且調整子樹次數也很多
02/23 23:02, 22F
推
02/23 23:05, 5年前 , 23F
所以 heap sort 也不適用在大型資料庫的排序
02/23 23:05, 23F
推
02/23 23:42, 5年前 , 24F
所以照這樣說的話 如果只是資料量多但data size不大的話用q
02/23 23:42, 24F
→
02/23 23:42, 5年前 , 25F
uick sort從兩邊去追縱的話很像是最適合的
02/23 23:42, 25F
→
02/23 23:42, 5年前 , 26F
謝謝你 解釋超詳細的
02/23 23:42, 26F
推
02/24 00:15, 5年前 , 27F
要看用途吧，例如 os 中比較要求 worst case 也就是要求
02/24 00:15, 27F
→
02/24 00:15, 5年前 , 28F
穩定性的時候會傾向 merge sort，何況 quick sort 還有
02/24 00:15, 28F
→
02/24 00:15, 5年前 , 29F
unstable 這個致命缺點，所以很難斷定什麼時候用哪個絕
02/24 00:15, 29F
→
02/24 00:15, 5年前 , 30F
對比較好
02/24 00:15, 30F
‣ 更多 sdfg014025xx 的文章
文章代碼(AID): #1SSIYV50 (Grad-ProbAsk)