作者 主題: 請教如何改寫perl程式,以加快執行速度  (閱讀 26252 次)

0 會員 與 1 訪客 正在閱讀本文。

chienwen

  • 懷疑的國中生
  • **
  • 文章數: 37
    • 檢視個人資料
    • 線上字典
我最近在處理一些文字轉換的工作。
我用程式去檢查錯誤。程式碼如下
代碼: [選擇]
package input ;

sub check_chinese_spell {
my $s = join( ", " , @_ ) ;
$s =~ s/\xB6\xD7\xB3\xF8/\xB7\x4A\xB3\xF8/g ; # 匯報 - 彙報
$s =~ s/\xB6\xD7\xBD\x73/\xB7\x4A\xBD\x73/g ; # 匯編 - 彙編
$s =~ s/\xB6\xD7\xA5\x5A/\xB7\x4A\xA5\x5A/g ; # 匯刊 - 彙刊
$s =~ s/\xB6\xD7\xB6\xB0/\xB7\x4A\xB6\xB0/g ; # 匯集 - 彙集
# ..... (有7000筆的比對項目)....
$s =~ s/\xB4\xE5\xA6\xE6/\xB9\x43\xA6\xE6/g ; # 游行 - 遊行
$s =~ s/\xB4\xE5\xBF\xB3/\xB9\x43\xBF\xB3/g ; # 游興 - 遊興
$s =~ s/\xB4\xE5\xBE\xC7/\xB9\x43\xBE\xC7/g ; # 游學 - 遊學
$s =~ s/\xAA\xED\xB5\xFD/\xAA\xED\xC3\xD2/g ; # 表証 - 表證
$s =~ s/\xBF\xEB\xB5\xFD/\xBF\xEB\xC3\xD2/g ; # 辨証 - 辨證
$s =~ s/\xC5\x47\xB5\xFD/\xC5\x47\xC3\xD2/g ; # 辯証 - 辯證

return $s ;
} ;

1 ;


程式碼約7000行 (7000個比對項目)
比對的資料約有 70萬筆。(每筆大約100個中文字)

在 PIII 1.6G, Ram 1.3G 的電腦下,須 6 個小時,程式才能跑完。
不知有沒有其他方法改寫程式,以加快執行速度?
謝謝您
:D

Yamaka

  • 俺是博士!
  • *****
  • 文章數: 4905
    • 檢視個人資料
    • http://www.ecmagic.com
請教如何改寫perl程式,以加快執行速度
« 回覆 #1 於: 2006-05-21 06:42 »
換一台配備好一點的如何  :roll:

chienwen

  • 懷疑的國中生
  • **
  • 文章數: 37
    • 檢視個人資料
    • 線上字典
請教如何改寫perl程式,以加快執行速度
« 回覆 #2 於: 2006-05-21 08:10 »
perl 的精神之一: 就是一件事,不是只能用一種方法去做。
以這個指令來說:
代碼: [選擇]
s///
平常比對個一萬次,一百萬次,一千萬次,都感覺不出它很慢。
可是當比對49億次時 (7,000 x 700,000) 卻要花六小時。
我想,perl 應該會有更有效率的方法,只是我不會而己。

至於,是否要為這個換一台電腦?
以我目前的環境而言,我這台電腦用於架個小型網站,應該是很足夠的,
我覺得最大的瓶頸,除了人腦以外,是在於頻寬的花費,
而不是 cpu 或 ram 上面。

至於那六個小時,當然是在我睡覺的時侯完成。
:D

Yamaka

  • 俺是博士!
  • *****
  • 文章數: 4905
    • 檢視個人資料
    • http://www.ecmagic.com
請教如何改寫perl程式,以加快執行速度
« 回覆 #3 於: 2006-05-21 10:16 »
唔~~
您堅持 Perl 的精神,
嗯...那當我沒說過~~  :o

PS:
如果是我要處理那些資料,
我會將資料做切割,
然後分散到幾台PC做處理...
唔~~ 當我沒 說  8)

asako

  • 活潑的大學生
  • ***
  • 文章數: 221
    • 檢視個人資料
