亚洲av成人无遮挡网站在线观看,少妇性bbb搡bbb爽爽爽,亚洲av日韩精品久久久久久,兔费看少妇性l交大片免费,无码少妇一区二区三区

Chinaunix

標(biāo)題: 我對(duì)算法的一點(diǎn)感觸 [打印本頁]

作者: xtthnfr 時(shí)間: 2007-08-31 18:41
標(biāo)題: 我對(duì)算法的一點(diǎn)感觸
工作9年了，對(duì)算法有點(diǎn)感觸，我來說說。

有次看電視，采訪一個(gè)廚師里面的大師，他的招牌菜是魚香肉絲。

這個(gè)菜，估計(jì)中國非常多的廚師都會(huì)做。

采訪他時(shí)，他說，他炒菜時(shí)，要先看看這菜是給誰吃。

如果是上海人，他辣子少放點(diǎn)，多放點(diǎn)糖。

如果是四川人，他辣子和花椒會(huì)多放點(diǎn)。

如果是江西人，他多放辣子。

如果里面男人居多，他多放肉。

......

我個(gè)人認(rèn)為，這個(gè)廚師大師，如果來寫程序的話，他應(yīng)該會(huì)在算法上花費(fèi)很多功夫的。

另外，中國絕大多數(shù)的廚師，炒菜時(shí)，又有幾個(gè)象他這樣用心去琢磨嗎？

其實(shí)，解決了生存問題后，任何程序員都可以用心去琢磨自己的程序，慢慢地在自己的開發(fā)中涉及到算法。

當(dāng)然，那些還沒解決生存問題的程序員們，能把老板交代的工作完成了，是第一重要的，算法離他們還太遠(yuǎn)。

這個(gè)就如同普通的一個(gè)士兵，在戰(zhàn)場上，第一重要的是如何保護(hù)自己的性命，如果這點(diǎn)都做不到，那里能談到殺敵，更不用說戰(zhàn)法，戰(zhàn)術(shù)，戰(zhàn)略......

我運(yùn)氣比較很好，從2002年7月份到現(xiàn)在，我差不多一直和搜索引擎打交道，在這個(gè)領(lǐng)域里面，算法往往很重要。

舉個(gè)例子，URL排重的問題。

spider抓取回來很多URL，如何發(fā)現(xiàn)這些URL是新找到的？還是已找到的？

估計(jì)很多程序員，解決這個(gè)問題會(huì)有下面類似步驟：

step 1:
使用數(shù)據(jù)庫進(jìn)行存儲(chǔ)，建立庫表結(jié)構(gòu)，新找到一個(gè)URL，就把它扔到數(shù)據(jù)庫中，如果已有了就不存儲(chǔ)進(jìn)去。

/****************************
*后來出現(xiàn)問題
*(1)URL有上億個(gè),數(shù)據(jù)庫存儲(chǔ)不了，數(shù)據(jù)庫的存儲(chǔ)和查詢速度太慢。
*(2)a.asp?a=1&b=2和a.asp?b=2&a=1實(shí)際上同樣一個(gè)URL。
****************************/

step 2:
建立URL參數(shù)序列化處理，把各個(gè)參數(shù)按照一定規(guī)則來處理。

比如說：把URL中參數(shù)按照ASCII碼大小進(jìn)行序列化，a.asp?b=2&a=1的全部轉(zhuǎn)化為a.asp?a=1&b=2。

另外，使用STL中的MAP來進(jìn)行存儲(chǔ)，存儲(chǔ)/查詢時(shí)間快。

/****************************
*后來出現(xiàn)問題，URL過多后，MAP還是比較慢。
****************************/

step 3:
自己寫hash,取代MAP，提高速度。

/****************************
*后來出現(xiàn)問題，單臺(tái)服務(wù)器的內(nèi)存，存儲(chǔ)空間有限，繼續(xù)改進(jìn)hash算法，用多臺(tái)服務(wù)器進(jìn)行分步存儲(chǔ)。
****************************/

