2016年的最后几小时, 随便写写关于Scala和OCaml的一些入门体验好了.

今年对FP语言特别感兴趣, 上了两门Scala的公开课(here and here)和一门OCaml的公开课(here), 在博客中写了一系列的笔记, 课后作业也都认真做完了. 斗胆说这两门语言都算入门了吧... 这里就随便写一下使用这两门语言的感受, 想到哪里写到哪里...

FP语言和之前接触的语言确实不大一样, 比如之前我都有种错觉, 学什么语言只要知道循环/条件/基本类型运算怎么写, 就差不多可以上手了...... 然后遇到了FP, 发现循环语句其实是不必要的... 记得看到过一篇文章, 类比学FP就好像开了很多种车的老司机突然开始学开宇宙飞船, 肯定各种WTF不适应了~

以前谈到FP我只能联想到一些Python里的FP特性: lambda表达式, 高阶函数之类的, 顶多还想到个闭包... 不过Python里面的FP特性和Scala/OCaml里的比起来还是差了不少: i.e. 现在非常希望Python里可以支持pattern matching...

Scala

Scala算是比较亲民的FP语言了(和Java有点像...), 也是我最早接触的FP语言. EPFL的那两门公开课质量很棒, 毕竟是Scala的作者亲自来上的...

• immutable types: 习惯了就好, 就像java里所有东西都是final的, 要修改什么东西的时候改成新建一个, immutable数据的优点就是并行方便啊...
• 一切皆为表达式, specifically, if ...

前一段时间写了不少Python的爬虫程序, 为此还看了极客学院上的一些教程, 现在来简单总结一下. 主要介绍用requests + lxml的方式, scrapy的话之前写过一篇介绍性的文章, 这里就不重复了. 而且感觉一般简单的爬虫项目, 一个Python文件就基本可以搞定, 没必要用scrapy建立一个工程文件夹搞那么正式...

安装需要的库(python2):

pip install requests, lxml

然后在Python程序最开始导入:

import requests  
from lxml import etree

requests基础用法

抓取html内容

用requests获取目标网址的html代码非常简单, 只需要用requests.get方法, 传入网址URL即可.

举个例子, 想要抓取维基语录的HTML内容, 代码很简单:

url = 'https://zh.wikiquote.org/zh-cn/阿爾伯特·愛因斯坦'  
r ...

总结一下用python撸codejam时常用的一些库, 并且给一些简单的例子. 发现用python撸codejam非常合适: codejam的时间要求不严格(4/8分钟), 而且程序只要本地运行. 正好可以使用python简洁的语法和丰富的函数库.

collections

py自带的一些好用的数据结构...
https://docs.python.org/2/library/collections.html

from collections import Counter, deque, defaultdict

itertools

主要是用来穷举的时候它里面一些函数很好用...

https://docs.python.org/2/library/itertools.html

>>> from itertools import product, combinations   
>>> a = 'ABCD'; b='EFG'   
>>> for p in product(a,b):    
print ...

昨天做的一道codejam题目, 这个题目的三种解法都非常有代表性, 特此一记.

题目链接在这里:
https://code.google.com/codejam/contest/8234486/dashboard#s=p2

Elliot's parents speak French and English to him at home. He has heard a lot of words, but it isn't always clear to him which word comes from which language! Elliot knows one sentence ...

