Re: [問題] 提昇搜尋的效率
其實問題有點模糊
不過我想這應該是程式語言跟java的問題
因為c都是陣列拉~指標啦~等等可以讓你碰到底層的演算法
可是java並沒有這樣子
所以如果你一開始就學資料結構 學C
再來用java 會搞的很亂
實際上除非你自己寫套件
不然像我
沒學過演算法
沒學過資料結構
沒學過C
不知道什麼是指標
不知道什麼位移
更別說什麼tree了
對於只會打電動其他什麼都不會的情況下
一開始就碰java
然後我就照著java.util裡面提供的套件去用
老實說,我根本就不知道裡面到底在幹麻!!!
其實我學習的順序剛好跟大家相反
在這個問題
首先要釐清的是
insert get-->這些方法的定義是什麼?
物件的定義是什麼?
那筆資料的index->定義為何?
所以我只好公堂之上大膽假設一下
你的get是
1.XXObject get(); 這樣嗎?
FIFO? LIFO?
還是
2.XXObject get(XXType index);這樣嗎
index是???
先定義好模組的行為
再來討論一下實作的方式跟細節
因為往往問題確定了,其解決的實作竟然是不可思議的簡單!!!
所以你願意分享一下你所規劃的介面嗎
(順便要有註解喔)
PS.在這裡我只用我的想法來寫測試案例
(所以想法肯定會跟原PO不同)
XXXList xxxlist = instanceofXXXList();
xxxlist.insert(XXXBeanA("id022"));
String key = "id01234";
XXXBeanA bean_null=xxxlist.getByKey(key);
Asserts.equalsNull(bean_null);
xxxlist.insert(XXXBeanA("id6789"));
xxxlist.insert(XXXBeanA("id649"));
xxxlist.insert(XXXBeanA("id99789"));
Asserts.equals("id99789",xxxlist.getLast().getId());
Asserts.equalsNotNull(xxxlist.getByKey("id649"));
在這裡我定義了
void insert(XXXBeanA bean);
XXXBeanA getBykey(String key);
XXXBeanA getLast();
三種行為及其相關的IO參數
(以上我都還沒實作,保證編譯全部紅字!!!)
然後我就來找找到底用什麼方法會更有效率呢?
所以這種問題可以用TDD來思考喔!!!!!
然後getLast()真的很簡單!!!
因為
XXXBeanA last_beanA = null;
public void insert(XXXBeanA bean){
//放到按照演算法的容器裡面
_handle(bean);
//放置最後
last_beanA=bean;
}
public XXXBeanA getLast(){
return last_beanA;
}
得到最後新增的物件用這樣方式就可以達到了
連什麼演算法都不用!!!
以上的操作並沒有考慮thread safe喔
※ 引述《sudada (嘰咕嘰咕嘰咕)》之銘言：
: 各位好
: 最近遇到一個sorting的問題
: 假設我有一個List裡面放我自訂的class
: 他必須是個排序好的狀態
: 但是每次有新增或更新資料 我都必須取得那筆資料的index
: 而且使用上get的使用機率應該會比insert高一點
: ^^^
: 這邊修正一下...
: 目前我有兩種想法
: 第一
: 每次丟資料進去都call一次sort
: 不過這樣沒辦法直接知道我剛剛新增的那筆資料
: 到底會被丟到哪裡去
: 所以sort完以後還要再抓一次index?
: 這種方法我覺得完全不可行......
: 第二
: 跑迴圈用自己的compare方式找到適當的位置
: 直接call insert
: 這樣"感覺上"快很多
: 但是問題出在用List的資料結構的話
: 每次都必須從頭開始 cost應該是O(n)?
: 如果要改進這裡勢必要改資料結構
: 用binary tree又怕會影響整體get的效能
: 想請問大家會怎麼取捨
: 謝謝
--
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 163.29.29.131
※ 編輯: swpoker 來自: 163.29.29.131 (06/19 14:50)
→
06/19 14:51, , 1F
06/19 14:51, 1F
→
06/19 15:19, , 2F
06/19 15:19, 2F
推
06/19 20:39, , 3F
06/19 20:39, 3F
→
06/20 09:15, , 4F
06/20 09:15, 4F
討論串 (同標題文章)