读书人

利用hashtable跟time函数加速Lisp程序

发布时间: 2013-10-14 12:54:46 作者: rapoo

利用hashtable和time函数加速Lisp程序
程序功能是从一个英文文本中得到单词表,再得到押韵词表。即输出可能这样开始:
a ameoeba alba samba marimba...
这样结束:
...megahertz gigahertz jazz buzz fuzz
有了这么一个表,诗人会爽很多。

算法:得到单词表后,先把单词反序,用sort函数对所有反序单词排序,排好后再反序。

我叽里呱啦地写完了,用了630KB的2100行的文本来测试一下。time一下main函数,30多秒……现在用了如题的两个工具,程序跑到了0.08s!

首先,我处理重复单词的算法超级低效,先是在read-word函数里,不管是否当前单词已记录,都把当前单词记录下来,然后:
(setf words (delete-duplicates words :test #'equal :end n))
用delete-duplicates函数只保留相同单词的最后一个。
该函数的工作原理是两个两个比较,然后把前者丢弃掉,如果:from-end是true的话,那把后者丢弃掉。显然的是,它要比较很多,如果一个单词重复很多次的话,那要经过很多轮的比较,元素移动很多。具体是如何经过很多轮的、为什么很慢的,我也不懂,望高手指点。
如果我在添加新单词的时候:
(defun write-word (to)(with-open-file (str to :direction :output:if-exists :supersede)  (map nil #'(lambda (x)(fresh-line str)(princ x str))  (xform #'nreverse(sort (xform #'nreverse words)      #'string<)))))
事实上,这照搬了《Ansi Common Lisp》的代码。

代码见:https://github.com/lzwjava/rhymes

读书人网 >编程

热点推荐