step 4:
......

/****************************
*發(fā)現(xiàn)新的問題，繼續(xù)改進(jìn)........
****************************/

[ 本帖最后由 xtthnfr 于 2007-8-31 18:43 編輯 ]

作者: lenovo 時(shí)間: 2007-08-31 18:47
不錯(cuò)。從實(shí)踐中出發(fā)，
更容易讓人接受。

作者: MMMIX 時(shí)間: 2007-08-31 19:35

原帖由 xtthnfr 于 2007-8-31 18:41 發(fā)表
工作9年了，對(duì)算法有點(diǎn)感觸，我來說說。

有次看電視，采訪一個(gè)廚師里面的大師，他的招牌菜是魚香肉絲。

這個(gè)菜，估計(jì)中國非常多的廚師都會(huì)做。

采訪他時(shí)，他說，他炒菜時(shí)，要先看看這菜是給誰吃。

...

不要?jiǎng)硬粍?dòng)就把算法抬那么高 :em11:

作者: cugb_cat 時(shí)間: 2007-08-31 19:56
曾經(jīng)做過兩年的ACM競賽，依靠的只是算法，雖然現(xiàn)在工作中用到很深的算法的情況不多，但，有了那些基礎(chǔ)后，理解別人的算法，已有的算法，是非常容易非常簡單的事情。

作者: MMMIX 時(shí)間: 2007-08-31 20:00

原帖由 cugb_cat 于 2007-8-31 19:56 發(fā)表
曾經(jīng)做過兩年的ACM競賽，依靠的只是算法，雖然現(xiàn)在工作中用到很深的算法的情況不多，但，有了那些基礎(chǔ)后，理解別人的算法，已有的算法，是非常容易非常簡單的事情。

這個(gè)估計(jì)還要看是什么算法以及理解到什么程度

作者: ypxing 時(shí)間: 2007-08-31 20:02
平時(shí)搞搞算法還是可以提高個(gè)人技術(shù)素養(yǎng)的

作者: cugb_cat 時(shí)間: 2007-08-31 20:06

原帖由 MMMIX 于 2007-8-31 20:00 發(fā)表

這個(gè)估計(jì)還要看是什么算法以及理解到什么程度

這個(gè)就不好說了呵呵要看修煉到什么程度了

作者: MMMIX 時(shí)間: 2007-08-31 20:31

原帖由 ypxing 于 2007-8-31 20:02 發(fā)表
平時(shí)搞搞算法還是可以提高個(gè)人技術(shù)素養(yǎng)的

對(duì)頭，這樣至少在需要選擇的時(shí)候不會(huì)茫然無措

作者: CNIU 時(shí)間: 2007-08-31 20:58
樓主說得很有道理的。雖然我們平時(shí)享受慣了基礎(chǔ)設(shè)施帶來的便利，難免對(duì)算法忽視，但是我們的忽視并不表示它不重要，就像我們不用都去學(xué)土木工程，去親自造高速公路，但并不表示那個(gè)就不重要。

作者: 030802127 時(shí)間: 2007-08-31 21:07
標(biāo)題: 回復(fù) #1 xtthnfr 的帖子
以后再遇到瓶頸，采用B+樹算法構(gòu)建索引文件

作者: benjiam 時(shí)間: 2007-09-01 16:41
以后再遇到瓶頸，采用B+樹算法構(gòu)建索引文件

并不合適，多個(gè)客戶端一起用也是非常麻煩的。

作者: 醉臥水云間 時(shí)間: 2007-09-01 20:08
樓主你就直說了吧，最后用什么方法快，別賣關(guān)子了，你說的那些處理都很平常，多數(shù)人都知道不靈的。

作者: rtp 時(shí)間: 2007-09-01 20:11

原帖由 MMMIX 于 2007-8-31 19:35 發(fā)表

不要?jiǎng)硬粍?dòng)就把算法抬那么高 :em11:

