Re: [問題] linked list& array

看板Programming作者yauhh (喲)時間14年前 (2011/03/10 23:13)推噓2(2推 0噓 62→)

留言64則, 5人參與討論串9/9 (看更多)

※ 引述《Lordaeron (Terry)》之銘言： : ※ 引述《adrianshum (Alien)》之銘言： : : 就說你沒在留心別人在說什麼. : : 你可以把 array 或 linked list 理解成實作好,不要吵. 就算這個千萬不能想成那個,那也只不過是: "直尺的邊線很直" "太陽從東邊出來" 那一類的常識,不是嗎? 想想看,為什麼大家一開始學程式,老師說array的取值時間是O(1),他們就一點沒有懷疑,可能也沒有具體思考過? 為什麼array的任一元素取值是O(1)時間成本? 在此所講的array是 C 的記憶體對應的基本 array. 為什麼取值是 O(1) ? 是因為這個array對應記憶體,而 array的底層---記憶體的取值都是用base和offset 來算,任何位置全都是幾個加法求出來,然後去取值,所以是 O(1). 由這項基本知識,我們可以隱約知道, array 的隨機存取便利並不是因為 C 語言本身的特質,而只不過是幾乎大部份的程式語言基礎都在這一台機器上. 機器特性是這樣, 順著機器的特性, array 才有隨機存取的特徵. 最初那位love誰網友所回應說:stack或queue要怎麼做 array? 是,的確很具體. 但是如果就因為這樣,就認為任何語言全部都是這樣,太不切實際. 事實上,跳到不同語言中,思考的基礎不會一樣. 若你只是因為站在 C 語言中看到 array 就是這樣子,就拒絕接受其他種語言的可能,拒絕思考用其他模型實作 array, 那未免太可憐. 這種思考方式只不過是打從你學程式一開始,就已經養成拒絕思考的習慣. 說穿了,很多人跟你一樣,全都是時薪多少錢的程式匠而已,沒什麼了不起. 與其留在圈圈之內,因為無足夠資訊而說不,倒不如跨出圈圈,多看一點點東西, 然後有足夠的資訊可以說不. 另外... 如果把隨機存取的便利抽掉, array 的原型是什麼? Array 就是一堆數字(索引)對應到一堆目標物,所以 array 的原型就是函數. 照電腦電路來看,可能是因為電力速度很快,所以從索引數字,base,offset算到目標元素太快了. 但是,換作你用人力在真正的倉儲系統找東西,給你一個編號,你還是找蠻久的, 所以隨機存取可能不是必要. 不過,許多別的電腦語言也要實作 array, VM也需要實作記憶空間,像 Java 的 heap. 在這時,所謂實體結構的堅持就很沒有必要. 如你所想,你認為我用stack做出linked list其實是用linked list實作linked list, 顯然是直接認定 stack 就是linked list. 但是這樣想也很有缺陷,誰說stack就一定是linked list了? 對一個抽象結構我們只關心介面,而不關心實作,你這樣一下子進去拆解裡頭的結構顯然很亂. 同樣的道理,用來做資料庫索引的B-Tree,也直接想成用array實作的樹結構,那就回去慢慢分析所有的結構,被那堆資訊淹沒. 我們只是需要那些抽象結構幫助好用好想而已,而不是強調抽象結構必須是怎麼樣的抽象結構,或不得是哪些實體結構. ------ 最後回歸正題: 根本不值得爭論stack可不可以做 linked list. 以我回應原po的文字意思,是說, "這種問題很好,表示你有在動腦袋." "如果你有在動腦袋,我建議你怎麼動腦袋比較好." 重點是在對原po的學習加以鼓勵. 但是,你覺得我們真的要浪費時間爭執 stack 和 queue 到底可以不可以做 array 和 linked list 嗎? 等你爭完了,會發現:一場空. 我隨便舉一個例子,例子可能很不完整很破爛,你卻認真分析那個例子, 那麼誰是傻子? 你早就知道這沒有意義了,不是嗎? -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 218.160.209.63 ※ 編輯: yauhh 來自: 218.160.209.63 (03/10 23:37)

→