作者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