2017-11-08

剑指offer

各个地方：每个函数注意入口处进行有效性判断，这要做到测试在前，编码在后
P32 注意一下设计模式，例如这个最简单的singleton模式
P58 如果要改变输入的输入最好问一下面试官
P49 C++的常亮字符串在一个特殊内存区域，方便指针赋值的时候重用
P59 面试题6 思维的扩展性，从反向联想到栈，从栈联想到递归（当然，用栈的方式更好，从栈转化为递归比较简单，反过来就不简单了，我觉得这可能也是考察点）
P61 对树的各种便遍历方法的非递归实现
P61 很多快速得到最值的问题可以通过堆来实现
P61 红黑树可以保证从根节点到叶节点的最长路径的长度不超过最短路径的两倍
P62 联想：哪两种遍历方式可以唯一的确定一颗二叉树
P94 如果面试题是求解一个问题的最优解，该问题可以划分为几个子问题，整体问题的最优解依赖于子问题的最优解，而且通常子问题会重叠，如斐波那契数列。
P92 通常在二维矩阵中寻找路径可以用回溯法解决（回溯法可以看做是一种暴力搜索），实际上是树的DFS。
递归的代价：函数调用压栈出栈的时空消耗；子问题的重复计算；调用栈溢出。

2017-10-19

Hadoop笔记（二）

前言

研一结束前通过雁栖湖校区大数据的相关课程真真正正的使用了hadoop等工具，研二到了实验室就开始使用七这些工具进行真实场景下的一些简单的大数据分析。在这里进行简单的总结，记录一下之前使用过程中没有用到的一些hadoop功能与工作中的一些小trick。

全局参数配置

由于实验需要，在使用中通常需要抽象出一些外部参数在运行时通过命令赋值。而当参数变多的时候，直接靠args从命令行读入参数开始变得臃肿而不便于维护和使用。比如在我的例子中一共有十多个可调参数，如果每次命令都要赋值显然十分不方便。

好在已经有可以直接使用的参数解析工具包 args4j 可以直接使用。

import org.kohsuke.args4j.CmdLineException;
import org.kohsuke.args4j.CmdLineParser;
import org.kohsuke.args4j.Option;
/**
 * Created by protao on 17-10-17.
 */
public class TestJava {

    public static class SampleCmdOption {

        @Option(name="-h", usage="show help doc")
        public boolean help = false;

        @Option(name="-n", usage="how many time you want print")
        public int n = 1;

        @Option(name="-s", usage="the string you want to print")
        public String s = "hello world";

    }

    public static void showHelp(CmdLineParser parser){
<!-- more -->
        System.out.println("LDA [options ...] [arguments...]");
        parser.printUsage(System.out);
    }

    public static void main(String[] args) {
        //开始解析命令参数
        SampleCmdOption option  = new SampleCmdOption();
        CmdLineParser parser = new CmdLineParser(option);

        try {
	    parser.parseArgument(args);

            if (option.help){
                showHelp(parser);
                return;
            }
            for(int i = 0; i < option.n; i++) {
		System.out.println(option.s);
	    }
	

        }catch (CmdLineException cle){
            System.out.println("Command line error: " + cle.getMessage());
            showHelp(parser);
            return;
        }catch (Exception e){
            System.out.println("Error in main: " + e.getMessage());
            e.printStackTrace();
            return;
        }
	System.out.println("main program");
    }
}

其中Option Annotation中name是在命令行中参数的赋值入口，usage是对该参数的描述，如上述代码，在命令行中运行java TestJava -h会显示：

LDA [options ...] [arguments...]
 -h     : show help doc (default: true)
 -n N   : how many time you want print (default: 1)
 -s VAL : the string you want to print (default: hello world)

运行java TestJava -n 5 -s 23333会显示：

23333
23333
23333
23333
23333
main program

此外在Option中还有一些额外的配置。例如required标注的参数在使用时一定要手动赋值：

1 2	@Option(name="-iamstupid", usage="you must be stupid", required=true) public boolean joke1=true;

这样的话运行的时候就一定要加上-iamstudid。

另外，我们还可以标注对参数的赋值要求，例如上面可以看到在输出的帮助文档中usage显示在冒号的后面，而前面冒号除了参数名称还有一个类似参数类型的标注，这个也是可以手工配置的。

