Re: [問題] 提昇搜尋的效率
※ 引述《sudada (嘰咕嘰咕嘰咕)》之銘言：
: 各位好
: 最近遇到一個sorting的問題
: 假設我有一個List裡面放我自訂的class
: 他必須是個排序好的狀態
: 但是每次有新增或更新資料 我都必須取得那筆資料的index
: 而且使用上get range的使用機率應該會比insert高一點
: 目前我有兩種想法
: 第一
: 每次丟資料進去都call一次sort
: 不過這樣沒辦法直接知道我剛剛新增的那筆資料
: 到底會被丟到哪裡去
: 所以sort完以後還要再抓一次index?
: 這種方法我覺得完全不可行......
: 第二
: 跑迴圈用自己的compare方式找到適當的位置
: 直接call insert
: 這樣"感覺上"快很多
: 但是問題出在用List的資料結構的話
: 每次都必須從頭開始 cost應該是O(n)?
: 如果要改進這裡勢必要改資料結構
: 用binary tree又怕會影響整體get的效能
: 想請問大家會怎麼取捨
: 謝謝
這裡有個叫 TreeSet 的東西 有個 method 應該有用:
NavigableSet<E> headSet(E toElement, boolean inclusive)
Returns a view of the portion of this set whose elements are less than (or
equal to, if inclusive is true) toElement.
也就是說 用 headSet 拉出來再貼 size 就能得到 index 了
或許你可以改用 TreeSet 來做事 (它的底層是紅黑樹, 插入刪除尋找都是對數時間)
range query 也有 subSet 可以用
--
'Oh, Harry, don't you see?' Hermione breathed. 'If she could have done
one thing to make absolutely sure that every single person in this school
will read your interview, it was banning it!'
---'Harry Potter and the order of the phoenix', P513
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.30.32
推
06/18 13:56, , 1F
06/18 13:56, 1F
→
06/18 13:58, , 2F
06/18 13:58, 2F
→
06/18 13:59, , 3F
06/18 13:59, 3F
→
06/18 14:00, , 4F
06/18 14:00, 4F
→
06/18 14:03, , 5F
06/18 14:03, 5F
→
06/18 14:05, , 6F
06/18 14:05, 6F
討論串 (同標題文章)