{"id":1294,"date":"2012-06-28T01:41:31","date_gmt":"2012-06-27T17:41:31","guid":{"rendered":"https:\/\/www.highflybird.com\/blog\/?p=130"},"modified":"2012-06-28T01:41:31","modified_gmt":"2012-06-27T17:41:31","slug":"%e4%ba%8c%e5%8f%89%e6%a0%91","status":"publish","type":"post","link":"https:\/\/www.highflybird.com\/blog\/?p=1294","title":{"rendered":"\u4e8c\u53c9\u6811"},"content":{"rendered":"

\u8fd9\u4e2a\u662f\u7528lisp\u6765\u6784\u5efa\u4e8c\u53c9\u6811\u3002
\n\u5bf9autolisp\u6765\u8bf4\uff0c\u6784\u5efa\u4e8c\u53c9\u6811\u662f\u4e00\u4e2a\u96be\u9898\uff0c\u56e0\u4e3alisp\u6ca1\u6709\u6307\u9488\uff0c\u6240\u4ee5\u6bd4\u8f83\u56f0\u96be\u3002
\n\u4e0b\u9762\u662f\u5b9e\u73b0\u7684\u4ee3\u7801\u3002
\n<\/p>\n

[codesyntax lang=”lisp”];;;=============================================================
\n;;;\u7528AutoLISP\u6784\u5efa\u4e00\u4e2a\u4e8c\u53c9\u6811(Construct a Binary Search tree)
\n;;;\u4ece\u4e2d\u95f4\u5206\u5f00\uff0c\u76f4\u5230\u5206\u5f97\u53ea\u662f\u5269\u4e0b\u4e24\u4e2a\u5143\u7d20\u6216\u8005\u4e00\u4e2a
\n;;;\u6b64\u7ed3\u6784\u7528\u4e8e\u67e5\u627e\u4e00\u4e2a\u5143\u7d20\uff0c\u4f7f\u5f97\u5355\u6b21\u67e5\u627e\u7684\u65f6\u95f4\u4e3aO(n) = log(n)
\n;;;————————————————————-
\n;;;\u8f93\u5165: Lst \u4e00\u4e2a\u5df2\u7ecf\u6392\u5e8f\u7684\u8868\uff0c\u53ef\u4ee5\u62d3\u5c55\u6b64\u8868\u4e3a\u70b9\u8868\u6216\u5176\u4ed6\u8868\u3002
\n;;;\u8f93\u51fa: \u4e00\u4e2a\u4e8c\u53c9\u67e5\u627e\u6811
\n;;;Author:Highflybird in Shenzhen,China,2012-06-15
\n;;;=============================================================
\n(defun BTree (lst \/ L R)
\n (cond
\n ( (cddr lst) ;the length of list > 2
\n (setq R lst)
\n (repeat (\/ (length lst) 2) ;Split it
\n (setq L (cons (car R) L)) ;Left part of list
\n (setq R (cdr R)) ;Right part of list
\n )
\n (cons (car R) ;middle number as the first.
\n (cons (BTree (reverse L)) ;recurse Left part
\n (BTree (cdr R)) ;recurse Right part
\n )
\n )
\n )
\n ( (cdr lst) ;just two elements
\n (cons (cadr lst) (car lst)) ;the right node is empty.
\n )
\n ( lst
\n (car lst) ;if just one,the node is an element.
\n )
\n )
\n)<\/p>\n

;;;=============================================================
\n;;;\u7528AutoLISP\u4ece\u4e8c\u53c9\u6811\u4e2d\u67e5\u627e\u4e00\u4e2a\u5143\u7d20(Search a key in binary tree)
\n;;;\u6bcf\u6b21\u67e5\u627e\u603b\u662f\u4ece\u4e2d\u95f4\u5f00\u59cb\uff0c\u5982\u679c\u4e0d\u662f\uff0c\u5927\u4e8e\u4e2d\u95f4\u7684\u5c31\u67e5\u627e\u53f3\u8fb9\uff0c\u5c0f\u4e8e
\n;;;\u4e2d\u95f4\u5219\u67e5\u627e\u5de6\u8fb9\uff0c\u76f4\u5230\u539f\u5b50\u6216\u8005\u70b9\u5bf9\u8868\u3002
\n;;;\u56e0\u4e3a\u6811\u7684\u6700\u5927\u6df1\u5ea6\u4e0d\u8d85\u8fc7log(n)\uff0c\u6545\u5355\u6b21\u67e5\u627e\u7684\u65f6\u95f4\u4e3aO(n)<=log(n)
\n;;;————————————————————-
\n;;;\u8f93\u5165: \u8981\u67e5\u627e\u7684Key\uff0c\u5df2\u7ecf\u6784\u5efa\u597d\u7684\u4e8c\u53c9\u67e5\u627e\u6811\uff0cn\u67e5\u8be2\u7684\u6700\u5927\u8282\u70b9\u6570
\n;;;\u8f93\u51fa: \u5982\u679c\u627e\u5230\uff0c\u8fd4\u56de\u627e\u5230\u7684Key\u7684\u4f4d\u7f6e\u3002\u5426\u5219\u8fd4\u56denil
\n;;;Author:Highflybird in Shenzhen,China,2012-06-15
\n;;;=============================================================
\n(defun BFind (key Tree n \/ L R i)
\n (if (atom Tree) ;if it’s an atom,
\n (if (= key Tree) 0) ;set the index as 0
\n (if (= (setq L (car Tree)) key) ;if left node = key
\n (\/ n 2) ;the index is the middle number.
\n (if (atom (setq R (cdr Tree))) ;if the right node is an atom
\n (if (= R key) 0) ;and right node = key, set the index as 0
\n (if (> L key) ;if left node > key
\n (BFind key (car R) (\/ n 2)) ;recurse Left
\n (if (setq i (BFind key (cdr R) (\/ (1- n) 2))) ;otherwise recurse right
\n (1+ (+ (\/ n 2) i)) ;must add the index
\n )
\n )
\n )
\n )
\n )
\n)<\/p>\n

;;;=============================================================
\n;;;\u4ee5\u4e0b\u7528\u4e8e\u6d4b\u8bd5\uff0c\u7528\u4e86\u51e0\u79cd\u529e\u6cd5\u5bf9\u4e00\u4e2a\u6709\u5e8f\u7684\u6570\u7ec4\u67e5\u627e(For test)
\n;;;\u6570\u7ec4\u4e3a\u7b49\u5dee\u6570\u5217\uff0c\u4ece2.5\u5f00\u59cb\uff0c\u5dee\u4e3a1, \u4f8b\u5982:(2.5 3.5 4.5 5.5 ….)
\n;;;\u67e5\u627e\u65b9\u6cd5:\u5305\u62ec\u4e8c\u53c9\u6811,\u6298\u534a\u67e5\u627e,vl-position,member,assoc,\u76f4\u63a5\u67e5.
\n;;;\u5982\u679c\u6b64\u7a0b\u5e8f\u7528\u4f18\u5316\u7f16\u8bd1\uff0c\u5219\u662f\u66f4\u80fd\u63d0\u9ad8\u4e8c\u53c9\u6811\u7684\u67e5\u627e\u548c\u6784\u5efa\u901f\u5ea6
\n;;;=============================================================
\n(defun c:test (\/ e j k n lst lst1 Tree v x)
\n (initget 7)
\n (setq v (getvar “LOCALE”))
\n (if (= v “CHS”)
\n (setq j (fix (getreal “n\u8bf7\u8f93\u5165\u4e00\u4e2a\u6570\u7ec4\u5927\u5c0f(\u5982\u679c\u8f93\u5165\u6570\u7ec4\u8fc7\u5927\uff0c\u53ef\u80fd\u4f1a\u5bfc\u81f4\u505c\u6b62\u54cd\u5e94): “)))
\n (setq j (fix (getreal “nPlease enter the length of a list (a big number maybe cause nonresponse): “)))
\n )<\/p>\n

(setq x (+ 1.5 j))
\n (setq k (1- j))
\n (setq lst nil)
\n (setq lst1 nil)
\n (repeat j
\n (setq lst (cons x lst))
\n (setq lst1 (cons (cons x k) lst1))
\n (setq x (1- x))
\n (setq k (1- k))
\n )
\n (Benchmark ‘(setq lst (vl-sort lst ‘<) N (length lst)) “Vl-sort” 1)
\n (Benchmark ‘(setq Tree (BTree lst) N N) “Construct Binary tree” 1)
\n (benchmark ‘(setq Array (makearr lst vlax-vbdouble)) “Construct Safearray” 1)<\/p>\n

(setq k (\/ N 10))
\n (princ (strcat “n\u4ee5\u4e0b\u5bf9\u6bcf\u4e2a\u51fd\u6570\u91cd\u590d\u4e86” (itoa K) “\u6b21\u6d4b\u8bd5\u3002”))<\/p>\n

(setq x -7.5)
\n (Benchmark ‘(repeat k (setq e (BFind x Tree N)) (setq x (+ x 10))) “BinaryTree” 1)<\/p>\n

(setq x -7.5)
\n (Benchmark ‘(repeat k (setq e (bfind1 x Tree N)) (setq x (+ x 10))) “BinaryTree1” 1)<\/p>\n

(setq x -7.5)
\n (benchmark ‘(repeat k (setq e (HalfSeek x Array)) (setq x (+ x 10))) “HalfSeek” 1)<\/p>\n

(setq x -7.5)
\n (Benchmark ‘(repeat k (vl-position x lst) (setq x (+ x 10))) “vl-position” 1)<\/p>\n

(setq x -7.5)
\n (Benchmark ‘(repeat k (cdr (assoc x lst1)) (setq x (+ x 10))) “Assoc” 1)<\/p>\n

(setq x -7.5)
\n (Benchmark ‘(repeat k (- N (length (member x lst))) (setq x (+ x 10))) “Member” 1)<\/p>\n

;(setq x -2.5)
\n ;(benchmark ‘(repeat N (Search x lst) (setq x (1+ x))) “Search Directly” 1) ;\u8fd9\u4e2a\u65b9\u6cd5\u8fc7\u6162<\/p>\n

;;\u4ee5\u4e0b\u663e\u793a\u90e8\u5206\u67e5\u627e\u7ed3\u679c
\n (princ “n\u4ee5\u4e0b\u663e\u793a\u7528\u4e8c\u53c9\u6811\u5bf9\u5341\u4e2a\u6570\u5b57\u7684\u67e5\u627e\u7ed3\u679c\u3002”)
\n (setq x -2.5)
\n (repeat 20
\n (if (setq e (BFind x Tree j))
\n (princ (strcat “n\u53d1\u73b0\u5728” (itoa e)))
\n (princ (strcat “n\u6ca1\u53d1\u73b0” (rtos x)))
\n )
\n (setq x (1+ x))
\n )
\n (gc)
\n (princ)
\n)<\/p>\n

;;;============================================================
\n;;;\u7528AutoLISP\u6298\u534a\u6cd5\u67e5\u627e
\n;;;\u9996\u5148\u6784\u9020\u4e86\u4e00\u4e2a\u5b89\u5168\u6570\u7ec4\uff0c\u8fd9\u6837\u4f7f\u5f97 nth\u66f4\u5feb\u3002
\n;;;\u7136\u540e\u4ece\u4e2d\u95f4\u627e\u8d77\uff0c\u5982\u679c\u5927\u4e8e\u4e2d\u95f4\uff0c\u5c31\u627e\u53f3\u8fb9\uff0c\u5c0f\u4e8e\u5219\u627e\u5de6\u8fb9\uff0c\u76f4\u5230\u627e
\n;;;\u627e\u5b8c\u3002\u8fd9\u4e2a\u6ca1\u7528\u9012\u5f52\uff0c\u5728\u5185\u5b58\u4e0a\u53ef\u80fd\u4f1a\u7a0d\u5fae\u6709\u4f18\u52bf\uff0c\u4f46\u662f\u5bf9\u4e8e\u901f\u5ea6\uff0c
\n;;;\u5176\u5b9e\u8ddf\u4e8c\u53c9\u6811\u76f8\u5dee\u4e0d\u5927\u3002
\n;;;\u4f18\u70b9: \u53ef\u4ee5\u4e0d\u7528\u9012\u5f52\uff0c\u6548\u7387\u53ef\u4ee5\u66f4\u9ad8\u3002
\n;;;\u7f3a\u70b9: \u662f\u8981\u6784\u7b51\u5b89\u5168\u6570\u7ec4\uff0c\u4e0d\u662f\u6240\u6709\u7684\u8868\u90fd\u53ef\u4ee5\u8f6c\u5316\u4e3a\u5b89\u5168\u6570\u7ec4.
\n;;;\u8f93\u5165: \u8981\u67e5\u627e\u7684key\uff0c\u548c\u5b89\u5168\u6570\u7ec4L\u3002
\n;;;\u8f93\u51fa: \u5982\u679c\u627e\u5230\uff0c\u8fd4\u56de\u627e\u5230\u7684Key\u7684\u4f4d\u7f6e\u3002\u5426\u5219\u8fd4\u56denil
\n;;;Author:Highflybird in Shenzhen,China,2012-06-15
\n;;;============================================================
\n(defun MakeArr (L DataType \/ n a)
\n (setq n (length L))
\n (setq a (vlax-make-safearray DataType (cons 0 (1- n))))
\n (vlax-safearray-fill a L)
\n)
\n(defun HalfSeek (key L \/ Nmin Nlen Nmax Nmid Nval)
\n (setq Nmin 0)
\n (setq NLen (1+ (vlax-safearray-get-u-bound L 1)))
\n (setq Nmax (1- NLen))
\n (setq Nmid (\/ Nlen 2))
\n (setq Nval (vlax-safearray-get-element L Nmid))
\n (while (and (\/= Nval key) (<= Nmin Nmax))
\n (if (> Nval key)
\n (setq Nmax (1- Nmid))
\n (setq Nmin (1+ Nmid))
\n )
\n (setq Nmid (\/ (+ Nmax Nmin) 2)
\n Nval (vlax-safearray-get-element L Nmid)
\n )
\n )
\n (if (= nval key)
\n Nmid
\n )
\n)<\/p>\n

;;;============================================================
\n;;;\u7b80\u5355\u7684LISP\u641c\u5bfb\uff0c\u6328\u4e2a\u5730\u627e\uff0c\u627e\u5230\u4e3a\u6b62\uff0c\u5bf9\u6392\u5e8f\u548c\u672a\u6392\u5e8f\u7684\u5747\u53ef\u7528\u3002
\n;;;\u4f46\u662f\u5355\u6b21\u67e5\u627e\u5e73\u5747\u65f6\u95f4\u4e3aO(n)
\n;;;============================================================
\n(defun Search (key lst \/ i x)
\n (setq x lst)
\n (setq i -1)
\n (while (and x (\/= (car x) key))
\n (setq x (cdr x))
\n (setq i (1+ i))
\n )
\n)<\/p>\n

;;;============================================================
\n;;;\u6d4b\u8bd5\u7528\u51fd\u6570
\n;;;============================================================
\n(defun Benchmark (func funName times \/ t0 t1 res)
\n (setq t0 (getvar “TDUSRTIMER”))
\n (repeat times
\n (setq res (eval func))
\n )
\n (setq t1 (* (- (getvar “TDUSRTIMER”) t0) 86400))<\/p>\n

(princ (strcat “nnIt takes: ” (rtos t1 2 6) ” Seconds for ” funName))
\n (princ (strcat “.nTotal times: ” (itoa times)))
\n (princ (strcat “.nSpeed is: ” (rtos (\/ t1 times) 2 6) ” Seconds\/times.”))
\n (princ “nThe result is: “)
\n (princ res)
\n)<\/p>\n

;;;\u5982\u679c\u7528cond\u51fd\u6570\uff0c\u901f\u5ea6\u76f8\u5dee\u5f88\u5c11\uff0c\u6545\u53ea\u505a\u4fdd\u7559
\n(defun BFind1 (key lst n \/ x k)
\n (cond
\n ( (atom lst)
\n (if (= key lst)
\n 0
\n )
\n )
\n ( (and (atom (car lst)) (atom (cdr lst)))
\n (cond
\n ( (= key (car lst)) -1)
\n ( (= key (cdr lst)) 1)
\n )
\n )
\n ( (= (setq x (car lst)) key)
\n (\/ n 2)
\n )
\n ( (> x key)
\n (bfind1 key (cadr lst) (\/ n 2))
\n )
\n ( (setq k (bfind1 key (cddr lst) (\/ (1- n) 2)))
\n (1+ (+ (\/ n 2) k))
\n )
\n )
\n)<\/p>\n

(defun c:ccc()
\n (setq n 0 )
\n (repeat 10
\n (princ “nN is :”)
\n (princ (- n (\/ n 2) 1))<\/p>\n

(princ “na N is :”)
\n (princ (\/ (1- n) 2))
\n (setq n (1+ n))
\n )
\n (princ)
\n)
\n[\/codesyntax]<\/p>\n","protected":false},"excerpt":{"rendered":"

\u8fd9\u4e2a\u662f\u7528lisp\u6765\u6784\u5efa\u4e8c\u53c9\u6811\u3002 \u5bf9autolisp\u6765\u8bf4\uff0c\u6784\u5efa\u4e8c\u53c9\u6811\u662f\u4e00\u4e2a\u96be\u9898\uff0c\u56e0\u4e3alisp\u6ca1\u6709\u6307\u9488\uff0c\u6240\u4ee5\u6bd4\u8f83\u56f0<\/p>\n

Read More<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"ngg_post_thumbnail":0,"footnotes":""},"categories":[9],"tags":[15],"class_list":["post-1294","post","type-post","status-publish","format-standard","hentry","category-programming","tag-15"],"_links":{"self":[{"href":"https:\/\/www.highflybird.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/1294","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.highflybird.com\/blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.highflybird.com\/blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.highflybird.com\/blog\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.highflybird.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1294"}],"version-history":[{"count":0,"href":"https:\/\/www.highflybird.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/1294\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.highflybird.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1294"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.highflybird.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1294"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.highflybird.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1294"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}