{文章笔记}Storm创始人Nathan Marz:反馈即一切

读到一篇十分好的文章:是对Storm创始人的专访。

1、学习新的编程语言是提高的好方法,要不仅仅学习其语法,要掌握它的习惯用法,并且用其写出实际的应用。
2、努力提高自己解决问题的能力,而不仅仅是关注知识点。
3、反馈即一切,错误的决定只能靠反馈来修正,快速开发出产品原型,收集反馈,才能使产品做的更好。
4、开源对初创公司意义重大,所以做有益于初创公司发展,降低其成本的开源软件都是有益的。
5、一本好书Big Data:Principles and Best Practices of Scalable Realtime Data Systems,书中有架构大数据系统的方法论和最佳实践。
6、系统应该能从容恢复人为故障。
7、提高写作技能的方法是多写,然后从别人的讨论中,找到自己写作的问题,哪里写的不好。

8、避免做出通用的设计,除非透彻理解了问题域,应该直接打造原型,学习问题域,再重新设计系统。设计软件系统就是学习如何在行进中开发。

《程序员》:设计软件系统时,你会采用哪些步骤?

Nathan:我认为,设计软件系统完全就是学习如何在行进中开发。我应用一种被我称之为“面向痛苦编程”(Suffering-Oriented Programming)的原则,使学习最大化,浪费最小化。关于这种方式的详细介绍我已写在博客上(http://nathanmarz.com/blog/suffering-oriented-programming.html)。其核心思想是,避免做出“通用”和“可扩展”的设计,除非你已透彻理解了问题域(Problem Domain)。

相反,你应该直截了当地尽快打造出可用原型,继而通过迭代和改进学习问题域,当你对问题域的盘根错节有了清晰的理解后,再回过头来重新设计系统,使之具备通用和可扩展等特性。到最后一步才开始收紧代码,优化性能。归纳为三个步骤,就是“先使之可能,再使之漂亮,后使之快速。”

9、好程序员痴迷于提高自己的核心技能,有把事情做成的心态,让系统真正可以运行重要的多,而不是设计完美的系统。

《程序员》:你面试过许多程序员,那些最优秀的人有什么共同之处?

Nathan:最好的程序员都痴迷于提高自身的核心技能,他们喜欢探索新的编程语言和想法。好程序员的另一个重要特征是,他们都有“把事情做成”的心态。与完美的设计相比,让系统真正可以运行要重要得多。还有一点,他们都知道除非先让系统运转起来,然后从中学习,否则别想得到完美的设计。

C++容器中如何通过reverse_iterator删除元素

容器里面的erase的参数是iterator类型的,并且没有reverse_iterator类型为参数的删除函数,那如何删除reverse_iterator类型指向的元素呢?

只要了解下reverse_iterator就很容易做到,reverse_iterator其实是对iterator的一个封装,详细可以查看reverse_iterator的文档,这里简单说一下。

iterator i;

&*(reverse_iterator(i)) == &*(i - 1)

可以从reverse_iterator.base()取得相应的iterator,将其前向移动一个位置就是对应的reverse_iterator指向的位置,使用test.erase(--r_it.base())即可删除。

reverse_iterator和iterator的指向关系

参考文献:

http://stackoverflow.com/questions/1830158/how-to-call-erase-with-a-reverse-iterator

http://www.cplusplus.com/reference/iterator/reverse_iterator/

源码编译GCC的正确方法

懒得看文档的同学来看这里,GCC的编译稍多几步,如果不知道直接./configure然后make会栽。。。

关键几条,其中建立objdir这一步不能省。

tar xzf gcc-4.8.0.tar.gz
cd gcc-4.8.0
./contrib/download_prerequisites
cd ..
mkdir objdir
cd objdir
$PWD/../gcc-4.8.0/configure --prefix=/opt/gcc-4.8.0
make
make install

来源:http://stackoverflow.com/questions/12650493/checking-for-suffix-of-object-files-configure-error-cannot-compute-suffix-o

{思考之美}Tarjan算法求无向图割顶(cut vertex) v0.1

连通的无向图G(V, E)的割顶是V中的一点,使得去掉此点后原图不连通。最简单的方法就是枚举V中的点,依次删除进行判断图是否连通,这需要O(V * (V + E))的复杂度。另外就是要Tarjan算法通过一遍DFS的信息求得所有的割点。

无向图的DFS会生成一颗路径树T,并且由于是无向图,图G只能有正向边(T边)和反向边(B边),路径树中存在正向边,故两点在树中连通,则必然在原图G中连通,因此需要考虑的是如何在T删除点u后,除了正向边,原图G中的反向边是否可以将原图连通。

u为割点有以下两种情况:

  • u是T的根节点,并且有>=2个孩子节点
  • u不是T的根节点,但u的孩子节点v中,存在v为根的子树内的所有点都无法到达u的祖先。

证明:

  • u是根节点,并且有>=2个孩子节点,如果删去u则各个孩子节点为根的子树之间无法连通,并且由于是无向图G中反向边不会在子树之间存在,故无边将子树之间连通,故原图G也不连通。
  • u不是T的根节点,在树T上删除点u,则u孩子节点各个子树的点无法只通过正向边同其它点连通,因此如果u孩子节点子树的后向边里也没有指向u祖先的点,那么u孩子节点子树的点就无法到达其它点,故u为割点。反过来,如果u子节点v的子树都存在到达u祖先的边的话,则这些子树之间可以通过先到达u的祖先,然后连通。

因此我们需要记录u点到达根节点的距离level,以及其孩子节点v所在子树能到达的u的祖先节点。到达根节点的距离可以在DFS过程中求得。关键是如何求出x子树所能到达的father(x)的祖先节点。最简单的方法就是记录v子树能到达的祖先节点集合anc(v),那么u子树能到达的祖先节点是所有孩子节点anc(v)的并集以及u能到达的祖先节点集合,然后删除不是u祖先节点的节点。这里就是Tarjan算法的精妙之处(PS:意思就是傻逼了,我也不知道robert tarjan是怎么想出来的,如果你知道的话请留言告诉我)了,上面的这个操作正好可以利用level来进行判断通过记录low(v),表示v以及v后代中能到达的u的祖先中最接近根的点。这样就可以在DFS过程中,计算low(v) = min(后向边到达的祖先点u(u不是v的父节点), low(v的后代))。

对于u不是T根节点的情况,如果存在v使level(u) <= level(low(v)),则u为割点。

Scheme is a Pretty Language II

I hate this, “int tmp, tmp2;”, why not “int tmp1, tmp2;” ?
Why? I do not know the future.

求得n次方根 {y^n}=x,可以转换为求 y=\frac{x}{y^(n-1)} 的不动点,求不动点可以使用x, f(x), f(f(x)) \ldots 不断逼近的方法,直接使用 y=\frac{x}{y^(n-1)} 求会使得抖动过大,使用平均阻尼来解决,如果一次平均阻尼无法解决,那么使用多次平均阻尼,求解 y=\frac{x}{y^(n-1)} 需要 floor(\log_2 n) 次平均阻尼。

I know what i think, but i do not know what i do!

(define (iterative-improve enough? improve)
 (lambda (guess)
   (let ((next (improve guess)))
     (if (enough? next guess)
         guess
         ((iterative-improve enough? improve) next)))))

(define (fixed-point f guess)
 (define tolerance 0.000001)
 (define (enough? v1 v2)
   (< (abs (- v1 v2)) tolerance))
 ((iterative-improve enough? f) guess))

(define (compose f g)
 (lambda (x)
   (f (g x))))

(define (repeat-func f n)
 (if (= n 0)
     (lambda (x) x)
     (compose f (repeat-func f (- n 1)))))

(define (average-damp f)
 (lambda (x)
   (average x (f x))))

(define (average a b)
 (/ (+ a b) 2))

(define (log2 x) (/ (log x) (log 2.0)))

(define (pow a n)
 (define (iter a n result)
   (cond ((= n 0) result)
         ((even? n) (iter (* a a) (/ n 2) result))
         (else (iter (* a a) (/ (- n 1) 2) (* a  result)))))
 (iter a n 1))

(define (nth-root x n)
 (fixed-point ((repeat-func average-damp
                            (floor (log2 n)))
               (lambda (y) (/ x (pow y (- n 1)))))
              1.0))

Scheme is a Pretty Language

好久没写博文了,也不是不想写,上个月刚毕业,在要毕业的时候心情是很复杂的,最怀念的还是大学里的那些朋友,虽然以后肯定还会见面,但失去的一起在大学生活的那种快乐却永远也回不来了。

其实原来放在草稿里的时候这里还有一段,但删掉了,就像我总是把文章放进草稿里一样

最近在看SICP,这是很久之前就想看却留到现在的好多书其中一本,别的不多说了,反正我觉得fp是我目前觉得最能体现计算本质的编程范式,这本书也是一本体现计算本质的佳作(这是废话)。

由于做习题,所以需要对写出函数进行测试,手动敲总是不方便的,所以就写了下面两个函数,第一个给输入输出case进行测试,第二个给输入case和一个标准函数然后进行测试。写这两个测试函数的时候,我第一次体会真正的只关注求解问题的思考方式。

(define (test-func func test-case)
 (map (lambda (m)
        (equal? (apply func (car m)) (car (cdr m))))
      test-case))
(define (map func enum)
 (if (null? enum)
     nil
     (cons (func (car enum))
           (map func (cdr enum)))))
(define (check-func test-func sample-func test-case)
 (map (lambda (m)
        (equal? (apply test-func m)
                (apply sample-func m)))
      test-case))
(define (map func enum)
 (if (null? enum)
     nil
     (cons (func (car enum))
           (map func (cdr enum)))))

test-func使用的例子

(define (fast-expt n b a)
 (if (= n 0)
     a
     (if (even? n)
         (fast-expt (/ n 2) (* b b) a)
         (fast-expt (/ (- n 1) 2) (* b b) (* a b)))))
(define test-case '(((1 5 1) 5)
                   ((0 5 1) 1)
                   ((6 5 1) 15625)
                   ((7 5 1) 78125)
                   ((5 9 1) 59049)))