請教如何改寫perl程式,以加快執行速度
« 回覆 #4 於: 2006-05-22 17:05 »
你要不要先判斷行裡有無『匯』這個字,
有的話再判斷取代
沒有的話就跳過。
這樣每行的判斷應會少點,速度也應會快點

damon

  • 管理員
  • 俺是博士!
  • *****
  • 文章數: 4225
    • 檢視個人資料
    • http://blog.damon.tw/
請教如何改寫perl程式,以加快執行速度
« 回覆 #5 於: 2006-05-22 21:52 »
你的演算法有問題吧,這樣一筆一筆比對是最笨的方法,有幾筆就要判斷幾次
你需要的不是語法,是演算法的概念吧
尤其是怎麼減少判斷的時間的部份,好好想想怎麼樣比較快吧
例如如果第一個字是匯的話就丟到比對匯字的部份
或是用第二個字來比對,或是以最常出錯的字來比對,先比對最容易出錯的部份再來比對不容易出錯的部份,這都是你的演算法可以思考的方向
如果你有辦法利用統計資料把哪些字容易打錯,哪些字不容易打錯
你的演算法可以做成中文的拼字檢查了

被騎上班的老

  • 酷!學園 學長們
  • 活潑的大學生
  • ***
  • 文章數: 360
    • 檢視個人資料
請教如何改寫perl程式,以加快執行速度
« 回覆 #6 於: 2006-05-24 02:31 »
演算法的確有很大的關係。

我的建議是將 pattern  存成資料庫然後排序,資料庫一 load 到記憶體就不必重新讀入,另外有排序的搜尋絕對要比從頭到尾的比對快。
目前你的程式一行一次比對,就要重新將變數 load 到記憶體,比對然後執行, I/O 的時間就拖長

其次,只需要執行需要的轉換。意思是說其實你轉換一次的時候,如果比對不成功。 7000 行全部白跑了,比對成功的話 也有 6999 行白跑了。

所以應該先檢查是否在 pattern 比對資料庫中,否的話就 return 。是的話就執行比對的程式。

對阿,寫到這裡突然想到,學校裡面上過,資料跟程式應該分開啊! 因為資料會異動,根本不應該放在程式裡面啊。資料放在資料庫,你的程式大小就會減少, cycle time 也就跟著減少了啊。

加油加油! 你的經驗會是我們一個重大的課題。

chienwen

  • 懷疑的國中生
  • **
  • 文章數: 37
    • 檢視個人資料
    • 線上字典
請教如何改寫perl程式,以加快執行速度
« 回覆 #7 於: 2006-05-27 09:24 »
網路上有一些好用的字典資料庫, 例如:

http://www.freebsd.org/cgi/pds.cgi?ports/chinese/dictd-database
http://stardict.sourceforge.net/Dictionaries_zh_TW.php

其中, 有一些正體中文的文件, 是翻譯自簡體中文.
但我發現有一些文字轉換之後, 會有錯誤.
我想把這些字典資料庫重新轉換, 更正這些錯誤.
因此, 才有這次的問題.

我是用 perl 的套件做正簡中文轉換:
代碼: [選擇]
use Encode ;
use Encode::HanConvert ;


我發件這個套件, 遇到某些字, 會轉換錯誤, 一共有 880 個中文字.
錯誤的原因是: 有些簡體中文字, 會對應兩個以上的正體中文字.

我用這 880 個中文字, 查詢教育部的辭典, 一共查出約 7000 個辭彙,
這 7000 個辭彙, 就是這個問題的比對項目.

我依據學長姊的指導, 將程式碼稍加修改如下:
代碼: [選擇]
package input ;

sub check_chinese_spell {
my $s = join( ", " , @_ ) ;

if ($s =~ /\xB6\xD7/) { # 匯彙
$s =~ s/\xB6\xD7\xB3\xF8/\xB7\x4A\xB3\xF8/g ; # 匯報 - 彙報
$s =~ s/\xB6\xD7\xBD\x73/\xB7\x4A\xBD\x73/g ; # 匯編 - 彙編
$s =~ s/\xB6\xD7\xA5\x5A/\xB7\x4A\xA5\x5A/g ; # 匯刊 - 彙刊
$s =~ s/\xB6\xD7\xB6\xB0/\xB7\x4A\xB6\xB0/g ; # 匯集 - 彙集
# ...略...
} ;
# ...略...
return $s ;
} ;