总结了一下C++ STL里面用的比较频繁的一些代码片段. (地址: https://github.com/X-Wei/cpp-demo-snippets/tree/master/STL)
cpp文档: http://en.cppreference.com/w/cpp

常用的library主要有:
<algorithm>, <vector>, <queue>, <set>, <map>, <cmath>

另外一个常见的cpp文件开头版本是:

#include <iostream>  
#include <vector>  
#include <algorithm>  
using namespace std;  
#define forloop(i,lo,hi) for(int i = (lo); i <= (hi); i++)  
#define rep(i ...

今天简单介绍一下优先队列(priority queue, 以下简称PQ)这个数据结构的实现.

PQ又叫"堆"(heap), 但是可能优先队列这个名字更容易记忆它的用途: pq是一种队列, 不过不是先进先出(FIFO), 而是每次出队的元素永远是优先级最高的.

logical structure of PQ

个人感觉"堆"这个名字大概源于PQ的(逻辑上的)形状吧: PQ是一种树(tree), 准确的说, 是一种二叉树(binary tree), 说得再准确一点, 它是一种完全二叉树(complete binary tree): 没错, PQ是一种满足某些条件的完全二叉树.

所谓的"完全二叉树", 要满足:

• 除了最后一层, 所有层都排满(没有非空节点)
• 最后一层的所有非空节点都排在左边

一张图可以直观说明, 完全二叉树其实就是长得像这样:

一个完全二叉树能被成为PQ的话, 要满足的条件就是:

对于任何一个节点, 它的优先级都大于左右子节点的优先级.

比如下图 ...

今天总结一下非常有用的快速排序(qsort)算法, 以及由此衍生的一些其他相关算法(Knuth shuffle, quick select, 3-way partition).

快速排序的算法可以用三句话描述:
[Algo]

• 选择基准项(pivot element, 一般取第一个元素为pivot)
• 把数组里所有小于pivot的移动到pivot左边, 大于pivot的移动到右边 ⇒ 此时pivot已经位于最终排序时的正确位置
• 对pivot左右两个数组分别递归进行快速排序

由以上描述可见, qsort是一个递归算法, 我们可以把它的函数声明写成: void qsort(int[] a, int lo, int hi), 表示排序a[lo, hi]之间(闭区间)的所有元素.

quick partition

由上面描述可以见, qsort最关键的是第二步: 把数组元素以pivot分为两部分. 这个操作就是quick partition.

函数声明为: int partition(int[] a, int ...

weighted graph的最短路径问题有三个非常有名的算法, 分别以三个大牛的名字命名, 今天用尽量简洁的篇幅一一介绍.

简单起见(这回只写伪代码好了), 对于图的定义如下:

• node index = {1,2,...,n}
• e[u,v] = distance of edge(u,v); if (u,v) is not an edge, e[u,v]=INF
• 令N=点的数量, M=边的数量

任意两点最短路径: Floyd-Warshall

Floyd算法解决的问题是: 对于任意两个节点s(source)和t(target), 求s到达t的最短路径.

Floyd算法的思想是动态规划:

• 定义d ...

今天总结一下也许是搜索问题里最重要的算法: DFS !

由于树可以看成是一个graph, 这里还是只写对于graph的DFS算法. Graph类的定义还是用每一个节点保存邻居信息:

public class GraphNode{      
    int val;      
    List<GraphNode> neighbors;      
}

为了防止重复, 仍然用一个HaseSet记录走过的节点:

HasheSet<GraphNode> visited = new HasheSet<GraphNode>();

Recursive DFS

首先写递归版本的DFS, DFS就是一条路走到底, 不撞南墙不回头, 所以递归写起来很自然: 每到一个节点, 标记其已经访问过了, 然后对于邻居里面没有访问的节点继续递归进行DFS.

递归的DFS代码非常简洁:

public void DFS(GraphNode nd){      
    System.out.println(nd.val);    
    visited.add(nd);   
    for(GraphNode next: nd.neighbors){   
        if ...

今天总结一下广度优先搜索(BFS). BFS是树/图的遍历的常用算法之一, 对于没有边权重的图来说可以计算最短路径.
由于树的BFS只是图的BFS的一种特殊情况, 而且比较简单不需要visited标记, 这里只写一下图的BFS好了.
先定义一个Graph类, 这里在每一个节点保存邻居信息:

public class GraphNode{   
    int val;   
    List<GraphNode> neighbors;   
}

BFS for trees/graphs

图的遍历需要注意不走重复节点, 所以需要一个HashSet(名字叫visited)来保存哪些节点已经访问过了. 需要注意的是, 在把一个节点放进队列queue的时刻就要把它放进visited, 而不是在队列里取出来的时刻再放.

public void BFS(GraphNode start){   
    LinkedList<GraphNode> q = new LinkedList<GraphNode>();   
    HasheSet<GraphNode> visited = new HasheSet<GraphNode>();   
    q.push(start);   
    visited ...