Re: [問題] linked list& array

[yauhh (喲)]

※ 引述《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)
→ Lordaeron:array/stack/queue 是處理資料的方式
→ Lordaeron:Linked List 是資料存放的方法.
→ Lordaeron:有人連基本的定義也不懂,給link 也不看
→ Lordaeron:就愛在這扯在一起談
→ firejox:Link List/array/stack/queue都可以作為
→ firejox:處理資料的方式和存放的方法
→ firejox:後來卻扯遠了QQ
→ Lordaeron:http://xlinux.nist.gov/dads// 自己查
→ Lordaeron:array/stack/queue都有operation
→ Lordaeron:但linklist 沒有
推 arcred:呃..linked list刪點加點都是operation啊
→ arcred:不就資料不完整而已? @@
→ firejox:他們都屬於data structure啊 .....
→ Lordaeron:定義就在哪,請自己看.
推 arcred:丟個網站就斬釘截鐵說定義是你想的那樣, 別
→ arcred:人的話聽不進去, 只能說: 你高興就好 -o-
→ Lordaeron:你最好比哪個網站的說明還要強囉.
→ adrianshum:@arcred:如果有看過某人以前做的討論,
→ adrianshum:你會發覺這是常態. 所以我也懶得再說下
→ adrianshum:去了 XD  放輕鬆就好.
→ firejox:網站也是人寫的啊
→ firejox:又不是一定絕對的
→ Lordaeron:當然不絕對, 因為你連基本的什麼叫定義
→ Lordaeron:都不知道, 更別說哪個網站是幹嘛的
→ Lordaeron:而adrianshum的常態就是打嘴砲打了就跑
→ Lordaeron:如果對定義有問題,請你拿出你手邊的
→ Lordaeron:DS/algorithm 的書來看.
→ Lordaeron:還是你比較強,自己定義出自己的stack
→ Lordaeron:和linklist像adrianshum哪樣來玩文字
→ Lordaeron:哪就沒什麼好討論的了,因為你爽就好了
→ firejox:我覺得定義只是最簡單的部份
→ firejox:因為不能再簡化了，而延伸的是他的性質
→ firejox:有很多的操作都是由性質延伸的
→ firejox:所以我頂多只能對他描述罷了
→ firejox:重定義沒有意義阿
→ firejox:array+stack湊一湊就很像vector了
→ firejox:因為用了性質去處理就有辦法達到
→ Lordaeron:看來你是沒有數學觀念,更像沒學過DS的人
→ Lordaeron:哪樣,現在連vector 都跑出來了.
→ Lordaeron:如果真的沒學過DS,請你去好好的學吧
→ Lordaeron:不要再硬拗了,現在stack,LinkedList都
→ Lordaeron:是早就有人定義好的了,是你們愛拗說
→ Lordaeron:哪只是一個介面,B-Tree也是一個array的
→ Lordaeron:這種爛文字遊戲,又是誰在這自high呢?
→ Lordaeron:你們有讀過B-tree 的定義?還是你愛叫
→ Lordaeron:它是B-Tree 它就是?
→ firejox:我只是說"很像" 並沒有說"相等"
→ firejox:性質相似並不是本質一樣
→ firejox:打個比方 如果要把三角形相似說成全等
→ firejox:我只能無言了
→ Lordaeron:你真的無言就好了,因為只有你的DS中有
→ Lordaeron:Vector 這個東西,你還是回去看書吧
→ firejox:我愈來愈覺得談話是處於平行的狀態下
→ firejox:我覺得你還沒聽懂我說的話，完全誤會了我
→ firejox:的意思
→ firejox:我沒有在玩文字遊戲,這種只是簡單的邏輯
→ firejox:而已
→ Lordaeron:你的簡單的邏輯就是,你沒去讀DS 的書
→ Lordaeron:還在這拗,你還是回去讀書吧
→ Lordaeron:連什麼是定義都沒搞清楚,書也不見, 就在
→ Lordaeron:扯,網站是人寫的, 又不一定
→ Lordaeron:又說什麼延申性質.
→ wfgh:看了一整串下來 只覺得Lord大沒有接受別人看
→ wfgh:法的心態 人家強調是思考過程 唉 死讀書的腦