幼稚。

作者: swordfish.cn 時(shí)間: 2007-09-01 20:59
這叫“摸著石頭過河”么。

作者: xtthnfr 時(shí)間: 2007-09-03 09:39

任何事情都要考慮效果和效率,程序設(shè)計(jì)尤其如此.

一般來講分為4種情況

1.效果好,效率高.

2.效果好,效率低.

3.效果差,效率高.

4.效果差,效率低.

程序設(shè)計(jì)出來能正常運(yùn)行,這是效果;程序設(shè)計(jì)出來效果好,運(yùn)行速度快,這是效率,也就是算法.

作為絕大多數(shù)公司,都對(duì)程序的要求是第一種,先要求效果....效率放到第二位.

解決了生存問題的公司和我們程序設(shè)計(jì)人員,才能資格和機(jī)會(huì)去追求第一種效果.

作者: 福瑞哈哥 時(shí)間: 2007-09-03 10:42
標(biāo)題: 回復(fù) #1 xtthnfr 的帖子
樓主的url排重有什么好方法嗎？

bloom-filter？還是干脆用map-reduce？你所列的前幾種方法都無法適應(yīng)大規(guī)模的應(yīng)用。

作者: xtthnfr 時(shí)間: 2007-09-03 11:16

我都說了是自己寫HASH了....

搜索引擎里面很多地方都用到HASH.

作者: xtthnfr 時(shí)間: 2007-09-03 11:36

原帖由 福瑞哈哥 于 2007-9-3 10:42 發(fā)表
樓主的url排重有什么好方法嗎？

bloom-filter？還是干脆用map-reduce？你所列的前幾種方法都無法適應(yīng)大規(guī)模的應(yīng)用。

搜索了一把.....我感覺bloom-filter基本上也還是hash....map-reduce看了半天....沒搞太明白....但我總的感覺就是特殊處理.

我在接著細(xì)化討論一點(diǎn)URL排重吧.

URL有很多特點(diǎn)....

1.URL太長的不多....太短的也不多.....你大概能分析出來URL的平均長度.

2.網(wǎng)頁數(shù)目特別多的超級(jí)的大網(wǎng)站也不多.....可以對(duì)各個(gè)網(wǎng)站進(jìn)行分級(jí).

3......

URL排重具備很多特點(diǎn),和純粹的算法上的隨機(jī)分布完全是兩回事.

所以,URL的排重的HASH就要根據(jù)你對(duì)URL的特點(diǎn)歸納整理出來之后來設(shè)計(jì).

比如說:先按照域名做第一次HASH....然后各個(gè)具體網(wǎng)站上面的在做2級(jí)HASH...象sina和sohu那樣的大網(wǎng)站,還可以按照頻道去做3級(jí)hash.....

//這只是我個(gè)人的想法....

作者: nully 時(shí)間: 2007-09-03 13:20
我的算法：

1.重排URL變量
2.md5一次，16個(gè)字節(jié)128位
3.將16字節(jié)運(yùn)算得到34位數(shù)據(jù)
4.34位數(shù)據(jù)剛好使用2G文件(* 8 bit)來記錄是否出現(xiàn)過

可能有重疊情況發(fā)生，但16G的位空間應(yīng)該夠用了。

作者: lemosa 時(shí)間: 2007-09-03 17:49
算法就像登山中尋找的路。
找對(duì)了，能省很多力氣！

作者: xtthnfr 時(shí)間: 2007-09-03 18:13

原帖由 nully 于 2007-9-3 13:20 發(fā)表
我的算法：

1.重排URL變量
2.md5一次，16個(gè)字節(jié)128位
3.將16字節(jié)運(yùn)算得到34位數(shù)據(jù)
4.34位數(shù)據(jù)剛好使用2G文件(* 8 bit)來記錄是否出現(xiàn)過

可能有重疊情況發(fā)生，但16G的位空間應(yīng)該夠用了。

