Re: [問題] 提昇搜尋的效率

[PsMonkey (痞子軍團團長)]

※ 引述《sudada (嘰咕嘰咕嘰咕)》之銘言：
: 各位好
: 最近遇到一個sorting的問題
: 假設我有一個List裡面放我自訂的class

  我假設你說的是 java.util.List

: 他必須是個排序好的狀態
: 但是每次有新增或更新資料 我都必須取得那筆資料的index
: 而且使用上get range的使用機率應該會比insert高一點
            ^^^^^^^^^^

  看不懂 @_@

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

  為什麼完全不可行？
  sort 完之後的 search 不會多花時間阿？

  或著說，如果真的很花時間
  那你應該先擔心記憶體爆掉吧？

: 第二
: 跑迴圈用自己的compare方式找到適當的位置
: 直接call insert
: 這樣"感覺上"快很多
: 但是問題出在用List的資料結構的話
: 每次都必須從頭開始 cost應該是O(n)?
: 如果要改進這裡勢必要改資料結構
: 用binary tree又怕會影響整體get的效能
    ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  這個「害怕」的來源我也不是很懂
  但是你不解事，那我們要如何替你（鍵盤）取捨？

  整個需求（在我腦補之後）看起來用 tree 很合理阿？

: 想請問大家會怎麼取捨
: 謝謝

  演算法我不是很懂（招換某 t）
  我只知道「骯髒事不滅法則」
  也就是說，該做的事情就是那些
  用了快樂的演算法可能會快一點，但是還是得作那些事情

  另外，你可能得把你的需求說得更明確一點
  光憑這些... 我覺得我看不太懂，也沒辦法開始算命 [死]


====
我先承認我是來混文章數的 [逃]


--
錢鍾書：    說出來的話
                                                  http://www.psmonkey.org
    比不上不說出來的話
                                                  Java 版  cookcomic 版
  只影射著說不出來的話
                                                  and more......

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 1.34.226.85
→ tkcn:輸兩秒.... 我以為這篇會沒人回的說
→ PsMonkey:早知道你會回我就不寫了 [淚目]
→ Schelfaniel:為何這篇會有 S ?
→ PsMonkey:因為版主也覺得這是來混文章數的 [蓋章][逃]
→ fireslayer:sort就N log N太慢吧 每次都要重新sort
推 if4:S 跟 ! 有什麼區別呀？
→ s3748679:一個是警告 一個是鎖文吧
→ PsMonkey:一個是 s、一個是 sm  [嬌羞]