Re: [問題] 提昇搜尋的效率
因為資訊有限，我沒有辦法做完整的判斷，
所以我只針對各段獨立的做回覆。
※ 引述《sudada (嘰咕嘰咕嘰咕)》之銘言：
: 各位好
: 最近遇到一個sorting的問題
: 假設我有一個List裡面放我自訂的class
: 他必須是個排序好的狀態
: 但是每次有新增或更新資料 我都必須取得那筆資料的index
說不定該改進的是這個需求？
: 而且使用上get range的使用機率應該會比insert高一點
: 目前我有兩種想法
: 第一
: 每次丟資料進去都call一次sort
: 不過這樣沒辦法直接知道我剛剛新增的那筆資料
: 到底會被丟到哪裡去
: 所以sort完以後還要再抓一次index?
: 這種方法我覺得完全不可行......
: 第二
: 跑迴圈用自己的compare方式找到適當的位置
: 直接call insert
: 這樣"感覺上"快很多
: 但是問題出在用List的資料結構的話
: 每次都必須從頭開始 cost應該是O(n)?
List 是一種 ADT，而不是一種資料結構，
我想你指的應該是 ArrayList 或著 LinkedList 其中之一。
如果你指的是 ArrayList，
那麼在尋找插入點時可以用 binary search，而不需要 "從頭開始"，
但是插入的部份要將所有 element 向後移，所以整體仍是 O(n)。
若指的是 LinkedList，
則是 O(n) 循序的找到插入點，並以 O(1) 完成插入，
但是每次 get 也都要 O(n)，
以你的需求來說，應該不會是個好選擇。
: 如果要改進這裡勢必要改資料結構
: 用binary tree又怕會影響整體get的效能
: 想請問大家會怎麼取捨
: 謝謝
簡單的說，ArrayList 就是 get O(1)，insert O(n)
tree-based 的資料結構則都是 O(log n)，
若把 "get/insert 的比例" 及 n 代入，大概就可以看出哪一個選擇比較有優勢了。
---
至於該不該做最佳化，那又是另一個議題了。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.34.7.189
推
06/18 14:01, , 1F
06/18 14:01, 1F
討論串 (同標題文章)