用MD5的話.....其實(shí)本質(zhì)上就是自己的Hash函數(shù),用MD5來代替.

但是,MD5運(yùn)算過于復(fù)雜,每運(yùn)算一次需要的CPU運(yùn)算次數(shù),過多.....可做個(gè)實(shí)驗(yàn)....50億次的MD5運(yùn)算....花費(fèi)時(shí)間太長.

所以,自己來設(shè)計(jì)的HASH函數(shù)一定要簡單,速度很重要.

[ 本帖最后由 xtthnfr 于 2007-9-3 18:19 編輯 ]

作者: xtthnfr 時(shí)間: 2007-09-03 18:18

原帖由 lemosa 于 2007-9-3 17:49 發(fā)表
算法就像登山中尋找的路。
找對(duì)了，能省很多力氣！

對(duì)頭.....這個(gè)比喻很形象.

爬到山頂,是我們程序設(shè)計(jì)的最后目的.但如何爬上去,路線選擇就是算法之路了.

我能想到的爬山路線有...

1.自己走路.

2.找個(gè)人背我上去.

3.開車上去.

4.坐纜車.

5.坐直升機(jī)...

作者: nully 時(shí)間: 2007-09-03 18:23

原帖由 xtthnfr 于 2007-9-3 18:13 發(fā)表

用MD5的話.....其實(shí)本質(zhì)上就是自己的Hash函數(shù),用MD5來代替.

但是,MD5運(yùn)算過于復(fù)雜,每運(yùn)算一次需要的CPU運(yùn)算次數(shù),過多.....可做個(gè)實(shí)驗(yàn)....50億次的MD5運(yùn)算....花費(fèi)時(shí)間太長.

所以,自己來設(shè)計(jì)的HASH函數(shù) ...

就我這個(gè)算法，I/O才是瓶勁，對(duì)于整個(gè)爬蟲來說，網(wǎng)絡(luò)I/O是瓶頸。
自己寫出來效果很難比md5好，重疊率較高

作者: xtthnfr 時(shí)間: 2007-09-03 19:04

原帖由 nully 于 2007-9-3 18:23 發(fā)表

就我這個(gè)算法，I/O才是瓶勁，對(duì)于整個(gè)爬蟲來說，網(wǎng)絡(luò)I/O是瓶頸。
自己寫出來效果很難比md5好，重疊率較高

MD5肯定玩不轉(zhuǎn)的.....運(yùn)算一次,耗費(fèi)時(shí)間太長.

現(xiàn)在的網(wǎng)絡(luò)速度,對(duì)于搜索引擎公司來講,不是啥問題.

如果,你抓取的URL總數(shù)是50億....那么你要處理的URL估計(jì)就會(huì)是 50 X N 億次.

把所有的URL排重都放到一個(gè)MD5里面來考慮....

可以算一下時(shí)間.....可以找些URL來做實(shí)驗(yàn)....看看1萬個(gè)URL,全部MD5運(yùn)算,需要多少時(shí)間....

如果抓取回來的URL為200億....可以大概估算出來MD5的運(yùn)算時(shí)間.

有時(shí)間的寫個(gè)小程序,運(yùn)算一下單條URL做MD5的平均時(shí)間.

作者: xtthnfr 時(shí)間: 2007-09-03 20:07

原帖由 xtthnfr 于 2007-9-3 19:04 發(fā)表

MD5肯定玩不轉(zhuǎn)的.....運(yùn)算一次,耗費(fèi)時(shí)間太長.

現(xiàn)在的網(wǎng)絡(luò)速度,對(duì)于搜索引擎公司來講,不是啥問題.

如果,你抓取的URL總數(shù)是50億....那么你要處理的URL估計(jì)就會(huì)是 50 X N 億次.

把所有的URL排重都放到 ...

我錯(cuò)了....

MD5的運(yùn)算速度是很快的....

寫了調(diào)用MD5的小程序,速度真的很快.

