厚积薄发¶

算法基础¶

算法分析¶

算法缺失一个公共的表达方法，很难有一个通用衡量，但是LLVM IR却可以补充这个空白。可以充分利用 LLVM 的分析功能来实现算法的精确分析。由于IR是通用的，并且IR指令对应到机器执行时间也都是固这的。所以完全可以拿到这样一样计算模型啊。差不多精确的知道其需要执行多少时间。并且用一个树形依赖来计算出来。所以生一个函数复杂度是能够精确的计算的。这样解决了采样的精度不足的问题，指令值收集速度，需要的资源太多，太慢的问题。算法的时间复杂度和空间复杂度-总结

算法的维度计算¶

时间复杂度并不是表示一个程序解决问题需要花多少时间，而是当问题规模扩大后，程序需要的时间长度增长得有多快。 http://www.matrix67.com/blog/archives/105

the design of a program is rooted in the layout of its data. The data structures don’t define every detail. but they do shape the overall solution.

http://blog.csdn.net/zolalad/article/details/11848739，常见的算法时间复杂度由小到大依次为：Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2n)＜Ο(n!) NP问题，就是基于复杂的度来说的。

O(1)表示基本语言的执行次数是一个常数，一般来说，只要算法中不存在循环语句，其时间复杂度就是O(1). 其中 O(log2^n) O(n),O(nlog2n),O(n2)O(n3)称为多项式时间。

