作者sudada (嘰咕嘰咕嘰咕)
看板java
標題[問題] 提昇搜尋的效率
時間Tue Jun 18 13:01:44 2013
各位好
最近遇到一個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
1F：→ eieio:SortedSet 如何？用 subset() 和 headset().size() 06/18 13:16
2F：→ eieio:我的意思是 TreeSet orz 06/18 13:19
3F：→ swpoker:請問有很多物件嗎~例如上萬個?不然100個都沒有什麼差異阿 06/18 13:26
4F：→ realmeat:用TreeSet寫comparator 結案 06/18 13:27
6F：→ sudada:粗估會有上萬 06/18 13:34
7F：推 PsMonkey:上萬筆也還好，我覺得你擔心效率之前要先擔心記憶體 XD 06/18 13:39
8F：→ swpoker:這樣感覺用資料庫算了~頂多放個key就好 06/18 13:44
9F：→ swpoker:大概只有在多執行緒時可能會有問題,但還是先考慮記憶體 06/18 13:48
10F：→ tkcn:10^4 還不用開始擔心記憶體吧? 06/18 13:50
11F：→ popcorny:同意10^4的記憶體不是問題..用tree based list就好了 06/18 13:56
12F：→ swpoker:或許可以分類阿~減少每次搜尋的最大次數 06/18 16:36
13F：推 sbrhsieh:請問此集合需要是排序好的狀態的理由是什麼？ 06/18 20:58
14F：推 luoqr:應該先問你的get range是什麼? 06/18 22:32
※ 編輯: sudada 來自: 114.47.158.194 (06/19 00:10)
15F：→ sudada:因為給使用者get的頻率會高很多 而且抓到的一定是排序過的 06/19 00:13
16F：→ sudada:所以資料在insert時我會先排序 使用者只要下一個range 06/19 00:16
17F：→ swpoker:請問有多執行緒的問題嗎? 06/19 09:39
18F：推 PsMonkey:那在 get 之前判斷有沒有 sort 過就好了阿 06/19 10:22
19F：推 popcorny:保持sort好這總需求很常見啊..這樣get才會有效率啊 06/19 14:05
20F：推 popcorny:keyword: binary search tree 06/19 14:10
21F：→ popcorny:"這樣get才有效率" 應該要改成 "這樣search才有效率" 06/19 14:15
22F：→ sbrhsieh:若 sorted list已把get/search降到理想程度，又何需在 06/19 15:39
23F：→ sbrhsieh:insert/update時取得record的index？特別是get op 次數遠 06/19 15:41
24F：→ sbrhsieh:大於insert/update op 的情況下。 06/19 15:43
25F：→ sbrhsieh:用binary tree怕影響get效能，sorted list也是二元搜尋啊 06/19 15:47
26F：→ sbrhsieh:效能就可接受，這很奇怪ㄋㄟ... 06/19 15:48