Re: [請益] 請問學哪個比較實用

看板Soft_Job作者 (喲)時間16年前 (2010/02/20 16:31), 編輯推噓15(15推 0噓 94→)
留言109則, 7人參與, 最新討論串10/19 (看更多)
※ 引述《remmurds (雷穆爾德‧小一)》之銘言： : ※ 引述《Smurf (哈里歐)》之銘言： : : 我表達能力不夠好 讓大大誤會了 想學C++是因為我想知道封裝的實作細節 : : 例如Java的ArrayList其實就是先預設一個size : : 超過這個size要重新配置 所以元素太多時用ArrayList效能會降低 : : LinkedList的實做就是Double Linked List資料結構 要用哪個視情況而定 : 　　你還是沒看懂我在說什麼。想知道封裝的細節跟想學C++有什麼絕對的關連？請自行 : 搜尋一下天●書局的網站，看看那些以資料結構為主題的書是不是都只用C++。 : 　　再強調一次，就資料結構或演算法而言，學哪種語言根本不是重點。如果一開始就被 : 語言綁住，就會像我一個學弟先前鬧出的笑話：「我學的是Python，我沒辦法寫鍊結串列 ^^^^ 這裡我稍有些疑議,我以為linked list就是綁在C或C++這種指標串連資料結構的語言. 如果選用別的語言,linked不linked可能都不重要. 像 Erlang 好了,list就是愛連就連,不用也不會像陣列一樣用太多空間,因為底層的 抽像機已經把一些linked的結構做好了. 它所謂linked list就是: [1|[2|[3|[]]]] 語法上省略寫為 [1,2,3] 所謂linked就是一個結構包含另一個結構. Linked list則是結構的包含方式比較有規律. 在這方面,我覺得要說語言不重要,在linked list上面不是如此. Linked list用C或C++寫才會特別把link帶出來. 用Python,談什麼link呢? 而真要說不被語言綁住的,是stack,queue,tree,graph這些language-free的東西. -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 61.231.68.175
→
02/20 21:40, , 1F
不管是哪種LinkedList 它們最大的優點不就是解決陣列只有
02/20 21:40, 1F
→
02/20 21:41, , 2F
固定空間的問題? 這跟一種語言有沒有指標沒關係吧?
02/20 21:41, 2F
→
02/20 21:47, , 3F
但問題是,陣列只有固定空間不就是C語言特徵來的嗎
02/20 21:47, 3F
→
02/20 21:48, , 4F
當你遇到另一種語言,陣列空間基本已經不是問題,linked list
02/20 21:48, 4F
→
02/20 21:48, , 5F
就變得很不必要了.
02/20 21:48, 5F
→
02/20 21:52, , 6F
有陣列固定空間問題的又不是只有C或C++ Java、C#和其他那
02/20 21:52, 6F
→
02/20 21:53, , 7F
些常見的程式語言通通都有 只不過以Java和C#來說 已經有
02/20 21:53, 7F
→
02/20 21:53, , 8F
包裝好的東西可以直接拿來用 就跟你提到的Erlang一樣
02/20 21:53, 8F
→
02/20 21:54, , 9F
但不管有沒有現成的東西可以用 別忘了原原PO現在是要學這
02/20 21:54, 9F
→
02/20 21:55, , 10F
些資料結構 如果不從原理看起 就算有現成的東西 原原PO又
02/20 21:55, 10F
→
02/20 21:55, , 11F
怎麼知道這些東西的優缺點在哪?什麼時候可以派得上用場?
02/20 21:55, 11F
推
02/20 23:04, , 12F
既然你提到 Erlang, 如果不知道 linked list 的特性
02/20 23:04, 12F
→
02/20 23:05, , 13F
你怎麼知道要用 Result++H 還是 [H|Result] 的效率比較好?
02/20 23:05, 13F
→
02/20 23:48, , 14F
喔,沒想到會提到++... 應該是Result++[H]. 我想對於++的了解
02/20 23:48, 14F
→
02/20 23:49, , 15F
不是知不知道linked list的特性,而是++的定義如何.
02/20 23:49, 15F
→
02/20 23:51, , 16F
[] ++ X -> X; [X|Y] ++ Z -> X ++ [Y|Z].
02/20 23:51, 16F
→
02/20 23:52, , 17F
因為++是用了許多list運算處理左項,所以耗費較多計算時間.
02/20 23:52, 17F
→
02/20 23:54, , 18F
[X|Y] ++ Z -> [X|(Y++Z)] 寫錯,更正.
02/20 23:54, 18F
→
02/20 23:55, , 19F
這個跟linked list概念可以連接得上嗎? 我覺得很難...
02/20 23:55, 19F
推
02/20 23:55, , 20F
那不就是 linked list 的特性嗎? :p
02/20 23:55, 20F
→
02/20 23:56, , 21F
你寫的這些式子就在解釋 linked list 是怎麼運作的
02/20 23:56, 21F
→
02/20 23:57, , 22F
如果你沒有這些基礎的知識, 怎知道 ++ 會有什麼 performance
02/20 23:57, 22F
→
02/20 23:57, , 23F
的 impact
02/20 23:57, 23F
→
02/21 00:16, , 24F
嗯,對耶... 受教了.
02/21 00:16, 24F
→
02/21 00:18, , 25F
不過回remmurds,不用這東西不表示不該知道它啦.而是在別的
02/21 00:18, 25F
→
02/21 00:18, , 26F
語言中,可能說linked list並且做了半天,那個模型仍然消失在
02/21 00:18, 26F
→
02/21 00:19, , 27F
語法中. 像Erlang就是. 所以倒不如不要計較這個小事.
02/21 00:19, 27F
推
02/21 02:17, , 28F
linked-list的好處不只是空間使用有彈性
02/21 02:17, 28F
→
02/21 02:17, , 29F
當資料要搬動時 也非常靈活 例如要在list中插入新元素
02/21 02:17, 29F
→
02/21 02:18, , 30F
陣列必須把所有元素都往後移一位 挪出空間
02/21 02:18, 30F
→
02/21 02:18, , 31F
linked-list可以直接插入 一個是 O(N) 一個是 O(1)
02/21 02:18, 31F
→
02/21 08:09, , 32F
linked list調整空間的彈性當然不用說,而且像Erlang及一些
02/21 08:09, 32F
→
02/21 08:10, , 33F
不錯的語言本身已經有這種有彈性的list特質.
02/21 08:10, 33F
→
02/21 08:12, , 34F
至於插入或刪除資料的O(1)和O(N)的比較,是因為有個固定陣列
02/21 08:12, 34F
→
02/21 08:13, , 35F
的基礎,才會冒出這個問題. 這問題在Erlang本身並不存在.
02/21 08:13, 35F
→
02/21 08:14, , 36F
因為不是先宣告空間再賦值,而是把資料取來直接合併成list.
02/21 08:14, 36F
例如,要做個key-value的linked list,結構是這樣: [{Key,Value},Next] Next如果是空節點,表達為 []. 串列建立函數是 create() -> []. 加入新節點是 add([], Node) -> [Node,[]]; add([L|List], Node) -> [L|add(List,Node)]. 所以先 L1 = add([], {a, 100}): add([], {a,100}) -> [{a,100},[]] 再 L2 = add(L1, {b, 200}): add([{a,100},[]], {b,200}) -> [{a,100}|add([],{b,200}] -> [{a,100}|[{b,200},[]]] -> [{a,100},{b,200},[]] 再 L3 = add(L2, {c, 300}): add([{a,100},{b,200},[]], {c,300}) -> [{a,100}|add([{b,200},[]],{c,300})] -> [{a,100}|[{b,200}|add({c,300},[])]] -> [{a,100}|[{b,200}|[{c,300},[]]]] -> [{a,100},{b,200},{c,300},[]] 而以上依序插入 {a,100}, {b,200}, {c,300} 的結果可以寫成一個普通的list: [{a,100},{b,200},{c,300}] 節點插入函數是O(N)的走訪與O(1)的插入, insert(LList, 1, [Data,_]) -> [Data|LList]; insert([L|List], N, [Data,_]) when N > 1 -> [L|insert(List,N-1, [Data,[]])]; insert(LList, _, _) -> LList. 這一點linked list和普通list沒有差別. 以前面試考過的串列倒排,可以做得一模一樣. 如果有一列串列是 [{a,100},{b,200},{c,300},[]] 除了第一節點之外,後面節點是走訪到就把節點抓出來放到串列前端, [{a,100},{b,200},{c,300},[]] -> [{b,200}|[{a,100},{c,300},[]]] -> [{c,300}|[{b,200}|[{a,100},[]]]] -> [{c,300},{b,200},{a,100},[]] 串列倒排函數是 reverse([]) -> []; reverse([Data,[]]) -> [Data,[]]; reverse([First,Second|Next]) -> [NH|NT] = reverse_partial([First|Next]), [NH, Second | NT]. reverse_partial([F,S|Next]) -> [S | revesre([F|Next])]. 但這樣寫起來好麻煩,倒是以下這種標準型好寫一點;只是缺點是慢一點點: rev([]) -> []; rev([H|T]) -> rev(T) ++ [H]. 另外有比較快的,用一個額外的變數累積結果的技巧: reverse(Any) -> rev(Any, []). rev([], Result) -> Result; rev([H|T], Part) -> rev(T, [H|Part]). 使用Python這種有函數風格的語言, 思考資料結構的方式或許不同,但內涵一樣有相當多的東西可引用. 這是我的一點意見. ※ 編輯: yauhh 來自: 61.231.68.175 (02/21 09:32)
推
02/21 09:27, , 37F
我不會 Erlang 語言 但這些資料結構底層的實作
02/21 09:27, 37F
→
02/21 09:27, , 38F
還是不脫 array, linked-list, tree, hash 等方式
02/21 09:27, 38F
還有 31 則推文
還有 3 段內文
推
02/22 01:15, , 70F
Python 內建的 list 是用 array 實作
02/22 01:15, 70F
→
02/22 01:15, , 71F
當程式需要大量插入、刪除、搬移的時候 效率很差
02/22 01:15, 71F
→
02/22 01:15, , 72F
怎麼能夠說「不需要用就不要用,也很有效率啊」 @@
02/22 01:15, 72F
→
02/22 01:34, , 73F
有點像是要說過度最佳化的問題 , 不過我認為多瞭解點無妨.
02/22 01:34, 73F
→
02/22 01:39, , 74F
現在很明顯,你一直說這個,卻沒有給個很明確的示範告訴我
02/22 01:39, 74F
→
02/22 01:40, , 75F
為什麼*任何程式語言*都要懂array與linked list的差異.
02/22 01:40, 75F
→
02/22 01:42, , 76F
然而我卻給個直接的例子告訴你並非如此,用Python之類的討論
02/22 01:42, 76F
→
02/22 01:42, , 77F
資料結構時,對於linked list是想都不必想的.
02/22 01:42, 77F
推
02/22 01:46, , 78F
Python 也可以自己實作 linked-list 啊
02/22 01:46, 78F
→
02/22 01:46, , 79F
你 Google "python linked-list" 就有許多文章了
02/22 01:46, 79F
→
02/22 01:46, , 80F
怎麼會是"想都不用想"???
02/22 01:46, 80F
→
02/22 01:48, , 81F
很明白告訴你了,特地做這個東西是白作工.
02/22 01:48, 81F
推
02/22 01:49, , 82F
當效能出現問題時候 就必須要有資料結構的知識
02/22 01:49, 82F
→
02/22 01:49, , 83F
就像現在,給你看了例子,你還是不信. 那我真沒輒.
02/22 01:49, 83F
→
02/22 01:49, , 84F
不論你用什麼語言 都要有這些知識
02/22 01:49, 84F
→
02/22 01:50, , 85F
有時甚至為了改善效能而必須用更合適的語言
02/22 01:50, 85F
→
02/22 01:50, , 86F
為什麼是白工？ 兩者的時間複雜度可不一樣耶
02/22 01:50, 86F
→
02/22 02:00, , 87F
我手上有一本函數語言的演算法書籍,資料結構部份的確什麼都
02/22 02:00, 87F
→
02/22 02:01, , 88F
有,但是獨缺linked list. 那你是否覺得搞這個的白痴到不把
02/22 02:01, 88F
→
02/22 02:01, , 89F
linked list列入討論範圍?
02/22 02:01, 89F
→
02/22 02:02, , 90F
很抱歉,我沒跟你談各種資料結構,我只談linked list.
02/22 02:02, 90F
推
02/22 02:02, , 91F
拿一本書就可以證明 python 裡不需要 linked-list?
02/22 02:02, 91F
推
02/22 02:09, , 92F
你還沒解釋為什麼在python裡做linked-list是白工喔 :P
02/22 02:09, 92F
→
02/22 12:22, , 93F
Huangs兄,讓我告訴你二件殘酷的事實: 1) Erlang的list就是
02/22 12:22, 93F
→
02/22 12:22, , 94F
跟linked list一樣的東西,所以我沒有理由再實作linked list
02/22 12:22, 94F
→
02/22 12:23, , 95F
2) Erlang基本資料型態根本沒有array,所以何必硬說要知道
02/22 12:23, 95F
→
02/22 12:23, , 96F
array跟linked list的差別? 要用array可以掛上array模組,
02/22 12:23, 96F
→
02/22 12:24, , 97F
但是普通程式我根本不用考慮什麼array空間有限的問題.
02/22 12:24, 97F
→
02/22 12:25, , 98F
你不知道Erlang卻敢隨便說任何語言都要考慮array跟linked
02/22 12:25, 98F
→
02/22 12:26, , 99F
list的差異,我只覺得這是否言過其實了?
02/22 12:26, 99F
推
02/22 13:53, , 100F
那如果現在的case需要 random access，Erlang 怎麼辦？
02/22 13:53, 100F
→
02/22 13:54, , 101F
只好用內建的 linked-list 很慢的操作囉？
02/22 13:54, 101F
→
02/22 13:54, , 102F
而且你剛講得不是 python 嗎？怎麼又變回 Erlang 了？
02/22 13:54, 102F
→
02/22 13:55, , 103F
我不知道 Erlang 是否可以用 array 來作 random access
02/22 13:55, 103F
→
02/22 13:56, , 104F
但程式設計師在寫Erlang仍然必需意識到這麼問題
02/22 13:56, 104F
→
02/22 13:56, , 105F
如果遇到的case需要大量的random access
02/22 13:56, 105F
→
02/22 13:57, , 106F
那麼不支援random access的語言 可能就存在效能的問題
02/22 13:57, 106F
→
02/22 13:57, , 107F
當效能問題嚴重時 甚至必需換語言
02/22 13:57, 107F
→
02/22 13:58, , 108F
所以說用任何語言 都要考慮 array 與 linked-list 的差異
02/22 13:58, 108F
→
02/22 19:56, , 109F
linked-list是資料結構 怎麼會綁語言呢...
02/22 19:56, 109F
‣ 更多 yauhh 的文章
文章代碼(AID): #1BVvtz9T (Soft_Job)
討論串 (同標題文章)
本文引述了以下文章的的內容：
以下文章回應了本文：
完整討論串 (本文為第 10 之 19 篇)：
排序： 最新先 | 最舊先 | 留言數
在新視窗開啟完整討論串 (共19篇)
‣ 更多 yauhh 的文章
文章代碼(AID): #1BVvtz9T (Soft_Job)