作者: 醉臥水云間 時(shí)間: 2007-09-03 20:26

原帖由 xtthnfr 于 2007-9-3 11:16 發(fā)表

我都說了是自己寫HASH了....

搜索引擎里面很多地方都用到HASH.

終于說到用HASH了！我覺得也是。50億個(gè)地址用多少位HASH比較合適？128？160？還是更短點(diǎn)就行？

作者: 醉臥水云間 時(shí)間: 2007-09-03 20:28

原帖由 xtthnfr 于 2007-9-3 20:07 發(fā)表

我錯(cuò)了....

MD5的運(yùn)算速度是很快的....

寫了調(diào)用MD5的小程序,速度真的很快.

相對(duì)于提取網(wǎng)頁數(shù)據(jù)，MD5的計(jì)算時(shí)間只是一小點(diǎn)點(diǎn)而已，網(wǎng)絡(luò)再快，提取網(wǎng)頁速度也是秒級(jí)的，計(jì)算MD5時(shí)間可以忽略不計(jì)。

作者: chinesedragon 時(shí)間: 2007-09-03 20:47
不參與論戰(zhàn)～～～～～～··

作者: jlogzl 時(shí)間: 2007-09-06 15:13
個(gè)人對(duì)于算法的看法是：
人機(jī)部分以人為本，機(jī)器處理部分以效率為本。

作者: unicorns 時(shí)間: 2007-09-06 15:41

原帖由 benjiam 于 2007-9-1 16:41 發(fā)表
以后再遇到瓶頸，采用B+樹算法構(gòu)建索引文件

并不合適，多個(gè)客戶端一起用也是非常麻煩的。

使用B樹是一種可選的路徑。
作HASH當(dāng)然效率比B樹高，但是需要大內(nèi)存阿。
B樹只要磁盤夠大就行了。還是比內(nèi)存便宜很多很多的。

如果是一個(gè)要賣給客戶的產(chǎn)品的話，只要效率完全夠用，
這一點(diǎn)上就會(huì)增強(qiáng)產(chǎn)品競爭力了。

當(dāng)然這個(gè)選型要結(jié)合具體情況分析，本身是一個(gè)權(quán)衡的過程。

多個(gè)客戶端的問題沒看明白，是說要同步多個(gè)客戶端嗎，
那這個(gè)問題無論采用哪種方式來組織都是不可避免的阿。

作者: doctorjxd 時(shí)間: 2007-09-06 17:04
算法與兵法

將軍說：兵法很重要，有了它才能決勝千里。

小兵說：也讀過兵法，總覺得太高深，實(shí)際工作中和敵人對(duì)砍才是主要工作，練好武術(shù)，增強(qiáng)體質(zhì)才是王道。

將軍說：你這樣人為就不對(duì)了，兵法是戰(zhàn)爭的藝術(shù)呀。

小兵說：不要把兵法抬得那么高，和敵人對(duì)砍，就看誰狠，刀法才是最重要。

將軍：。。。。你。。。，沒有兵法的妙用，你深陷重圍，光對(duì)砍有什么用？

小兵：哼！沒有我們下面人的對(duì)砍工夫，你兵法也沒什么用吧？

將軍：千軍易得，一將難求。之所以難求，就是因?yàn)樯羁汤斫獗ǖ膶④姾苌�。沒有睿智的戰(zhàn)略眼光，沒有對(duì)兵法的靈活運(yùn)用，百萬大軍也只不過是烏合之眾。

小兵：拿破侖也說過，不想當(dāng)將軍的士兵不是好士兵，但你沒有扎實(shí)的對(duì)砍技術(shù)，怎么又能成為好士兵呢？不是好士兵又怎么能成為將軍呢？

作者: ypxing 時(shí)間: 2007-09-06 17:07
妙哉

原帖由 doctorjxd 于 2007-9-6 17:04 發(fā)表
算法與兵法

將軍說：兵法很重要，有了它才能決勝千里。