1 ;

程式的速度大為提升, 重原先的 6~7 小時, 降到只剩 55 分鐘.
 (轉換同一個 70 萬筆的字典資料庫)

至於, 學長姊提到用資料庫排序, 再 load 到記憶體的方法,
目前我還沒有什麼概念, ... 繼續研究中 ...

這個 FreeBSD port 的 source 是用 perl 去轉換的.
我為了轉換的問題, 才用心去學 perl.
(也才體會出 perl 在文件處理上的功能這麼強)
一直以為自己語法沒學好, 猛往語法鑽,
"需要的不是語法,是演算法的概念吧"
原來演算法也是這麼重要!!
:D

被騎上班的老

  • 酷!學園 學長們
  • 活潑的大學生
  • ***
  • 文章數: 360
    • 檢視個人資料
請教如何改寫perl程式,以加快執行速度
« 回覆 #8 於: 2006-05-27 22:11 »
恭喜你,也感謝你的回報。其實我們有時候只是理論者,不是實作者。理論需要實作者的驗證,讓我們覺得讀的書有用。

其實這也是個良性循環,有人貢獻方法,有人貢獻實驗結論,然後大家都可以從中間學到經驗。這就是 study-area 的精神最佳應證。

這個討論真是經典,可否建請板主置頂成為這個板的好榜樣。

被騎上班的老

  • 酷!學園 學長們
  • 活潑的大學生
  • ***
  • 文章數: 360
    • 檢視個人資料
請教如何改寫perl程式,以加快執行速度
« 回覆 #9 於: 2006-05-29 00:53 »
data.txt

代碼: [選擇]
\xB6\xD7\xB3\xF8        \xB7\x4A\xB3\xF8
\xB6\xD7\xBD\x73        \xB7\x4A\xBD\x73
\xB6\xD7\xA5\x5A        \xB7\x4A\xA5\x5A
\xB6\xD7\xB6\xB0        \xB7\x4A\xB6\xB0
\xB4\xE5\xBF\xB3        \xB9\x43\xBF\xB3
\xB4\xE5\xBE\xC7        \xB9\x43\xBE\xC7
\xAA\xED\xB5\xFD        \xAA\xED\xC3\xD2
\xBF\xEB\xB5\xFD        \xBF\xEB\xC3\xD2
\xC5\x47\xB5\xFD        \xC5\x47\xC3\xD2

以 tab 分離,前面的是 key 也就是需要轉換的 pattern 後面是 value 也就是需要轉換成的文字。

a.pl

將文字檔轉換成一個 dbfile (data.db) 也就是說將程式與資料分開。你可以將資料存在另外一個文字檔,一方面增加資料的時候不必去修改程式另一方面可以縮小程式。

轉換文字檔成資料庫(data.db)只需要作一次,如果 data.txt 沒有異動不需要重做這個轉換。此外這個資料庫是一個排序過的資料庫,搜尋時間應該會縮短。

代碼: [選擇]
#!/usr/bin/perl

#use warnings;
#use strict;
use DB_File;

$DB_BTREE->{'compare'} = sub {
        my ($key1, $key2) = @_;
        "\L$key1" cmp "\L$key2";
};

# Declaration
our (%hash, $key, $value);
my $DB_FILE = "data.db";
my $DATAFILE = "data.txt";
my %hash;
my $line;

# delete $DB_FILE
unlink $DB_FILE ;
#
open(DATA, $DATAFILE);
tie(%hash, "DB_File", $DB_FILE, O_RDWR|O_CREAT, 0666, $DB_BTREE)
  or die "Cannot open DB_FILE $DB_FILE : $!\n";
