Re: [問題] 字串比對的效率

[AmosYang (LetMeGoogleThatForYou)]

※ 引述《ken915007 (Ken_Wu)》之銘言：
: 目前正在使用java實作data mining的方法...
: 實作中，在想一個問題，就是字串比對
: 怎樣的字串比對才有效率?

: 推 qrtt1:看能不能在資料前處理時統一成數字, 要結果再轉成字串        12/05 08:20
: → ken915007:若item要是多的話…這樣轉數字~最後在反轉~也是要時間    12/05 12:12
: → ken915007:酷!! 難道不能這樣用?還是比較不好??                    12/05 12:14
: → qrtt1:處理簡單的型別絕對比物件來的有效率                        12/05 13:41
: → qrtt1:關聯用 fp-tree 比較有效率的說 :P                          12/05 13:43
: 嗯! 我有看過這些方法~但精準度apriori會比較高點...所以才想用apriori，
: 但缺點就是要重覆掃資料...
: 有點離題了^^ 重點不是這演算法= =
: 我想知道對於字串的比對~像上面的範例~大家會用什麼方法去比對是否有出現過

如果 input data 沒有可 exploit 的性質

且 algorithm 一定得寫成原文中所述的話

那我目前只能想到
「確認所有的 String 比對使用 hashCode 以 fail-fast」

這就要去讀 JDK source code 去看 containsAll()

及 String.Equals 的實作

還有 String.hashCode 有無把 hashCode cache 起來

如果沒有的話，可以把 String 包成另一個 class 再實作 hashCode cache

class StringAndCachedHashCode
{
  Int32? hashCode = null;
  String string;

  internal StringAndCachedHashCode(String string)
  {
    this.string = string.
  }

  internal Int32 hashCode()
  {
    if (hashCode.HasValue)
      return hashCode.Value;
    else
    {
      hashCode = string.hashCode();
      return hashCode.Value;
    }
  }
}

再要更上層樓的話，就得確認 containsAll() 有實作 fail-fast

且還可以對 input data 做 statistical analysis

看能不能讓 containsAll() fail-fast-er :p
(例: always 從最稀有的 element 開始 check 'containsAll()')



另外一件很重要的事，這裡碎碎念一下

performance tuning 與任何其他的 scientific method 沒有不一樣的地方

perf tuning 的新手最常犯的一個錯誤就是瘋狂的把所有能想到的手段都試作

卻沒有嚴謹地檢視 ROI (return of investment)

我會建議原 po 這樣做:

1. Identify a set of well-understood test data.
2. Set your perf. tuning goal
3. Identify a method to measure against your perf. goal.
4. Watch your code under a profiler and
   identify the type of improvment that can bring you the biggest ROI
5. Implement the improvement
6. Test your new implementation with the test data from step#1.
7. Measure perf. improvement with the method from step#3.
8. Only if you have not met your perf. tuning goal, go back to step#4.
   Otherwise, call it a day.

當然，如果沒有 deadline 或有無限的時間…以上方法自然不適用… XD

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 65.87.177.87
※ 編輯: AmosYang        來自: 65.87.177.87         (12/05 17:33)
→ AmosYang:呃 那段code迷迷糊糊的寫成C#了 懶得改了 看得懂就好 :)
→ ken915007:呵呵~感謝^^  剛剛在看code想說怎麼看起來怪怪的= =
→ ken915007:我在想你的ROI是對哪部份?還有deadline是指哪部份?
推 ken915007:我才疏學淺…會比較不快理解~請多包含^^
→ ken915007:                                 涵
ROI := return of investment 中文可以翻作 投資報酬 ?
deadline -- 作業/報告/老闆耐心 的期限

易言之，最後這一段我想講的是「perf. tuning 的 engineer practice」

有的時候一些 tweak 在理論上會有幫助

但實質上效益卻不大，且要花很多時間去實作
這就是所謂的 low ROI

這就只能靠良好的 engineer practice / scientific method 去驗證

通常 80/20 rule 很少出錯；在學校裡教導的是 software engineering
但在現實生活中能養活人的是 software business
 perfect solution 的 ROI 多半不如 something just good enough
有些道理我也無法三言兩言說得很清楚 :)
反正如果沒有 deadline 的話一切好談 XD

※ 編輯: AmosYang        來自: 65.87.177.87         (12/05 18:24)
※ 編輯: AmosYang        來自: 65.87.177.87         (12/05 18:25)
推 ken915007:ROI我知道是什麼…只是不明你所講的是哪部分而已^^~感謝