這個去除重覆字元的函數, 還能再optimize 嗎?

Question

各位大大:這是一個用來去除文章裡面重覆出現字元的函數, 目前效能不是很理想,是否有高手能人可以幫忙看一下還有沒有更好的演算法來提升它的效能.目前的速度是: 一篇二萬六千字的文章, 跑一百次大約花去2.5~2.8秒.(ps. 平台是Dothan 2.26GHz! 如果用P4-3.2GHz 大約是3.5~3.9秒)    Public Function RemoveDupeChar(ByVal arrString() As Char) As Char()        \'=======================================        \'公用方法: 清除字元陣列中重覆的字元        \'傳入值:        \'           arrString(): 要排序的陣列        \'傳回值:        \'           Char()字元陣列        \'2004/11/04 by simon        \'2005/01/26 revised by simon        \'2006/06/19 revised by simon        \'=======================================        Dim arrTemp() As Char        ReDim arrTemp(arrString.GetUpperBound(0))        \'\'第一代演算法, 2004/11/04 by simon        \'\'將來源陣列中的字元逐一取出,檢查是否存在新陣列中,        \'\'若不在則放入, 若存在則忽略        \'Dim charTemp As Char        \'Dim i As Integer        \'For Each charTemp In arrString        \'    If Array.IndexOf(arrTemp, charTemp) = -1 Then        \'        arrTemp(i) = charTemp        \'        i += 1        \'    End If        \'Next        \'第二代演算法, 2005/01/26 revised by simon        \'將來源字元陣列組回成為字串        \'將字串中的字元逐一取出放入新陣列, 並回頭刪除來源字串中的所有這個字元        Dim i As Integer = 0        Dim strTemp As String = arrString        Do While strTemp.Length > 0            arrTemp(i) = strTemp.Chars(0)            strTemp = Replace(strTemp, arrTemp(i), "")            \'strTemp = strTemp.Replace(arrTemp(i), "")            i += 1        Loop        \'第三代演算法(ps. 因為performance還是很差)        \'???        ReDim Preserve arrTemp(i)        Return arrTemp    End Function

To明忠大大:
這裡有三篇純文字檔可以下載: http://*****/qw5ao
由於真正要存的產品開發資料較為敏感, 不宜外流.
在此抓了三篇網路上看到的文章給您作為測試用;
分別為一萬多字, 二萬多字, 三萬多字.

您的MyCount() 函數看來不錯, 計算方向和小弟小有不同,
請問跑起來效能如何? 用二篇上萬字串跑一百次大約幾秒?

我看到明忠大大會PHP 是嗎?
我查到PHP有一個函數Similar_Text(), http://linux.tnc.edu.tw/techdoc/banic/string/similar_text.html
不知道是不是在做同樣這件事? 效能如何?

對了, 依你6/1到現在的速度, 應該下星期就會有HTML精靈了吧. ^_^
simon是5/8加入的, 一開始沒有很認真, 所以也是花了大約一個月才突破2500點的關卡, 然後就直接升到實習生一級.

To WJS大大:
你這段code 的效能瓶頸應該是卡在 T2 = T2 + Abs((N2 - Len(S2)) - (N1 - Len(S1))) 這個字串的連接部份.
如果先把字串打成字元陣列, 處理完重複字元之後再接回成為字串, 效能應該會提升不少 ^_^

小弟在此感謝各位大大共襄盛舉,能集各路英雄好漢至此討論,小弟感到相當榮幸
各位所提到的方向,讓小弟受益不少
相信這二天來這版腦力激盪下,各位也應該從其他人身上得到許多靈感
這次答案小弟不想交付投票,因為我想來投票的網友程度,能區分各位大大的功力的可能不會太多
小弟在此僅以對自己幫助最大的答案來選,對其他大大還是致上十二萬分的謝意

simon最後用的方式是: 開一個65535的integer(),用來代表unicode二個byte的table,分別把A字串和B字串各掃過一次,並將每一字對應字碼填入integer(),每填入一次就計數加一.
最後再用另一個陣列來統計字元出現的次數.
在我的NB 上面,用"原來我不帥" 和"星座搏感情"比對一百次,只花了0.4 秒不到! 實際套到資料庫去,每秒可以比到四百多篇上下.

sample code在這裡,小弟不敢藏私,僅供各位參考.
http://*****/jxydg

Answer 1

你可以放兩篇文章上來做測試資料嗎...?

2006-06-20 20:51:03 補充：
恩...
我把我腦中的想法，寫成了程式...用VB寫的(因為我實在不太會寫演算法)
觀看版：
http://www.wretch.cc/blog/ArrackCode&article_id=7002505
方便複製版：
http://blog.xuite.net/zeng.mz/program/6920946
(因為我沒有HTML精靈可以用～Yahoo我恨你)

