作者 主題: 請問重複字串比對問題  (閱讀 7697 次)

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

dark

  • 俺是博士!
  • *****
  • 文章數: 1581
    • 檢視個人資料
請問重複字串比對問題
« 於: 2006-05-09 21:15 »
若今天有一變數
str="12345678,43244234,43254356,54454345,45435345,34235356,";

每 8 位數字以 "," 分欄位
共有數萬欄 ... 所以難免會有重複字串

請問 ..
以何種方式找出重複的字串最快呢 ??

小弟想到的是
awk 'BEGIN{RS="[,\n]+";x=""}{if(x !~ $0){ x=$0","x }else{print $0}}END{print "no_repeat="x}' /tmp/str_tmp.txt


沒想到 5 萬欄跑了 2 小時 .....  :cry:

湯姆貓

  • 活潑的大學生
  • ***
  • 文章數: 475
    • 檢視個人資料
請問重複字串比對問題
« 回覆 #1 於: 2006-05-10 00:47 »
我只想到用資料庫UNIQUE的方式來做,
把數字字串通通丟到資料庫中,
如果有重複會出現無法寫入資料,
再把重複的資料另外存.

很爛的方法....

Yamaka

  • 俺是博士!
  • *****
  • 文章數: 4913
    • 檢視個人資料
    • http://www.ecmagic.com
請問重複字串比對問題
« 回覆 #2 於: 2006-05-10 00:49 »
引述: "湯姆貓"
我只想到用資料庫UNIQUE的方式來做,
把數字字串通通丟到資料庫中,
如果有重複會出現無法寫入資料,
再把重複的資料另外存.

很爛的方法....


如果陣列有檢查資料是否已存在的功能,
如 PHP 的 in_array 之類的, 就不必動用到資料庫 ...

dark

  • 俺是博士!
  • *****
  • 文章數: 1581
    • 檢視個人資料
請問重複字串比對問題
« 回覆 #3 於: 2006-05-10 00:54 »
上面主要是每次比對 .. x 值就增加
速度越來越慢

想到可以利用能以字串當索引的陣列 ...

當重複時   只是二次做賦予值的動作
再把索引值抓出來
代碼: [選擇]
<?php
$str_replace
=str_replace&#40;",","\"=>\"\",\"",$str&#41;;
$str_replace=substr&#40;$str_replace,0,strrpos&#40;$str_replace,","&#41;&#41;.'&#41;;'."\n";
$fp=fopen&#40;"str.tmp","a"&#41;;
fwrite&#40;$fp,'<?php'."\n".'$all_array=array&#40;"'&#41;;
fwrite&#40;$fp,$str_replace&#41;;
fwrite&#40;$fp,"\n\n".'?'.'>'&#41;;
fclose&#40;$fp&#41;;

include_once&#40;"str.tmp"&#41;;

$title=array_keys&#40;$all_array&#41;;
foreach&#40; $title as $one_title => $old_title &#41;&#123;
echo $old_title."\n";
&
#125;
unlink &#40;"str.tmp"&#41;;
?>


a=$(date) ; php -q str.php > /dev/null ; echo $a ; date
三 5月 10 00:35:44 CST 2006
三  5月 10 00:35:47 CST 2006

... 3 秒鐘

只不過還有一點 .. 需寫入暫存檔再  include 進來
使用完還要刪除  ..... 這似乎有點麻煩

不知道有沒有其他把 "變數值" 變成陣列的方式呢 ?? ..... 還請指點

Yamaka

  • 俺是博士!
  • *****
  • 文章數: 4913
    • 檢視個人資料
    • http://www.ecmagic.com
請問重複字串比對問題
« 回覆 #4 於: 2006-05-10 01:01 »
引述: "dark"
只不過還有一點 .. 需寫入暫存檔再  include 進來
使用完還要刪除  ..... 這似乎有點麻煩

不知道有沒有其他把 "變數值" 變成陣列的方式呢 ?? ..... 還請指點


用 eval()

Darkhero

  • 酷!學園 學長們
  • 俺是博士!
  • *****
  • 文章數: 3728
  • 性別: 男
    • 檢視個人資料
    • ㄚ凱隨手紀
請問重複字串比對問題
« 回覆 #5 於: 2006-05-10 04:05 »
我這樣跑....從產生數字陣列,變成字串,然後從字串去處理,最後比對結果輸出,前後不到5秒吧...

不知道這樣的程式碼能不能達到你的要求呢?

代碼: [選擇]
[darkhero@home test]$ more test.php
<?
## 產生陣列
for($i = 1;$i <= 50000;$i++){
    $list[] = rand(10000000,99999999);
}
$str = implode(",",$list);

## 正式開始處理
$myArray = explode(",",$str);
$checkArray = array();
foreach($myArray as $val){
    $checkArray[$val]++;
    if($checkArray[$val] > 1){
        echo $val.":".$checkArray[$val]."\n";
    }
}
?>
希望我們的討論是為了把問題解決,而不是爭論誰對誰錯.
『灌水才是重點,發文只是順便』
『我寧可讓不會釣魚的工程師餓死,也不想讓會餓死的工程師去攪沉公司....』
Blog: http://blog.darkhero.net/
秘密基地: http://www.darkhero.net/comic/
目前服務的網站: http://www.libook.com.tw/