@Option(name="-h", usage="show help doc")
public boolean help = false;

@Option(name="-n", usage="how many time you want print", metaVar="1<=n\<10")
public int n = 1;

@Option(name="-s", usage="the string you want to print", mataVar="String")
public String s = "hello world";

@Option(name="-iamstupid", usage="you must be stupid", required=true)
public String joke1=true;

此时java TestJava -iamstupid -h输出：

LDA [options ...] [arguments...]
 -h         : show help doc (default: true)
 -iamstupid : you must be stupid
 -n 1<=n\<10 : how many time you want print (default: 1)
 -s String  : the string you want to print (default: hello world)

再hadoop集群中需要注意的是第三方jar需要分发到各个节点，2.0之前通过-libjars选项，2.0之后把第三方jar包存放到$HADOOP_HOME/share/hadoop/common下即可。（网上看到的方法，前一种方法我试了没有成功，后一种方法成功了）

然后hadoop主程序读入参数后还需要将参数全局共享到各个Task节点上，通过job的Configuration可以完成这个工作。

// main函数中向job写入参数
Configuration conf = new Configuration();
conf.setInt("max_count", option.max_count);

// map或者reduce中读出参数
Configuration conf = context.getConfiguration();
int max_count = conf.getInt("max_count", 50000);

分布式缓存

一些只读的小文件可以通过这个方式在节点间共享。

// main函数中向job写入路径
DistributedCache.addCacheFile(new Path([String path in hdfs]).toUri(    ), conf);

// map或reduce中，通过DistributeCache读取文件
BufferedReader reader = new BufferedReader(new FileReader((cache    Files[0].toString())));
String s;
while ((s = reader.readLine()) != null) {
// 按行读入文件
}
reader.close();

其他

在新版本中貌似已经弃用IdentityMapper或者IdentityReducer了，直接使用Mapper.class或者Reducer.class就可以完成直接输出的功能。

参考

2017-10-06

程序员的玩具

锋利的bash(1)

记录下自己的shell使用记录。

任务一：

输出绝对路径

详见输出绝对路径一文。

任务二：

把所有错误格式的jpg文件的后缀改为png