小兵說：也讀過兵法，總覺得太高深，實(shí)際工作中和敵人對(duì)砍才是主要工作，練好武術(shù)，增強(qiáng)體質(zhì)才是王道。

將軍說：你這樣人為就不對(duì)了，兵法是戰(zhàn)爭 ...

作者: oyd_admin 時(shí)間: 2007-09-07 17:05
前面某某說的MD5 做128bit的hash本身還是不錯(cuò)的，但是隨后說處理一下變成34bit，這個(gè)就太可能沖突了
還是另一位說的BloomFilter好，利用概率原理，能把位密度弄到超級(jí)大，而沖突機(jī)會(huì)還是很小

不過，實(shí)際運(yùn)行中的排重，沒有必要幾十億網(wǎng)頁重新排一遍吧？
在來一個(gè)url檢查一次的情況下，做索引文件就有余了，這時(shí)候的瓶頸必然是網(wǎng)絡(luò)通訊。

我怎么總覺得BloomFilter好是好，就是有點(diǎn)高不成低不就的。

作者: DennisRitchie 時(shí)間: 2007-09-07 17:28

原帖由 MMMIX 于 2007-8-31 19:35 發(fā)表

不要?jiǎng)硬粍?dòng)就把算法抬那么高 :em11:

關(guān)于算法的重要性，樓主只說過“在搜索引擎領(lǐng)域里面，算法往往很重要�！�，不知道你激動(dòng)個(gè)啥？？？

作者: 我learnc 時(shí)間: 2007-09-07 19:42

原帖由 jlogzl 于 2007-9-6 15:13 發(fā)表
個(gè)人對(duì)于算法的看法是：
人機(jī)部分以人為本，機(jī)器處理部分以效率為本。

人機(jī)部分非常難做,我以前寫的程序,效率不是問題,但是客戶普通反映用起來不方便.,客戶更在意的是方便他使用,慢一點(diǎn)他倒能夠忍受.甚至于追加硬件他也很高興掏錢:em11: :em11: :em11: :em11: :em11: :em11: :em11: :em11: :em11:

作者: liuty2006 時(shí)間: 2007-09-07 23:07
同意lz的觀點(diǎn)！
算法就是要解決實(shí)際中存在的問題而存在的！
不要為算法而算法，這樣在實(shí)際工作中很不經(jīng)濟(jì)！
比如：你開發(fā)的軟件用時(shí)一個(gè)月，用戶對(duì)速度滿意。
那你又何必絞盡腦汁花費(fèi)兩個(gè)月來開發(fā)出用戶并不在意的“更好”的軟件？

經(jīng)濟(jì)社會(huì)，就要有經(jīng)濟(jì)眼光！
夠用就成！

作者: hightman 時(shí)間: 2007-09-07 23:53
嘿,關(guān)于這個(gè)問題,小弟在分詞詞典存取時(shí)設(shè)計(jì)了一套自稱為 XDB 的東西, 就是 Hash + Btree 的結(jié)構(gòu), 感覺還不錯(cuò), 用來代替 gdbm, cdb ...

有興趣參見:
http://www.72891.cn/viewthr ... 9&highlight=cdb

作者: tom_xx_hu@yahoo 時(shí)間: 2007-09-08 05:01
同意LZ對(duì)算法的理解，但是不同意把如何認(rèn)識(shí)算法的重要性這樣一個(gè)學(xué)術(shù)或者技術(shù)的問題和個(gè)人的生存狀態(tài)相聯(lián)系：

當(dāng)然，那些還沒解決生存問題的程序員們，能把老板交代的工作完成了，是第一重要的，算法離他們還太遠(yuǎn)。

這樣好像誰要是不承認(rèn)算法的重要性就是生存問題還沒有解決的人。這是不光明磊落的態(tài)度。

[ 本帖最后由 tom_xx_hu@yahoo 于 2007-9-8 05:02 編輯 ]

歡迎光臨 Chinaunix (http://www.72891.cn/)