Darkhero

  • 酷!學園 學長們
  • 俺是博士!
  • *****
  • 文章數: 3728
  • 性別: 男
    • 檢視個人資料
    • ㄚ凱隨手紀
請問重複字串比對問題
« 回覆 #6 於: 2006-05-10 04:23 »
剛剛又改了一下,因為不知道你會從那讀取那麼多資料進來。
我就先假設是從資料檔案讀取的。格式就是 8個數字,然後用『,』分格

所以用下面這個程式碼好了
代碼: [選擇]

<?
$fp = fopen('str.tmp','r');
$fstat = fstat($fp);

$checkArray = array();
while($str = fgetcsv($fp,$fstat[size])){
    $myArray = $str;
    foreach($myArray as $val){
        $checkArray[$val]++;
        if($checkArray[$val] > 1){
           echo $val.":".$checkArray[$val]."\n";
        }
    }
}
?>



str.tmp 內的格式如下:
代碼: [選擇]

more str.tmp
19002339,81609184,50817982,.... 共十萬筆~
希望我們的討論是為了把問題解決,而不是爭論誰對誰錯.
『灌水才是重點,發文只是順便』
『我寧可讓不會釣魚的工程師餓死,也不想讓會餓死的工程師去攪沉公司....』
Blog: http://blog.darkhero.net/
秘密基地: http://www.darkhero.net/comic/
目前服務的網站: http://www.libook.com.tw/

dark

  • 俺是博士!
  • *****
  • 文章數: 1581
    • 檢視個人資料
請問重複字串比對問題
« 回覆 #7 於: 2006-05-10 09:15 »
多謝各位大大指點

查了 eval() ...  昨晚睡前試好久 ..... 小弟愚魯 ... 怎麼試都試不出來 :cry:
-----

這個是一個程式處理一半的字串 ... 所以不會這時輸出
目的是要每一欄位不要有重複出現 ...

查了一下Darkhero 大所提的 explode();
回傳值是一個陣列 ...

真是多謝 Darkhero 大大的指點 ...  :wink:

thyme

  • 老人組
  • 俺是博士!
  • *****
  • 文章數: 1281
    • 檢視個人資料
請問重複字串比對問題
« 回覆 #8 於: 2006-05-10 09:26 »
這樣看看可行否
cat /tmp/tmp_str.txt | tr "," "\n" | sort | uniq -d

dark

  • 俺是博士!
  • *****
  • 文章數: 1581
    • 檢視個人資料
請問重複字串比對問題
« 回覆 #9 於: 2006-05-10 09:38 »
引述: "thyme"
這樣看看可行否
cat /tmp/tmp_str.txt | tr "," "\n" | sort | uniq -d

多謝 thyme 大大 ...

小弟這方式有試過 ... 會造成記憶體緩衝不足 ...
主要是不同程式間互相呼叫資料流重導吧 ??

PS : 其實呼叫 PHP 雖有改善 ... 但剛想出來時很高興
連續按了好幾次 !! 觀看結果 ...... 結果也出現緩衝不足  :cry:

看來 , 有時間的話 ... 前面使用 awk 處理的部份也改 PHP ... 比較不會浪費呼叫過多程式所造成的時間

thyme

  • 老人組
  • 俺是博士!
  • *****
  • 文章數: 1281
    • 檢視個人資料
請問重複字串比對問題
« 回覆 #10 於: 2006-05-10 10:50 »
引述: "dark"
引述: "thyme"
這樣看看可行否
cat /tmp/tmp_str.txt | tr "," "\n" | sort | uniq -d

多謝 thyme 大大 ...

小弟這方式有試過 ... 會造成記憶體緩衝不足 ...
主要是不同程式間互相呼叫資料流重導吧 ??

PS : 其實呼叫 PHP 雖有改善 ... 但剛想出來時很高興
連續按了好幾次 !! 觀看結果 ...... 結果也出現緩衝不足  :cry:

看來 , 有時間的話 ... 前面使用 awk 處理的部份也改 PHP ... 比較不會浪費呼叫過多程式所造成的時間


你的記憶體會不會太少了?
我們算一下,十萬筆的八位數字加逗號的大小為0.9MB,
就算cat, tr, sort, uniq 每個都要用三份的記憶體來緩衝,
那也不會超過12MB呀!

dark

  • 俺是博士!
  • *****
  • 文章數: 1581
    • 檢視個人資料
請問重複字串比對問題
« 回覆 #11 於: 2006-05-10 11:41 »
引述: "thyme"
你的記憶體會不會太少了?
我們算一下,十萬筆的八位數字加逗號的大小為0.9MB,
就算cat, tr, sort, uniq 每個都要用三份的記憶體來緩衝,
那也不會超過12MB呀!
thyme 大大 ...  真抱歉
雖然記憶體很少 ..... 但聽您這麼說   我剛剛又跑一次
結果快的不得了 ..... 幾秒鐘而已

             total       used       free     shared    buffers     cached
Mem:        125984     114868      11116          0      57144      24284
-/+ buffers/cache:      33440      92544
Swap:       265032      31888     233144

可是同樣指令昨天跑時 ...  真的出現那個問題
當時我也有打 free ... 剩餘 8 , 9 MB ..... 跟現在 11 MB 差不到哪 (是 linux 物盡其用)
只是為什麼 ... 還真不知道