[問題] 提昇搜尋的效率

[sudada (嘰咕嘰咕嘰咕)]

各位好

最近遇到一個sorting的問題

假設我有一個List裡面放我自訂的class
他必須是個排序好的狀態
但是每次有新增或更新資料 我都必須取得那筆資料的index

而且使用上get的使用機率應該會比insert高一點
          ^^^
        這邊修正一下...

目前我有兩種想法

第一
每次丟資料進去都call一次sort
不過這樣沒辦法直接知道我剛剛新增的那筆資料
到底會被丟到哪裡去
所以sort完以後還要再抓一次index?
這種方法我覺得完全不可行......

第二
跑迴圈用自己的compare方式找到適當的位置
直接call insert
這樣"感覺上"快很多
但是問題出在用List的資料結構的話
每次都必須從頭開始 cost應該是O(n)?
如果要改進這裡勢必要改資料結構
用binary tree又怕會影響整體get的效能

想請問大家會怎麼取捨

謝謝

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.221.177.192
→ eieio:SortedSet 如何？用 subset() 和 headset().size()
→ eieio:我的意思是 TreeSet orz
→ swpoker:請問有很多物件嗎~例如上萬個?不然100個都沒有什麼差異阿
→ realmeat:用TreeSet寫comparator 結案
推 popcorny:apache commons有TreeList http://goo.gl/l6sJm
→ sudada:粗估會有上萬
推 PsMonkey:上萬筆也還好，我覺得你擔心效率之前要先擔心記憶體 XD
→ swpoker:這樣感覺用資料庫算了~頂多放個key就好
→ swpoker:大概只有在多執行緒時可能會有問題,但還是先考慮記憶體
→ tkcn:10^4 還不用開始擔心記憶體吧?
→ popcorny:同意10^4的記憶體不是問題..用tree based list就好了
→ swpoker:或許可以分類阿~減少每次搜尋的最大次數
推 sbrhsieh:請問此集合需要是排序好的狀態的理由是什麼？
推 luoqr:應該先問你的get range是什麼?
※ 編輯: sudada          來自: 114.47.158.194       (06/19 00:10)
→ sudada:因為給使用者get的頻率會高很多 而且抓到的一定是排序過的
→ sudada:所以資料在insert時我會先排序 使用者只要下一個range
→ swpoker:請問有多執行緒的問題嗎?
推 PsMonkey:那在 get 之前判斷有沒有 sort 過就好了阿
推 popcorny:保持sort好這總需求很常見啊..這樣get才會有效率啊
推 popcorny:keyword: binary search tree
→ popcorny:"這樣get才有效率" 應該要改成 "這樣search才有效率"
→ sbrhsieh:若 sorted list已把get/search降到理想程度，又何需在
→ sbrhsieh:insert/update時取得record的index？特別是get op 次數遠
→ sbrhsieh:大於insert/update op 的情況下。
→ sbrhsieh:用binary tree怕影響get效能，sorted list也是二元搜尋啊
→ sbrhsieh:效能就可接受，這很奇怪ㄋㄟ...