实现算法时的一些感想

  1. 学好各个语言,各个库的 API;不要钻牛角尖:自己去实现得写好多行,而库正确调用,也就2,3行就能完成。:写的时候我会掉入陷阱,自己去折腾与要实现的算法无关的事情。比如 K-NN 算法的基本形式,我一度走偏,去研究如何统计出现次数最多值。耽误很多时间
  2. 我没有去苛求提高程序的运行效率,只是想把算法的过程掌握并实现出来。所以程序很短小,20多行。可是真的动手做的时候,要至少写200行废掉的代码,一步一步把数学上很简单一个符号就能表示的东西编程代码。数学这些算法,不像写程序时要实现的一个小函数那么简单,中间数据传递,数据类型的转换每一步都是坑。要是用 Py2,还有编码的坑(我不敢跳进去,谁敢谁跳吧)。
  3. 编码一时爽,事后回顾???。有时候一行代码的实现有些奇怪,第二天自己看的时候都得想一会。同理,去读别人的代码,如果对方编码习惯不好,很乱,还不写注释,是真的没有心情读下去。
  4. 树的数据结构我没学过。所以今天 2017-07-21 想实现 kd 树的时候头疼了好久。根本不知道怎么入手处理。树应如何构造一团雾?后来是去研究 Scipy 的 源代码 ,目前还在看代码,结构很清晰,各个部分功能是什么能看明白,但是技术实践上就比较头大。比如类的概念,还是没理解透。加上这些变量都是啥没有注释说明,更是一团雾。所以一边开着 Pycharm 读代码,一边开着 CodeRunner 去跑摘出来的代码片段,去猜测要实现的是什么

class node(object):
    if sys.version_info[0] >= 3:
        def __lt__(self, other):
            return id(self) < id(other)

        def __gt__(self, other):
            return id(self) > id(other)

        def __le__(self, other):
            return id(self) <= id(other)

        def __ge__(self, other):
            return id(self) >= id(other)

        def __eq__(self, other):
            return id(self) == id(other)

因为昨天实现出了一个 k-nn 原始形式(没用 kd 树),所以能体会到出要计算的量随着维度增加而增加。翻书时知道 kd 树能提高运行效率,还挺开心的。结果 Scipy 的代码里有这么一句:

For large dimensions (20 is already large) do not expect this to run significantly faster than brute force. High-dimensional nearest-neighbor queries are a substantial open problem in computer science.

看来维数灾难始终是个灾难

Comments
Write a Comment