提高Lisp性能 - cons vs append and foreach vs while/nth对比

st788796

More and more of you are finding that you have to deal with this goofy language called AutoLISP. Here are a couple items I pulled together related to some lisp “best practices”. Both apply to optimizing performance when processing large “lists” of data.

Thanks,

Nate.

   CONS versus APPEND

The cons function adds an element to the beginning of a list. The append function can be used to give the equivalent of adding an element to the beginning or end of a list.

Using the cons function can be MUCH faster than using append to build up a large list.

We'll run two tests to create a dummy list of 10,000 integer numbers. The first test is using the "cons" function. Appload and type test1 [enter] at the command prompt.

[pcode=lisp,true](defun c:test1 ( / )
   (setq i 1)
   (setq lst nil) ; start out with a blank list
   (repeat 10000
     (setq lst (cons i lst)) ; add next element to beginning of list
     (setq i (1+ i))
   )
   (setq lst (reverse lst)) ; put list back into correct order
   (princ)
)[/pcode]

The second test yields the same result but uses the "append" function:

[pcode=lisp,true](defun c:test2 ( / )
   (setq i 1)
   (setq lst nil) ; start out with a blank list
   (repeat 10000
     (setq lst (append lst (list i))) ; append next element on to end of list
     (setq i (1+ i))
   )
   (princ)
)[/pcode]

The first test using "cons" builds the 10,000 element list in memory in less than 0.01 seconds (on my T61p).The second test using "append" builds the exact same 10,000 element list in memory but takes a full 3.55 seconds to execute ( ! ). Dealing with large lists, it appears that the "cons" function is many, many times faster.

构造10,000元素表，Cons 用时 0.01 , append 用时 3.55

FOREACH versus WHILE / NTH

Let's say you need to cycle through a huge list, one list element at a time. There are two different functions that can cycle through a list, "foreach" and "nth" combined with a "while" loop. When dealing with a very large list, the "foreach" function can be much faster than using a while loop / nth function to index through the list.

These tests use the 10,000 element list held in memory created be either of the above two tests. This next test uses "foreach" to cycle through the 10,000 element list.

[pcode=lisp,true](defun c:test3 ( / )
   ; use 10,000 element "lst" created by test1 or test2
   (setq find_int (getint "\nFind integer="))
   (setq foundit nil)
   (foreach x lst
     (if (AND (not foundit) (= x find_int))
       (progn
         (setq foundit T)
         (princ " found")  
     ) )   
   )
   (princ)
)[/pcode]

This next test does the same thing but uses a "while" loop and the "nth" function to index its way through the 10,000 element list:

[pcode=lisp,true](defun c:test4 ( / )
   ; use 10,000 element "lst" created by test1 or test2
   (setq find_int (getint "\nFind integer="))
   (setq foundit nil)
   (setq ix 0)
   (setq slen (length lst))
   (while (AND (not foundit)(< ix slen))
     (if (= (nth ix lst) find_int) ; look for match
       (progn ; Found the target element
         (setq foundit T)
         (princ " found")  
     ) )
     (setq ix (1+ ix))   
   )
   (princ)
)[/pcode]

For the test, looking for integer value 5000 (halfway into the list). The "foreach" function finds and exits in less than 0.01 second. The while loop using the "nth" function finds and exits in 0.07 seconds. Using foreach is significantly faster in processing this large list.

原文地址: http://www.cppblog.com/85940806/articles/66489.html

MasterObjects

从学LISP开始，就知道cons的效率要比append高，当时不知所以然，随着时间的推移，了解的知识多了，这可以从数据结构的角度解释。

LISP的表应该是个单向链表结构，一个元素的尾指针指向下一个元素的头指针，指针就是数据存储的内存地址。

CONS仅仅是把一个元素的尾指针指向一个表的头指针上，一次内存写操作就执行完了。
而由于LISP的单向链表结构，APPEND函数要先遍历所有表元素到达尾部元素的尾指针，才能把它指向要APPEND的元素的头上，如果数据量大的情况下，速度就很慢了。

如果LISP表结构是双向链表的话，效率就是一样的。可惜ADESK公司不是这么设计的LISP表存储结构。

st788796

个人理解对 List 处理时如果每个处理不遗漏，While foreach  repeat mapcar 是一样的，看个人喜好，如果中间需要跳出，就加上条件用 while

MasterObjects

st788796 发表于 2013-5-8 18:01

                               
登录/注册后可看大图

个人理解对 List 处理时如果每个处理不遗漏，While foreach  repeat mapcar 是一样的，看个人喜好，如果中间 ...

说的对，其实对于现在计算机发展这么迅速的情况下，CPU,内存都不是10多年20多年前可想象的了，代码算法的好坏在普通应用上看不出太大的区别，因为计算机现在运算太快了，内存也太大了。

但是从计算机编程角度来说，研究算法还是具有普遍意义的。既然我们爱好编程，深究下没什么坏处。

fjb54007

正需要，谢谢楼主分享

/db_自贡黄明儒_

Car. vs. Last结果怎样？

newer

/db_自贡黄明儒_ 发表于 2014-11-14 22:24
Car. vs. Last结果怎样？

不用说了，链表结构，CAR最快，除非双链表。

veryCDxp

偶然間看到這篇文章，感覺自己在寫lisp的時候忽略了性能方面的問題，有的也該改良一下了

sicky111

谢谢分享。