[ Skill ] append1, append, nconc, tconc, lconc, cons 效率对比

https://www.cnblogs.com/yeungchie/

先说结论：cons > tconc, lconc >> nconc > append1, append

append1

1. let((a)
2.     ycTime(
3.         for(i 1 fix(3e4)
4.             a = append1(a i)
5.         )
6.     )
7.     length(a)
8. )
9. ; UserTime  : 12.108453s
10. ; SysTime   : 0.000000s
11. ; WallClock : 12.104178s
12. ; 30000

复制代码

append

1. let((a)
2.     ycTime(
3.         for(i 1 fix(3e4)
4.             a = append(a list(i))
5.         )
6.     )
7.     length(a)
8. )
9. ; UserTime  : 13.654966s
10. ; SysTime   : 0.000000s
11. ; WallClock : 13.651223s
12. ; 30000

复制代码

append1, append 这两个函数操作写链表速度奇慢，因为它将元素追加到末尾的方法需要把整个链表遍历一次，找到最后一个节点再追加。
唯一的好处就是对初学者友好，容易理解和使用，因此尽量在已知数据量不大的前提下，才去使用这两个函数。

nconc

1. let((a)
2.     ycTime(
3.         for(i 1 fix(3e4)
4.             a = nconc(a list(i))
5.         )
6.     )
7.     length(a)
8. )
9. ; UserTime  : 2.995670s
10. ; SysTime   : 0.000000s
11. ; WallClock : 2.994434s
12. ; 30000

复制代码

相比 append 快了一点，但也没有快很多，毕竟只追加 30000 次。
它对于输入变量是具有破坏性的，会直接修改变量，而不像 append 在底层会将数据进行拷贝，因此会快一些，更省内存。

tconc

1. let((a)
2.     ycTime(
3.         for(i 1 fix(3e4)
4.             a = tconc(a i)
5.         )
6.         a = car(a)
7.     )
8.     length(a)
9. )
10. ; UserTime  : 0.001871s
11. ; SysTime   : 0.000000s
12. ; WallClock : 0.001871s
13. ; 30000

复制代码

tconc 会保留链表中最后一个节点，当追加列表时直接操作该节点，因此不需要反复遍历整个链表。car 指向我们期望的链表。
在上面的情况下，相比 append 快了近 5000 倍，已经没有可比性了，所以后面函数把追加次数调整为 60000000 来比较。

1. let((a)
2.     ycTime(
3.         for(i 1 fix(6e7)
4.             a = tconc(a i)
5.         )
6.         a = car(a)
7.     )
8.     length(a)
9. )
10. ; UserTime  : 4.085272s
11. ; SysTime   : 0.000189s
12. ; WallClock : 4.083197s
13. ; 60000000

复制代码

lconc

1. let((a)
2.     ycTime(
3.         for(i 1 fix(6e7)
4.             a = lconc(a list(i))
5.         )
6.         a = car(a)
7.     )
8.     length(a)
9. )
10. ; UserTime  : 4.741206s
11. ; SysTime   : 0.000000s
12. ; WallClock : 4.740194s
13. ; 60000000

复制代码

两者区别在于，tconc 拼接的是一个标量，lconc 拼接的是一个链表。
速度相差不大，看情况来使用吧。

cons

1. let((a)
2.     ycTime(
3.         for(i 1 fix(6e7)
4.             a = cons(i a)
5.         )
6.     )
7.     length(a)
8. )
9. ; UserTime  : 1.865164s
10. ; SysTime   : 0.000000s
11. ; WallClock : 1.865343s
12. ; 60000000

复制代码

这个函数又快不少，它是将元素追加到链表开头，因此不需要遍历元素，也不需要记忆节点。
由于是向前追加，元素顺序可能会跟我们期望的相反，这时候就需要降链表翻转一下，看看速度。

1. let((a)
2.     ycTime(
3.         for(i 1 fix(6e7)
4.             a = cons(i a)
5.         )
6.         a = reverse(a)
7.     )
8.     length(a)
9. )
10. ; UserTime  : 3.655040s
11. ; SysTime   : 0.000000s
12. ; WallClock : 3.649090s
13. ; 60000000

复制代码

翻转增加了一点耗时，速度跟 tconc 和 lconc 差不多。

以上测得的耗时数据受客观环境差异会有所波动是正常的，观察这个时间数量级上的差异即可反映出效率上的优劣。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！