[已解决] 获取一个list的最后一个元素, 最有效的方法是什么?

Emacs-general
1

有没有类似car这样, 直接返回最后一个元素值?

找到了 (car (last list))

2

list 应该是一个单链形式的数据结构，必须先知道 list 长度，才能获取尾部元素。恐怕没有如 car 一样有效／高效方法。

last 其实就是 (nthcdr (1- (length list)) list) 的包装。

1 个赞
3

一般是这样, 不过很多list实现的时候, 都会记录尾部的指针, 方便快速追加, 这个指针可以用. emacs可能没这么实现.

4

有尾部指针的应该是双链表，Emacs的List是单链表。

很可惜Emacs没有动态数组的实现。ring.el可以当成动态数组用，不过扩容和插入都不够高效

5

单向链表也可以用尾部指针, 印象中以前接触过一些, 追加太方便了.

不过emacs里的链表可能很多地方要处理环路的问题, 必须遍历, 有可能因为这个放弃了尾部指针优化.

动态数组没怎么接触过.

6 
(defun ll (list)
  (let ((tmp list))
    (while (not (eq nil (cdr tmp)))
      (setq tmp (cdr tmp)))
    (car tmp)))

基本等于 -last。除了没 pred。

(benchmark-run 1000000 (car (last '(1 3 4 5 6))))
(0.213849 0 0.0)
(benchmark-run 1000000 (ll '(1 3 4 5 6)))
(0.14434100000000005 0 0.0)
1 个赞
7

看了下last里调用了safe-length, 而safe-length会检查环路, 增加了部分开销.

safe-length is a built-in function in ‘C source code’.

(safe-length LIST)

Return the length of a list, but avoid error or infinite loop.
This function never gets an error.  If LIST is not really a list,
it returns 0.  If LIST is circular, it returns a finite value
which is at least the number of distinct elements.
1 个赞
8

加个 circular detect 多不了什么开销，last 慢的原因在于 traverse 了两次。

(defun ll-c (list)
  (let ((slow list)
        (fast list)
        res)
    (while (not (or (null fast)
                    (and (null (cdr fast)) (setq res (car fast)))
                    (and res (eq slow fast) (error "circular"))))
      (setq res (cadr fast))
      (setq slow (cdr slow))
      (setq fast (cddr fast)))
    res))

(benchmark-run 1000000 (ll-c '(1 3 4 5 6)))
(0.15273299999999995 0 0.0)

(ll-c '#1=(1 2 3 4 . #1#)) ;; Lisp error: (error "circular")
2 个赞
9

原来如此…