而O(2^n)与0(n!)称为指数时间，计算机科学家普遍认为多项式时间复杂度的算法是有效算法，称为P(Polynomial)类问题，而后指数时间复杂的算法称为NP(Non-Deterministic Polynomial 非确定多项式）问题。

一般来说多项式级的复杂度是可以接受的，很多问题都有多项式级的解——也就是说，这样的问题，对于一个规模是n的输入，在n^k的时间内得到结果，称为P问题。有些问题要复杂些，没有多项式时间的解，但是可以在多项式时间里验证某个猜测是不是正确。比如问4294967297是不是质数？如果要直接入手的话，那么要把小于4294967297的平方根的所有素数都拿出来，看看能不能整除。还好欧拉告诉我们，这个数等于641和6700417的乘积，不是素数，很好验证的，顺便麻烦转告费马他的猜想不成立。大数分解、Hamilton回路之类的问题，都是可以多项式时间内验证一个“解”是否正确，这类问题叫做NP问题

树¶

二叉树，红叉树

树形结构深度不平衡，导致搜索的效率不稳定，所以为提高效率人们开始研究平衡二叉树，而红黑树就是平衡树的一种。使搜索的效率趋于稳定。

变量->数组->链表->树->图->拓扑

树形结构是嵌套结构的一种，嵌套结构其实就是像分形无穷，其实数据结构来说，链表就是表示各种各样的嵌套结构。对应的语言模式那就是递归。

递归函数可以全局变量来记录深度，可以用函数内部的static变量来记录，或也就是所谓的静态变量。总之这一段空间，就看你怎么样用与规划分配了。

树型结构是最常见的数据结构，例如文档目录，各种协义，以及html,xml等等都是树型结构。遍历方法分为深度优先，还是广度优先。所以在扁历生成一个列表的序列会大有不同。同时对于各种文档的解析来实现。也都是从上到下，从前往后。采用的递归式解析。一般用状态机+ vistor 模式来进行解析。

class Node:
    def __init__(self):
         self.parent
         self.children = []

    def tranverse(self):
         for child,in self.children:
            tranverse(child)

    def parse(self):
        Root = Node(none)

        for line in readline():
            state = state(line)
            newRoot =  New Node
            NewRoot.parent = Root
            Root.children.append(NewBoot)

环的实现¶

简单用array实现的环只需要处理指针最大值时，然后到首。

if index == max
   index = 0

index = value% max

硬件到逻辑变量的对应¶

这个是基础，基本的硬件单位有bit,byte,WORD,DWORD。逻辑单位有各种int, short int,long int, 各种float,32bit float以及64bit 的float. 以及char,string 等等。

然后是各种复杂逻辑结构的表示。

array,vector,list,matrix,tuple,map/dict等等。

再往后复杂的tree,图，class之间是可以建立的关系的。

结构化对比的实现¶

最简单一种遍历，从一个之中，从查找另一个。效率是n*n.

再好的一点，如果有序的话，就可以不回头。也就是最常匹配算法。就像现在diff算法一样。

但是如果再有一些结构的话，可以把key值或者路径还是最常匹配来得。具体到每一个最具体的项的再用简单的方法。关键是key map成list是不是有重复的，顺序无关的。这些会影响算法如何实现。

如何进行tree-based structured diff.

例如 http://diffxml.sourceforge.net/

另外一种做法，那是把结构化的变成 linebased. 这就需要先把结构flat化。例如https://en.wikipedia.org/wiki/Canonical_XML。就是这样的一种。也可以叫做正交化。现在已经有做的成熟的商业化工具diffDog. http://www.altova.com/diffdog/xml-diff.html

http://archiv.infsec.ethz.ch/education/projects/archive/XMLDiffSlides.pdf.

结构化的对比，难点是检测移动。

另外一种那就是tree2tree的对比算法. https://www.ietf.org/rfc/rfc2803.txt DomHash的算法。

编辑距离的计算，可以采用路径+ node本身hash等等。需要两个信息。一个是自身的信息。另外一个那就是它的位置移动。编辑距离同时还可以看到一个人在一个系统中移动轨迹。

X-Diff: An Effective Change Detection Algorithm for XML Documents. http://www.inf.unibz.it/~nutt/Teaching/XMLDM1112/XMLDM1112Coursework/WangEtAl-ICDE2003.pdf node signature + hash的做法。 A Semantical Change Detection Algorithm for XML http://www.inf.ufpr.br/carmem/pub/seke07.pdf，这个方法比较接近自己的算法。

基于xml的一种混合结构化数据对比方法。

看来我的这个东东也是可以发表的。

可以采用样式表的方法，决定对比方法。看一下html中样式表是如何添加的。就可以实现了。或者采用xpath的方式。

KFIFO¶

linux kernel是一个大宝藏，如果想找各种实现，去kernel的source tree 里找一找吧。例如ring buffer一个实现。ring buffer 实现的原点，如何实现下标的循环，但是由于自计算机整数的溢出来实现，再加取模计算，再把大小变成2的n次幂，这样取模就又变成了取与计算。 http://www.cnblogs.com/Anker/p/3481373.html

quicksort¶

这个是其实分段排序方法，与二分法是对应的。如果上千万排序怎么的办。直接发分段，然后再逐段的拼接呢。中间再字符串搜索功能。

Practice.of.Programming at Page 46.

基本结构对比¶

初级结构¶

int, float, string,enum

中级结构¶

array,list,hash,tree

#.array, 固定，但是存储效率高，采用动态的数据，可能会引起大量的数据搬运，所以初始空间的设置，以及增长方式是要考虑的重点。 #. list 最灵活，但是只能顺序用link来存取，所有二分法，排序算法等等基本上没有什么效果，因为其只能知道与其相关的信息。

对其profiling就要操作的效率。例如每一个查询，修改花了多久。例如在STL的时候，例如把deque, 换成list的效率的明显变化。

hash 把结合array,list的优点，也是优化空间最大的地方，就像一个矩形，面积恒定。但是如何分配长宽才能达到高效。而决定长宽分配是与存储对象本身的特性以及hash函数共同决定的。使其存储上更像array. 所以对其性能分析，就要查看其结构利用率。
tree 结合list,array,使其更像list,但是操作效率尽可能像array. 因为在树的排序，就可以用二叉树，平衡树，来加速寻找的过程。用于分树的key,相当于array中index.

高级结构¶

struct, 可以根据需求来定制，但是结构固定，也是为什么python的对象中固定元数据部分要struct表示。而动态部分用class来表示。

同时也可以把相应的操作函数相联起来，这个是比中级结构更强一些点，
class, 添加了数据本身的存取进行权限定义，另外通过继承可以添加，重写原来的struct.

而所有的这些变化点都是根据需要来的。

当把你的问题搞清楚了，采取的数据结构也搞清楚了。这个时候采用什么样语言与库就一目了然了。

队列¶

Queue, 先入先出的队列, LioQueue,PriorityQueue,Qeueue,deque,heapq. 以及 namedtuple, Counter,OrderedDict,defaultDict.

粒子群算法¶

都是GA的一种，它简化一些，去掉了交叉与变异。模拟鸟群找食的过程。它根据自己当前最优值与群体中最优值来进行更新。

蚁群算法¶

蚁群算法，还是根据蚁群，每一个蚂蚁也向外传播信息。每一个蚂蚁根据自身的精况来决定是否接受全局的信息。通过触角，其实就是人类交流中的局部信息，完成一个任务传递是相互遇见的频率，这个是代表什么？不同的激活个数，导致大脑的差异，这里就是提取信息的不同在环境密集情况下，如果探测到危险就停止。 http://open.163.com/movie/2015/1/6/H/MAFCPCJCV_MAFDA5K6H.html 计算概率密度，通过局部的计算。我想这可能是新的算法

计算模型¶

reduce 模式
scan 模式
map 模式
count_if 模式
match_if 模式
filter
group
约束求解，z3等等，并且在excel中也带有大量的solver,其实不需要从零开始写。

执行的模型¶

在需要并行执行的操作提供了，进程，线程，协程的基本模型。

当然在使用协程是最近才提供出来，可以在编程语言内部支持，相对于线程来不需要那些各种数据的锁机制。

同时实现异步的操作，现在async,await,yield,yield from的等等的支持，在实现各种复杂的建模的时候就会特别方便。

例如javascript系统event的机制实现了多进程打进了自己的语言机制.

而python 现在也支持async,await,yield等支持并行。

这样对于这个系统比较完备了。

进程通信¶

从课本上讲的 socket,信号量机制。到后面JSON,以及 protobuf , apache thrift socket 由简单的点对点到 n:n 的 zeromq , 这个由我想起了expect 实现的n:n 的通信。

quick start 给了一非常好玩的入门。

经过几分钟试用。Racket 集成了传统语言与符号语言的优势。符号语言的特点那就是非常的简练。把替换用到极致有M4那种功效，但时具有传统语言作用范围的概念，弥补了m4这个不足。继承了 lisp 与scheme 简单，直接用函数语言的() 来搞定一切。以及看函数式编程比较别扭，现在是越看越顺了。并且用起来也非常的简练。

并且还有对象，列表，map等等。

Racket 可以用直接处理图，并且有人拿来画图与做动画。

用racket 当做脚本使用 http://docs.racket-lang.org/guide/intro.html#%28tech._repl%29 。

当做系统脚本就得像bash那样的的清爽。同时具有python的强大。现在看来racket还是不错的。这里有全面的 racket-lang reference

代码最简单的方式那就是像bash一样，然后可以对输入与输出进行控制，并用管道，并且语法也要简单。这个正是函数式编程要达到目的。

(cmd para) 不正是bash的语法格式吗，并且直接用()执行一次替换，bash也正是这么来的。

并且直接直接系统命令，并且接近bash一样的简练。 http://rosettacode.org/wiki/Execute_a_System_Command#Racket

#lang racket
(system "ls")

;; capture output
(string-split (with-output-to-string (λ() (system "ls"))) "\n")

计算机程序的构造和解释¶

通过这本书真正明白计算的构造过程，并且只要支持局部或者全局的静态变量，就可以实现各种复杂的计算。

可以用let 实现不断的替换，从而实现电路的模拟。函数具有内部的状态，可以实现各种复杂的模拟，这个内部状态可以用python yield来实现。

parallel-execute过程。直接实现函数体的并行执行。

关键的就是这种符号替换执行。这个是难点是如何实现的。代码执行像数学公式一样。

对于现实仿真的问题，那就是如实现tick函数，同时也要保持依赖的问题。后台调用的是 phyx car 来模拟的, 采用最简单的迭代做法，每一个基本过程，然后不断迭代的过程。就是每一个tick函数如何写的问题。可以用recket 把迭代与传递链结合起来。

这也就是微分与与数值计算的模型。

racket的发展史。 https://www.zhihu.com/question/22785256

列表的模式匹配¶

原来没有明白，scheme中,cd,cdr用途，也就是头:余下的。就是各种模式匹配的基本模式啊。

curry 理论¶

传统函数理论，就是参数的处理，但是如何curry的处理，函数输入可以是无限的。就像一个递归一样。这样就把函数输入处理统一化了。其背后那就是个lambda理论。

程序的三大基础¶

以及其特珠性，

变量，这里的变量就是符号，各种符号定义。只是基本原语不一样。

所以这个语言基础，那就是lambda calculus,就是不断的替换，直到原语为止。数据结构也就是符号以及符号的集合，也就是列表两种。

其语法解释就像shell一样，shell 以行为单位，然后以空格作为分隔符。并且第一个符号为命令。其余的为参数。关键是什么时候发生替换。

在racket 中用单引号表示符号，不对其替换，只有let 中才对符号进行替换。

在clips中符号定义很宽泛，用任意可以打算ASCII码，作为符号，而非打印字符找了几个当做定界符。同时拿;来当comments,

符号语言与一般语言的区别，那就在于多一种符号的定义。而在Clips中可以用?,$?开头当做变量。

并且也匹配的原语，匹配单个符号，多个符号。不同语言里不是不同的。在 clips中，?是单个符号，而在$?是多个符号。

ruler,有自己的属性，以及前置条件，以及推导条件。然后根据前置条件来决定下一步是谁。不确的因素就是下一个要问的问题。

函数度编程特点¶

所有的过程都是函数，并且严格地区输入与输出。
没有变量或赋值，变量被参数替代
没有循环（递归代替）
函数的值只取于它的参数的值与求得参数值先后或者调用函数的路径我关。
函数是一类值

introduction¶

haskell offical web

debug and profiling¶

ghci 是可以直接以 :break line 类似于vim的命令直接在解释器下断点。并且是集成一起的。 ghci-debugger . profiling 见此 haskell profiling .

同时还得安装 apt-get install ghc-dynamic ghc-prof

库的管理¶

cabal 类似于 perl 的cpan,以及python的pip.

映射与函数的表示¶

haskell是与数学最接近的编程语言，haskell可以求解哪些隐式函数。它应该是用笛卡尔基再加过虑来实现的。并且是从数理的脚度来进编程的。

Monad是从另一个角度来分函数进行区分，那就是有限响应与无限响应滤波器，那就是有没有全局变量在函数内部，所谓纯虚函数，就是我们平时编程中最常见的函数，输出只与输入有关。没有记忆状态。而haskell把这个出来进行深入区分，就提出Monad的机制 http://zhuoqiang.me/what-is-monad.html。

http://www.zhihu.com/question/19635359

简单的语法¶

where 相当于 python中 context中with功能。

type C语言的中typedef 的功能。

Hoogle 在线的帮助文档引擎 xs 可变列表的剩余部分。

如何快速读haskell 代码¶

How_to_read_Haskell .

Thinking¶

Higher Order Functions 这个其实不是什么新东西，在perl里都有例如sort 排序，你可以使用各种方法传递给它。这个要用函数指针，并且能够动态生成代码最好。但是在这里支持会更好。在这里要习惯，函数内部调用函数。函数可以相互组合。

更加接近数学定义。用Haskell摆弄函数确实就像用Perl摆弄字符串那么简单。特别适合公式的推导。

– Main.GangweiLi - 19 Sep 2013

偏函数 可以预置一些参数的参数。

– Main.GangweiLi - 19 Sep 2013

lazy evaluate 这样能够把多层的循环压在一层去实现。并且采用了值不变的方式。

– Main.GangweiLi - 20 Sep 2013

前缀，中缀，后缀 表达式以前没有注意它，在hackell中，这几种是可以转换的，一般函数调用采用是前缀表达，操作符采用的中缀表达，那后缀在什么时候用呢

– Main.GangweiLi - 20 Sep 2013

表表操作 haskell的list类似于tcl中列表，可以嵌套，但是操作符不一样。

– Main.GangweiLi - 20 Sep 2013

产生列表 是不是可以集合，例如数列产生会很方便，但是它的列表可是无限长的，这更加适合公式的证明了。你可以用cycle,repeat等等来得到。

– Main.GangweiLi - 20 Sep 2013

函数式编程的一般思路 先取一个初始的集合并将其变形，执行过滤条件，最终取得正确的结果

– Main.GangweiLi - 20 Sep 2013

利用模式匹配来取代switch。

– Main.GangweiLi - 20 Sep 2013

特殊变量_类似于perl 的$_.

– Main.GangweiLi - 20 Sep 2013

*函数*本质就是种映射，这个ghci中最能体现，你可以指定其定义域与值域，以及这个这个映谢，函数的原型就这个。