print "Before Sort \n\n";
while($line = <DATA>)
{
        chomp($line);
        ($key, $value) = split(/\t/, $line);
        print $key, " -> ", $value, "\n";
        $hash{$key} = $value;
}



print "\nAfter Sort\n\n";
while(my($key, $value) = each %hash)
{
        print  $key, " -> ", $value, "\n";
}

# close file
untie % hash;
close DATA;



從 dbfile 比對 c.pl

代碼: [選擇]
#!/usr/bin/perl

use warnings;
use strict;
use DB_File;
our (%hash, $key, $value);

my $DB_FILE = "data.db";

tie(%hash, "DB_File", $DB_FILE, O_RDWR, 0666, $DB_BTREE)
        or die "Cannot open file '$DB_FILE'  $!\n";

$key = $ARGV[0];
print $key,"\n";

$value = $hash{$key};

print $value, "\n";
untie %hash;



例如  ./c.pl "\xB6\xD7\xBD\x73" 會回應

代碼: [選擇]
\xB6\xD7\xBD\x73
\xB7\x4A\xBD\x73



這是一個資料庫查詢的範例,使用時要比較快的話要把螢幕輸出,如 print 之類的指令關掉。

所以你的程式在比對的時候可以改成去查詢資料庫,如果有傳回值就可以執行轉換這個傳回值。要是沒有就可以 return,這樣的話就可以只比對一次就可以。

詳情可以找 perl DB_File 的文章

相殺

  • 可愛的小學生
  • *
  • 文章數: 3
    • 檢視個人資料
請教如何改寫perl程式,以加快執行速度
« 回覆 #10 於: 2006-05-30 02:39 »
一點淺見可以試試

把要比對的資料拆開比對例如[匯報][匯x]...[遊行][游x]....
先將第一個字的部分宣告成{"匯","游"....}陣列A
第一個字對應的部分宣告成{"彙","游"....}陣列B
第二個字的部分宣告成{"報","編","刊","行","興","學",...}陣列C
第一個迴路搜尋第二個字的旗標值(在該陣列內是第幾個元素)=x
第一個迴路找不到時不執行第二個迴路的搜尋
第二個迴路搜尋第一個字的旗標值(在該陣列內是第幾個元素)=y
然後在搜尋結果為真時
printf("%s%s",B[y],C
  • );


strcat(sa,B[y]);
strcat(sb,C
  • );

strcat(s,sa);
strcat(s,sb);

執行搜尋前必先將資料取出到記憶體內再執行而且不要在每筆比對都顯示
(搜尋成功才顯示)因為硬碟跟螢幕跑不快呀

stlee

  • 鑽研的研究生
  • *****
  • 文章數: 817
    • 檢視個人資料
請教如何改寫perl程式,以加快執行速度
« 回覆 #11 於: 2006-10-11 00:32 »
這個問題是不是要將大陸的簡體字網頁透過程式翻譯成繁體中文的阿
如果不是的話下面不用看了

如果是的話可以試試"查表法"
因為中文是以雙位元表示一個中文,且第一個位元是在ASCII的128-255之間的值
所以透過字元分析對照表格(需自行創建)索引到需要的結果
而且嚴格來說"查表法"並不是如二元搜尋的演算法則而是以資料表格索引對照的表格所以速度非常快,在本問題的資料量來說1秒內就能找出來了吧,詳細部分因為我並不確定問題本身用途為何所以不再多說,而且我看這個問題很久了所以也認真想了一個解決方案,不過目前只能翻到兩個字的句子(2維陣列)有興趣的話大家一起討論討論
程式是人寫的,別讓工具的限制成為您想像力的極限
~程式中最重要的部份應該是註解而不是程式碼,這是因為解讀註解一定比解讀程式碼簡單
~程式寫好後約一個月就會忘的差不多了,所以花點時間把註解寫好至少能讓自己(或別人)看的懂當初在寫什麼

TomUbuntu

  • 可愛的小學生
  • *
  • 文章數: 6
  • 性別: 男
    • 檢視個人資料
這隻程式應該有規律性的東西,把它找出來就是演算法了~~~~~針對這個演算法去加速就行了XD ;D ;D ;D ;D