[ Skill ] append1, append, nconc, tconc, lconc, cons 效率对比
https://www.cnblogs.com/yeungchie/
先说结论:
cons
>tconc, lconc
>>nconc
>append1, append
append1
let((a)
ycTime(
for(i 1 fix(3e4)
a = append1(a i)
)
)
length(a)
)
; UserTime : 12.108453s
; SysTime : 0.000000s
; WallClock : 12.104178s
; 30000
append
let((a)
ycTime(
for(i 1 fix(3e4)
a = append(a list(i))
)
)
length(a)
)
; UserTime : 13.654966s
; SysTime : 0.000000s
; WallClock : 13.651223s
; 30000
append1, append
这两个函数操作写链表速度奇慢,因为它每次追加元素都需要把整个链表遍历一次。
唯一的好处就是对初学者友好,容易理解和使用,因此在知道数据量不大的前提下,才去使用这两个函数吧。
nconc
let((a)
ycTime(
for(i 1 fix(3e4)
a = nconc(a list(i))
)
)
length(a)
)
; UserTime : 2.995670s
; SysTime : 0.000000s
; WallClock : 2.994434s
; 30000
相比
append
快了一点,但也没有快很多,毕竟只追加 30000 次。
它对于输入变量是具有破坏性的,会直接修改变量,而不像append
在底层会将数据进行拷贝,因此会快一些,更省内存。
tconc
let((a)
ycTime(
for(i 1 fix(3e4)
a = tconc(a i)
)
a = car(a)
)
length(a)
)
; UserTime : 0.001871s
; SysTime : 0.000000s
; WallClock : 0.001871s
; 30000
tconc
会保留链表中最后一个节点,当追加列表时直接操作该节点,因此不需要反复遍历整个链表。car
指向我们期望的链表。
在上面的情况下,相比append
快了近 5000 倍,已经没有可比性了,所以后面函数把追加次数调整为 60000000 来比较。
let((a)
ycTime(
for(i 1 fix(6e7)
a = tconc(a i)
)
a = car(a)
)
length(a)
)
; UserTime : 4.085272s
; SysTime : 0.000189s
; WallClock : 4.083197s
; 60000000
lconc
let((a)
ycTime(
for(i 1 fix(6e7)
a = lconc(a list(i))
)
a = car(a)
)
length(a)
)
; UserTime : 4.741206s
; SysTime : 0.000000s
; WallClock : 4.740194s
; 60000000
两者区别在于,
tconc
拼接的是一个标量,lconc
拼接的是一个链表。
速度相差不大,看情况来使用吧。
cons
let((a)
ycTime(
for(i 1 fix(6e7)
a = cons(i a)
)
)
length(a)
)
; UserTime : 1.865164s
; SysTime : 0.000000s
; WallClock : 1.865343s
; 60000000
这个函数又快不少,它是将元素追加到链表开头,因此不需要遍历元素,也不需要记忆节点。
由于是向前追加,元素顺序可能会跟我们期望的相反,这时候就需要降链表翻转一下,看看速度。
let((a)
ycTime(
for(i 1 fix(6e7)
a = cons(i a)
)
a = reverse(a)
)
length(a)
)
; UserTime : 3.655040s
; SysTime : 0.000000s
; WallClock : 3.649090s
; 60000000
翻转增加了一点耗时,速度跟
tconc
和lconc
差不多。