(display (test-func fast-expt test-case))

输出: (#t #t #t #t #t)

check-func使用的例子

(define (fib n)
 (fib-iter 1 0 0 1 n))
(define (fib-iter a b p q count)
 (if (= count 0)
     b
     (if (even? count)
         (fib-iter a
                   b
                   (+ (* p p) (* q q))
                   (+ (* 2 p q) (* q q))
                   (/ count 2))
         (fib-iter (+ (* b q) (* a q) (* q p))
                   (+ (* b p) (* a q))
                   p
                   q
                   (- count 1)))))

(define (sample-fib n)
 (sample-fib-iter 1 0 n))
(define (sample-fib-iter a b n)
 (if (= n 0)
     b
     (sample-fib-iter (+ a b) a (- n 1))))
(define test-case '((0) (1) (2) (3) (4) (5) (6) (7) (8) (9) (10)))
(display (check-func fib sample-fib test-case))

输出: (#t #t #t #t #t #t #t #t #t #t #t)

前段时间想写一篇{思考之美},主题就是“不管往回几年重来到现在都会比现在更好,也明确知道在未来也会这么想,但却不能改变这样的状况”。 现在想想,如果我是从SICP入门编程的,那现在又会是什么样子呢。

PS:在找那个想法的时候突然发现evernote里还有半篇没写完的“{思考之美}求解序列的最小循环节及此问题扩展”,我都忘记了,可又想什么时候才能写完呢?