for f in ./download/*
do
    head=`od -N2 -t x1 $f | head -1 | sed -e 's/0000000//g' -e  |tr -d '\n'`
    if test $head = 8950
    then
        mv ${f%%.jpg}.jpg ${f%%.jpg}.png
    fi
done

解释：od用于输出文件的八进制、十六进制或其它格式编码的字节，通常用于显示或查看文件中不能直接显示在终端的字符。-N2表示输出两个字符，-t x1是指用十六进制输出。head易于理解。sed是字符串处理命令，-e指有多个命令，s是替换指令。tr又是一种字符串处理命令，-d表示需要删除。

知识点1:测试命令test，可以用在if语句中测试字符串或数字或文件是否满足一些简单的条件。详见RUNOOB

知识点2：字符串操作

2017-09-05

大数据

matplotlib参考

基础

import numpy as np
import matplotlib as mpl
import matplotlib.pyplot as plt

file_path = "result"

with open(file_path) as f:
    lines = f.readlines()

x=[]
y=[]
for line in lines:
    splited = line.split("\\t")
    x.append(splited[0])
    y.append(splited[1].strip())

plt.figure("flow data", figsize=(15,5), dpi=80)
plt.plot(x, y, 'b-', lw=1)
plt.show()

png

进阶

2017-09-01

大数据

浅析Bloom Filter与java实现

概述

布隆过滤器实际上对外表现为一个set类型，可以实现添加元素/判断元素是否存在/并集等操作。需要注意的是布隆过滤器不提供元素的删除功能，这一点特点使得他不能作为常规的集合类型使用，那么它的使用场景是保存大量固定元素的集合，并判断一个新到来的元素是否已经存在在这个集合中,s所谓“过滤器”也是因此得名。他以一定误报率（不在的元素判断为在）为代价，减少了大量存储空间。

原理

BF主要需要包含一个长度为m位的位图，和k个相互独立的哈希函数，哈希函数的值域在0到m-1之间。
如果希望加入一个元素，那么将该元素输入k个哈希函数得到k个索引，将BitArray中对应索引位置置1即可。
如果希望查询一个元素是否存在，同样将该元素输入k个哈希函数，得到k个索引，如果k个索引位置中任一位置不存在，如果所有位置都是1，那么该元素就有很大可能存在。

java实现：

public class BloomFilter<E> {

    private BitSet bf;
    private int bitArraySize = 100000000;
    private int numHashFunc = 10;

    public BloomFilter() {
        bf = new BitSet(bitArraySize);
    }

    public void add(E obj) {
        int[] indexes = getHashIndex(obj);

        for (int index : indexes) {
            bf.set(index);
        }
<!-- more -->
    }

    public boolean contains(E obj) {
        int[] indexes = getHashIndex(obj);

        for (int index : indexes) {
            if (bf.get(index) == false) {
                return false;
            }
        }
        return true;
    }

    public void union(BloomFilter<E> other) {
        bf.or(other.bf);
    }

    protected int[] getHashIndex(E obj) {
        int[] indexes = new int(numHashFunc);

        long seed = 0;
        byte[] digest;
        try {
            MessageDigest md = MessageDigest.getInstance("MD5");
            md.update(obj.toString().getBytes());
            digest = md.digest();

            for (int i=0; i < 6; i++) {
                seed = seed ^ (((long)digest[i] & 0xFF))<<(8*i);
            }
        } catch (NoSuchAlgorithmException e) { }

        Random gen = new Random(seed);

        for (int i = 0; i < numHashFunc; i++) {
            indexes[i] = gen.nextInt(bitArraySize);
        }

        return indexes;
    }
}

伪正率

由于一个哈希函数应将一个元素等概率的映射到BitArray的一位，因此，某一位为1的概率是：

\[1/m\]

一个元素经过一个hash映射到BitArray后，某一位仍然是0的概率

\[1-1/m\]

因为一个元素需要经过k个hash映射，因此一个元素加入BF中，某一位仍然是0的概率：

\[(1-1/m)^k\]

同理，存放n个元素的BF，某一位是0的概率：

\[(1-1/m)^{kn}\]

存放n个元素的BF，某一位是1的概率：

\[1-(1-1/m)^{kn}\]

某k个不同比特位被这前面n个元素置1的概率

\[(1-(1-1/m)^{kn})^k\]

当m很大的时候

\[ \lim_{x\rightarrow+\infty}(1-(1-1/m)^{kn})^k \]

\[ =\lim_{x\rightarrow+\infty}(1-(((1-1/m)^m)^{nk/m})^k\]

\[ =((1-e^{-kn/m})^k \]

这个推导不是完全正确的,因为它假定每一位被设置的概率独立。但即使它是近似的,我们也可以看出误报的概率会随着m(数组)的比特数的增加而变小,随着n(插入元素)的数量增加而增大。并且即使我们通过没有假设独立的方式推导，还是可以得到相同的结果。

最优的哈希函数数量

我们假设\[p=e^{-kn/m}\]\[k=-m/nln(p)\]
他是当m趋近于无穷大时，存放n个元素的BF，某一位是1的近似概率。我们的目标函数是误报率，即\[ ((1-e^{-kn/m})^k \]
出于求导的方便考虑，我们对该函数的对数求导\[ ln(((1-e^{-kn/m})^k) \]
带入p，得到
\[ -m/n*ln(p)ln(1-p) \]

根据对称性，当p=0.5时，伪正率最低。所以最优的k应该等于ln2*m/n。

思考

在计算机科学中，我们常常会碰到时间换空间或者空间换时间的情况，即为了达到某一个方面的最优而牺牲另一个方面。Bloom Filter在时间空间这两个因素之外又引入了另一个因素：错误率。在使用Bloom Filter判断一个元素是否属于某个集合时，会有一定的错误率。也就是说，有可能把不属于这个集合的元素误认为属于这个集合（False Positive），但不会把属于这个集合的元素误认为不属于这个集合（False Negative）。在增加了错误率这个因素之后，Bloom Filter通过允许少量的错误来节省大量的存储空间。

参考

http://blog.csdn.net/dadoneo/article/details/6847481
hadoop in action
维基百科