作者yauhh (哟)
看板Soft_Job
标题Re: [请益] 请问学哪个比较实用
时间Sat Feb 20 16:31:54 2010
※ 引述《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
1F：→ remmurds:不管是哪种LinkedList 它们最大的优点不就是解决阵列只有 02/20 21:40
2F：→ remmurds:固定空间的问题? 这跟一种语言有没有指标没关系吧? 02/20 21:41
3F：→ yauhh:但问题是,阵列只有固定空间不就是C语言特徵来的吗 02/20 21:47
4F：→ yauhh:当你遇到另一种语言,阵列空间基本已经不是问题,linked list 02/20 21:48
5F：→ yauhh:就变得很不必要了. 02/20 21:48
6F：→ remmurds:有阵列固定空间问题的又不是只有C或C++ Java、C#和其他那 02/20 21:52
7F：→ remmurds:些常见的程式语言通通都有 只不过以Java和C#来说 已经有 02/20 21:53
8F：→ remmurds:包装好的东西可以直接拿来用 就跟你提到的Erlang一样 02/20 21:53
9F：→ remmurds:但不管有没有现成的东西可以用 别忘了原原PO现在是要学这 02/20 21:54
10F：→ remmurds:些资料结构 如果不从原理看起 就算有现成的东西 原原PO又 02/20 21:55
11F：→ remmurds:怎麽知道这些东西的优缺点在哪?什麽时候可以派得上用场? 02/20 21:55
12F：推 ledia:既然你提到 Erlang, 如果不知道 linked list 的特性 02/20 23:04
13F：→ ledia:你怎麽知道要用 Result++H 还是 [H|Result] 的效率比较好? 02/20 23:05
14F：→ yauhh:喔,没想到会提到++... 应该是Result++[H]. 我想对於++的了解 02/20 23:48
15F：→ yauhh:不是知不知道linked list的特性,而是++的定义如何. 02/20 23:49
16F：→ yauhh:[] ++ X -> X; [X|Y] ++ Z -> X ++ [Y|Z]. 02/20 23:51
17F：→ yauhh:因为++是用了许多list运算处理左项,所以耗费较多计算时间. 02/20 23:52
18F：→ yauhh: [X|Y] ++ Z -> [X|(Y++Z)] 写错,更正. 02/20 23:54
19F：→ yauhh:这个跟linked list概念可以连接得上吗? 我觉得很难... 02/20 23:55
20F：推 ledia:那不就是 linked list 的特性吗? :p 02/20 23:55
21F：→ ledia:你写的这些式子就在解释 linked list 是怎麽运作的 02/20 23:56
22F：→ ledia:如果你没有这些基础的知识, 怎知道 ++ 会有什麽 performance 02/20 23:57
23F：→ ledia:的 impact 02/20 23:57
24F：→ yauhh:嗯,对耶... 受教了. 02/21 00:16
25F：→ yauhh:不过回remmurds,不用这东西不表示不该知道它啦.而是在别的 02/21 00:18
26F：→ yauhh:语言中,可能说linked list并且做了半天,那个模型仍然消失在 02/21 00:18
27F：→ yauhh:语法中. 像Erlang就是. 所以倒不如不要计较这个小事. 02/21 00:19
28F：推 Huangs:linked-list的好处不只是空间使用有弹性 02/21 02:17
29F：→ Huangs:当资料要搬动时 也非常灵活 例如要在list中插入新元素 02/21 02:17
30F：→ Huangs:阵列必须把所有元素都往後移一位 挪出空间 02/21 02:18
31F：→ Huangs:linked-list可以直接插入 一个是 O(N) 一个是 O(1) 02/21 02:18
32F：→ yauhh:linked list调整空间的弹性当然不用说,而且像Erlang及一些 02/21 08:09
33F：→ yauhh:不错的语言本身已经有这种有弹性的list特质. 02/21 08:10
34F：→ yauhh:至於插入或删除资料的O(1)和O(N)的比较,是因为有个固定阵列 02/21 08:12
35F：→ yauhh:的基础,才会冒出这个问题. 这问题在Erlang本身并不存在. 02/21 08:13
36F：→ yauhh:因为不是先宣告空间再赋值,而是把资料取来直接合并成list. 02/21 08:14
例如,要做个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)
37F：推 Huangs:我不会 Erlang 语言 但这些资料结构底层的实作 02/21 09:27
38F：→ Huangs:还是不脱 array, linked-list, tree, hash 等方式 02/21 09:27
39F：→ Huangs:而这些实作方式都有不同的效率和使用时机 02/21 09:27
40F：→ Huangs:O(N) vs. O(1) 之类的复杂度差异永远存在 02/21 09:28
41F：→ Huangs:高阶语言只是把这些资料结构包装起来了 问题仍然存在的 02/21 09:28
42F：推 Huangs:看来只是用不同的语法在操作linked-list 02/21 09:37
43F：推 Huangs:反而是你一开始的命题「linked-list绑C/C++等语言」的反例? 02/21 09:40
※ 编辑: yauhh 来自: 61.231.68.175 (02/21 09:49)
44F：→ yauhh:不是,我觉得是在Erlang中,刻意做linked list虽然做出来, 02/21 09:51
45F：→ yauhh:但却是跟普通的资料型态一模一样.结论是在Erlang根本不用做. 02/21 09:52
46F：→ yauhh:我的reverse/1做错了,果然,要直接对应仍然有些困难. 02/21 09:53
reverse/1改一下是
reverse([]) -> [];
reverse([LList,[]]) -> LList;
reverse([First,Second|Next]) when is_atom(First)
-> reverse([[Second,First,[]] | Next]);
reverse([First,Second|Next]) when is_list(First)
-> reverse([[Second|First] | Next]).
这样符合前一段论述.
47F：推 Huangs:那当有两种 case 时: 大量 random access 和大量插入删除 02/21 09:54
48F：→ Huangs:在 Erlang 要如何选择container？ 02/21 09:55
※ 编辑: yauhh 来自: 61.231.68.175 (02/21 10:17)
49F：→ yauhh:random access有Erlang Term Service和Dictionary可用 02/21 10:30
50F：→ yauhh: Store 02/21 10:39
51F：→ lovekkk:我以为 linked list 主要用处是插入资料方便? 02/21 10:42
52F：→ lovekkk:长度的话 array 也可以用外部档案分批存取来解决 02/21 10:43
53F：→ lovekkk:linked list 要多存链结, 一次能读入的资料搞不好还比较少 02/21 10:45
54F：→ remmurds:阵列只有固定长度的问题不只有空间不够 也包含空间浪费 02/21 10:48
55F：→ lovekkk:没关系, 有浪费问题表示...还够用 :p 02/21 10:49
56F：推 Huangs:所以说 Erlang 的程师设计师 仍然要了解Linked-list 02/21 16:11
57F：→ Huangs:与array的特性 才能正确使用适合的资料结构 02/21 16:12
58F：→ Huangs:所以并没有因为选用了Erlang或其他高阶语言 02/21 16:12
59F：→ Huangs:linked-list就变得不重要啊 02/21 16:12
60F：→ Huangs:说穿了 在高阶语言上 即使没有指标 02/21 16:14
61F：→ Huangs:仍然是透过其他方式来操作 linked-list 02/21 16:14
62F：推 ledia:推楼上 02/21 21:44
63F：→ yauhh:不过,据个人所知,函数语言的程式改良比较不会在这小地方钻. 02/22 00:41
64F：→ yauhh:毕竟你说用错资料结构,会有什麽机会用错呢? 基本型态就几种 02/22 00:42
65F：→ yauhh:而已.实在是蛮难延用C语言处理资料空间的思考方式. 02/22 00:43
66F：→ yauhh:嗯...我真的没说linked list不重要,而是 "在Erlang谈什麽 02/22 00:58
67F：→ yauhh:linked list呢?" 意思是说,list本身就有linked list的弹性. 02/22 00:59
68F：→ yauhh:所以像Python之流的函数语言,如前文所嗤笑的不懂linked list 02/22 00:59
69F：→ yauhh:我个人是看不懂有什麽可笑的.不需要用就不要用,也很有效率啊 02/22 01:00
70F：推 Huangs:Python 内建的 list 是用 array 实作 02/22 01:15
71F：→ Huangs:当程式需要大量插入、删除、搬移的时候 效率很差 02/22 01:15
72F：→ Huangs:怎麽能够说「不需要用就不要用,也很有效率啊」 @@ 02/22 01:15
73F：→ TonyQ:有点像是要说过度最佳化的问题 , 不过我认为多了解点无妨. 02/22 01:34
74F：→ yauhh:现在很明显,你一直说这个,却没有给个很明确的示范告诉我 02/22 01:39
75F：→ yauhh:为什麽*任何程式语言*都要懂array与linked list的差异. 02/22 01:40
76F：→ yauhh:然而我却给个直接的例子告诉你并非如此,用Python之类的讨论 02/22 01:42
77F：→ yauhh:资料结构时,对於linked list是想都不必想的. 02/22 01:42
78F：推 Huangs:Python 也可以自己实作 linked-list 啊 02/22 01:46
79F：→ Huangs:你 Google "python linked-list" 就有许多文章了 02/22 01:46
80F：→ Huangs:怎麽会是"想都不用想"??? 02/22 01:46
81F：→ yauhh:很明白告诉你了,特地做这个东西是白作工. 02/22 01:48
82F：推 Huangs:当效能出现问题时候 就必须要有资料结构的知识 02/22 01:49
83F：→ yauhh:就像现在,给你看了例子,你还是不信. 那我真没辄. 02/22 01:49
84F：→ Huangs:不论你用什麽语言 都要有这些知识 02/22 01:49
85F：→ Huangs:有时甚至为了改善效能而必须用更合适的语言 02/22 01:50
86F：→ Huangs:为什麽是白工？ 两者的时间复杂度可不一样耶 02/22 01:50
87F：→ yauhh:我手上有一本函数语言的演算法书籍,资料结构部份的确什麽都 02/22 02:00
88F：→ yauhh:有,但是独缺linked list. 那你是否觉得搞这个的白痴到不把 02/22 02:01
89F：→ yauhh:linked list列入讨论范围? 02/22 02:01
90F：→ yauhh:很抱歉,我没跟你谈各种资料结构,我只谈linked list. 02/22 02:02
91F：推 Huangs:拿一本书就可以证明 python 里不需要 linked-list? 02/22 02:02
92F：推 Huangs:你还没解释为什麽在python里做linked-list是白工喔 :P 02/22 02:09
93F：→ yauhh:Huangs兄,让我告诉你二件残酷的事实: 1) Erlang的list就是 02/22 12:22
94F：→ yauhh:跟linked list一样的东西,所以我没有理由再实作linked list 02/22 12:22
95F：→ yauhh:2) Erlang基本资料型态根本没有array,所以何必硬说要知道 02/22 12:23
96F：→ yauhh:array跟linked list的差别? 要用array可以挂上array模组, 02/22 12:23
97F：→ yauhh:但是普通程式我根本不用考虑什麽array空间有限的问题. 02/22 12:24
98F：→ yauhh:你不知道Erlang却敢随便说任何语言都要考虑array跟linked 02/22 12:25
99F：→ yauhh:list的差异,我只觉得这是否言过其实了? 02/22 12:26
100F：推 Huangs:那如果现在的case需要 random access，Erlang 怎麽办？ 02/22 13:53
101F：→ Huangs:只好用内建的 linked-list 很慢的操作罗？ 02/22 13:54
102F：→ Huangs:而且你刚讲得不是 python 吗？怎麽又变回 Erlang 了？ 02/22 13:54
103F：→ Huangs:我不知道 Erlang 是否可以用 array 来作 random access 02/22 13:55
104F：→ Huangs:但程式设计师在写Erlang仍然必需意识到这麽问题 02/22 13:56
105F：→ Huangs:如果遇到的case需要大量的random access 02/22 13:56
106F：→ Huangs:那麽不支援random access的语言 可能就存在效能的问题 02/22 13:57
107F：→ Huangs:当效能问题严重时 甚至必需换语言 02/22 13:57
108F：→ Huangs:所以说用任何语言 都要考虑 array 与 linked-list 的差异 02/22 13:58
109F：→ xvid:linked-list是资料结构 怎麽会绑语言呢... 02/22 19:56