我把Replace的結果去掉，不存入動態陣列，而只比對兩個文章較小的那個數字，就存入變數中，最後在計算度回傳...

我初步測試的結果，是勉勉強強還可以(我還怕有BUG...)
不過應該還是有待討論，還可以在更好:D

2006-06-20 23:52:31 補充：
恩...PHP的部份，看了介紹感覺好像是用來比相似度的沒錯，明天來試試看:D

2006-06-21 00:02:56 補充：
效能宇宙無敵差/___\兩篇比對一百次，要17秒多....(我的是Intel Celeron 2.66)再來思考一下好了

2006-06-21 00:25:50 補充：
補充一下，我比對星座搏感情.txt將VB程式移植到Linux和Mac OS X.txt更新一個小BUG後大約是13秒左右更新的程式一樣在上面的網址

2006-06-21 00:30:36 補充：
http://home.yahoo.com.tw/holddragon/SampleCode.rar

2006-06-21 10:00:29 補充：
今天找時間測試了一下 Similar_Text()，好像不太正確，去查了一下資料是給英文用的，對於中文好像沒有實用性因為我比對了"一二三四五"跟"中中中中中"，出來的結果是40%我拆開內碼來看，估計推算應該是當作英文使用，用1Byte去比對的00000000h: A4 40 A4 47 A4 54 A5 7C A4 AD ; 一二三四五00000010h: A4 A4 A4 A4 A4 A4 A4 A4 A4 A4 ; 中中中中中

2006-06-21 16:31:07 補充：
恩，WJS大大跟我第一次想的時候犯了同樣的錯...
如果S在S1中搜尋得到，在S2中搜尋不到
那麼相同字元應該是0，
可是如果只是
T2 = T2 + Abs((N2 - Len(S2)) - (N1 - Len(S1)))
還是會把相同字元計算進去

參考之

2006-06-21 17:24:24 補充：
我的程式有錯誤...修改在http://blog.xuite.net/zeng.mz/program/6920946中間有字打錯=_=，下載點晚點在更新

Answer 2

To WJS大大:
你這段code 的效能瓶頸應該是卡在 T2 = T2 + Abs((N2 - Len(S2)) - (N1 - Len(S1))) 這個字串的連接部份.
如果先把字串打成字元陣列, 處理完重複字元之後再接回成為字串, 效能應該會提升不少 ^_^

Answer 3

'我的也不理想,這兩篇文章跑100次要23秒XD,由於有把換行字元一併計算,故答案跟明忠大大有點不一樣!!Function Test(ByVal S1 As String, ByVal S2 As String) As Single    Dim S$, St$, T1&, T2&, N&, N1&, N2&        T1 = Len(S1) + Len(S2)        Do      N1 = Len(S1): N2 = Len(S2)      If N1 = 0 Then Exit Do      If N2 = 0 Then Exit Do      If N2 < N1 Then         St = S1: S1 = S2: S2 = St         N = N1: N1 = N2: N2 = N      End If      S = Left$(S1, 1)      S1 = Replace$(S1, S, ""): S2 = Replace$(S2, S, "")      T2 = T2 + Abs((N2 - Len(S2)) - (N1 - Len(S1)))    Loop    Test = Format((T1 - (T2 + Len(S1) + Len(S2))) / T1, "0.000")End FunctionPrivate Sub Command1_Click()    Dim A() As Byte, S1$, S2$, I%, H!        ReDim A(FileLen("C:\星座搏感情.txt") - 1)    Open "C:\星座搏感情.txt" For Binary As #1    Get #1, , A    Close #1    S1 = StrConv(A, vbUnicode)    ReDim A(FileLen("C:\原來我不帥.txt") - 1)    Open "C:\原來我不帥.txt" For Binary As #1    Get #1, , A    Close #1    S2 = StrConv(A, vbUnicode)    D = Timer    For I = 1 To 100        H = Test(S1, S2)    Next    Print H, Timer - DEnd Sub

2006-06-21 17:51:36 補充：
To:明忠大大
我的T2是表兩字串無交集的數量,故要計算相似率才要以總字元數-T2-S1剩下的字元數-S2剩下的字元數/總字元數^^

2006-06-21 17:59:29 補充：
To:憂兄
嗯!我再想想看有無別種方式,但T2是Long型態並非String^^

Answer 4

不才心中已有若干想法，惟非一時可使他人理解。希藉由問題發問回復方式能得一一化解，不知各位意下如何？

問題1：對一篇文章之重點加以摘要萃取以利有效縮小比較資料數量，是否同意摘要萃取器(abstractor)作為嚐試之新方向呢？

後續之問題將待前面之問題已有回復後，再行提出！