[理工] 101 台大資工 軟設 [4] [6]

看板Grad-ProbAsk作者 (善良老百姓)時間7年前 (2017/02/05 17:23), 7年前編輯推噓13(13推 0噓 62→)
留言75則, 10人參與, 最新討論串1/1
想對一下答案 4: http://imgur.com/a/IuTqZ (b) (a) (c) (d) 6: http://imgur.com/a/fekTl (1) ABECFIDGJMHKNLOP (2) ABCDHGFEIJKLPONM (3) ABFJKGCEIMNOPLHD (4) (更正) ABCDFGHJKEIMNOPL 謝謝 -- ▲ ◢◤▅▄▃▁All you have to do is ●嚐嚐老納▍ ▲ ____ ◣Put Your banana in my candy cave▅▅▅▅▄ 的香蕉吧 -■ ▎ ▲ ⊙ ▲◆幹妳媽的 我不哈洋鯰◆ ╰ ◢ 〃〃 〃〃▼ ╰│╯ < ▲ ◣ ╯ ▄▂ ▄▂▼ ╰╮|▆◤ 、 ＣＨＡＲＬＩＥ ～ ╯ ～ ▲●◣ ╰ ▇▂▃ \ 皿 The Unicorn ψjeans1020 ●───● ◣◥◣◢◤ ◢◣ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.138.32.19 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1486286594.A.310.html
→
02/05 18:59, , 1F
請問4-2怎麼解
02/05 18:59, 1F
推
02/05 19:25, , 2F
我4-2和6-4和你不一樣 其他都一樣
02/05 19:25, 2F
推
02/05 19:39, , 3F
4-2我是選b但我也不太確定
02/05 19:39, 3F
推
02/05 19:42, , 4F
6-4我是算這樣
02/05 19:42, 4F
→
02/05 19:42, , 5F
02/05 19:42, 5F
謝謝! 漏算一個
→
02/05 20:00, , 6F
4-2我也選A
02/05 20:00, 6F
→
02/05 20:18, , 7F
想問一下 4-2 選a的理由@@ 我傾向選B
02/05 20:18, 7F
推
02/05 20:35, , 8F
4-2我選a吧，re-hashing我印象中是最慢的方式，真的不得
02/05 20:35, 8F
→
02/05 20:36, , 9F
以才會re-hashing,chaining雖然linked-list可以連很多，
02/05 20:36, 9F
→
02/05 20:36, , 10F
不過說unlimited似乎不太好
02/05 20:36, 10F
推
02/05 20:37, , 11F
A選項太武斷了，如果第一個hash function把所有元素都
02/05 20:37, 11F
→
02/05 20:38, , 12F
hash到同一個bucket時，chaining會比較慢
02/05 20:38, 12F
→
02/05 20:41, , 13F
因為rehashing還有第二次機會可以適當分散元素
02/05 20:41, 13F
→
02/05 20:42, , 14F
等等，這題是選對的還是錯的？
02/05 20:42, 14F
→
02/05 20:51, , 15F
不過照T大的意思，unlimited確實也是太武斷...
02/05 20:51, 15F
→
02/05 20:58, , 16F
想問一下4-2 c選項是正確的？
02/05 20:58, 16F
→
02/05 21:07, , 17F
4-2(c)我認為是對的，如果max number of elements超過
02/05 21:07, 17F
→
02/05 21:07, , 18F
bucket數，那會永遠都找不到合適的位置
02/05 21:07, 18F
→
02/05 21:08, , 19F
所以要先知道max number of elements避免做白工
02/05 21:08, 19F
→
02/05 21:10, , 20F
等等@_@ 這題是選錯的.. 我選a
02/05 21:10, 20F
→
02/05 21:14, , 21F
B 理論上是可無限沒錯 但實際上看allocation的多寡吧
02/05 21:14, 21F
推
02/05 21:30, , 22F
我覺得是c錯，rehashing是當load factor 超過一定
02/05 21:30, 22F
→
02/05 21:30, , 23F
值(ex:0.5)時重新開一個兩倍size的table，不用知道
02/05 21:30, 23F
→
02/05 21:30, , 24F
有多少元素吧
02/05 21:30, 24F
推
02/05 21:36, , 25F
我也選C 但我的理由跟樓上不同＠＠ 我以為的rehashing解
02/05 21:36, 25F
→
02/05 21:37, , 26F
決collision是指定義好一堆hash function 當H1(k) collis
02/05 21:37, 26F
→
02/05 21:38, , 27F
yu大上面說的是不是double hashing?
02/05 21:38, 27F
→
02/05 21:38, , 28F
ion時 嘗試用H2(k) 若仍collision則嘗試H3(k)... etc
02/05 21:38, 28F
→
02/05 21:38, , 29F
阿阿對耶！感謝gary大更正，把rehashing弄錯了QQ
02/05 21:38, 29F
阿...看來我也搞錯了 orz
→
02/05 21:39, , 30F
/faculty.simpson.edu/lydia.sinapova/www/cmsc250/
02/05 21:39, 30F
→
02/05 21:40, , 31F
等等 我發現我不會用電腦版貼XD
02/05 21:40, 31F
推
02/05 21:40, , 32F
選c+1..
02/05 21:40, 32F
→
02/05 21:41, , 33F
兩種似乎都叫rehasing QQ
02/05 21:41, 33F
推
02/05 21:42, , 34F
那我覺得我上面A選項太武斷那邊不要理我QQ
02/05 21:42, 34F
→
02/05 21:42, , 36F
sc250/LN250_Weiss/L09-HashingB.htm
02/05 21:42, 36F
→
02/05 21:43, , 37F
02/05 21:43, 37F
→
02/05 21:45, , 38F
感謝～
02/05 21:45, 38F
→
02/05 21:46, , 39F
一直以為rehashing是re-try的意思QQ
02/05 21:46, 39F
→
02/05 21:47, , 40F
就像aa大說的那樣，可是查了一下發現好像不太是這樣
02/05 21:47, 40F
→
02/05 21:50, , 41F
我對rehashing定義 跟aa大的一樣@@
02/05 21:50, 41F
推
02/05 21:52, , 42F
應該是說兩個都叫rehashing 但我覺得這邊他想講的比較偏
02/05 21:52, 42F
→
02/05 21:52, , 43F
向我講的那個 因為他是說要「處理」collision 而g大所提
02/05 21:52, 43F
→
02/05 21:52, , 44F
的比較像是「降低collision機率」 而不是「處理」collisi
02/05 21:52, 44F
→
02/05 21:52, , 45F
on 個人意見～
02/05 21:52, 45F
推
02/05 21:53, , 46F
02/05 21:53, 46F
→
02/05 21:54, , 47F
要做g大所提的rehashing比較像是insert完或insert前 發現
02/05 21:54, 47F
→
02/05 21:54, , 48F
load factor過高所以調整 而這邊所要講的應該是hashing後
02/05 21:54, 48F
→
02/05 21:54, , 49F
位子上已有人 感覺是不同事情
02/05 21:54, 49F
→
02/05 21:54, , 50F
我在Horowitz這本書看到的一段文字，感覺跟網路上的
02/05 21:54, 50F
→
02/05 21:54, , 51F
rehashing講的不太一樣，也許真的有兩個版本@@
02/05 21:54, 51F
→
02/05 21:55, , 52F
但我所講的那種也不會要用到max element數量吧@@ 剛剛查
02/05 21:55, 52F
這邊 max element 的數量是指同一個 bucket 裡的數量嗎?
→
02/05 21:55, , 53F
了一下洪毅答案給C
02/05 21:55, 53F
→
02/05 21:57, , 54F
可是他沒寫理由XD
02/05 21:57, 54F
→
02/05 21:57, , 55F
我認為書上講的跟aa大講的是一樣的意思，我再吸收一下
02/05 21:57, 55F
→
02/05 21:57, , 56F
這兩個版本的用意
02/05 21:57, 56F
→
02/05 21:58, , 57F
應該是aa大說的那樣，我也有查到那樣說法
02/05 21:58, 57F
→
02/05 21:59, , 58F
之前查的那個應該不是拿來處理collision
02/05 21:59, 58F
→
02/05 21:59, , 59F
先感謝解答 ~
02/05 21:59, 59F
→
02/05 22:04, , 60F
結果現在(A)(B)(C)感覺都有錯一些地方XD
02/05 22:04, 60F
→
02/05 22:16, , 61F
A我認為是對的～ 單就題目給的三個方法的話 因為chaining
02/05 22:16, 61F
→
02/05 22:17, , 62F
跟overflow area 都是collision->插到list->結束 但rehas
02/05 22:17, 62F
→
02/05 22:18, , 63F
可能要試非常多次才能找到空位 （個人想法～
02/05 22:18, 63F
→
02/05 22:18, , 64F
*rehashing
02/05 22:18, 64F
→
02/05 22:24, , 65F
我是想插到list如果要插到尾端的話要先找到尾端，也許
02/05 22:24, 65F
→
02/05 22:24, , 66F
沒那麼快？
02/05 22:24, 66F
→
02/05 22:42, , 67F
就是因為插尾端太慢了 所以list會插頭（我記得洪毅上課是
02/05 22:42, 67F
→
02/05 22:43, , 68F
這樣講的） 另外6-4我的答案跟我戰友的答案都同二樓
02/05 22:43, 68F
→
02/05 22:44, , 69F
其他都跟原PO一樣
02/05 22:44, 69F
已修改!
→
02/05 22:47, , 70F
原來洪逸說過list會插頭，不過我看Horowitz這本他舉的
02/05 22:47, 70F
→
02/05 22:48, , 71F
例子是插尾，不過插頭確實是快多了@@
02/05 22:48, 71F
※ 編輯: kyuudonut (220.132.251.85), 02/05/2017 23:08:41 ※ 編輯: kyuudonut (220.132.251.85), 02/05/2017 23:10:54
推
02/06 07:34, , 72F
4-2(C)錯吧知道element總數跟是否overflow沒那麼直接吧
02/06 07:34, 72F
推
02/06 10:44, , 73F
應該說也沒有一定要插頭XD 看你想怎麼實作 如果剛插入的
02/06 10:44, 73F
→
02/06 10:44, , 74F
東西不常被存取 可能就插尾會比較好(?) 另外max element
02/06 10:44, 74F
→
02/06 10:44, , 75F
應該是指最多會插入多少東西到hash table內
02/06 10:44, 75F
‣ 更多 kyuudonut 的文章
文章代碼(AID): #1Obky2CG (Grad-ProbAsk)