1 初级排序算法

排序算法关注的主要是重新排列数组元素，其中每个元素都有一个主键。排序算法是将所有元素主键按某种方式排列（通常是按照大小或是字母顺序）。排序后索引较大的主键大于等于索引较小的主键。

排序算法类的模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

public class Example{
    public static void sort(Comparable a[]){}
    private static boolean less(Comparable a, Comparable b){
        return a.compareTo(b) < 0;
    }
    private static void exch(Comparable[] a, int i, int j){
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
    private static void show(Comparable[] a){
        for(int i = 0;  i < a.length; i++){
            System.out.print(a[i] + " ");
        }
        System.out.println();
    }
    public static boolean isSort(Comparable[] a){
        for(int i = 1; i < a.length; i++){
            if(less(a[i], a[i - 1]))
                return false;
        }
        return true;
    }
    public static void main(String[] args){
        //从标准输入读入字符串，排序后输出
        Integer[] a = new Integer[]{1,34,55,66,7};
        sort(a);
        assert isSort(a);
        show(a);
    }
}

• 排序成本模型：研究排序算法时，需要计算比较和交换的次数。对于不交换元素的算法，计算访问数组的次数。
• 额外内存使用：排序算法的额外内存开销和运行时间同等重要。排序算法可分两类：除了函数调用所需的栈和固定数目的实例变量之外无需额外内存的原地排序算法，以及需要额外内存空间来存储另一份数组副本的其它排序算法。
• 数据类型：上述排序算法模板适用于任何实现了Comparable接口的数据类型。例如，Java中封装的Integer和Double，以及String和其他许多高级数据类型（如File和URL）都实现了Comparable接口，因此可以直接调用这些类型的数组作为参数调用我们自己实现的排序方法。

例如——用快排对N个随机的Double数据进行排序：

1
2
3
4
5

Doulbe[] a = new Double[N];
for(int i = 0; i < N; i++){
    a[i] = StdRandom.uniform();
    Quick.sort(a);
}

观察

运行时间和输入本身相对无关，主要取决于问题规模
例：统计文件中三个数和为0的数量

1
2
3
4
5
6
7
8
9
10
11
12
13

public class ThreeSum{
    public static int count(int a[]){
        int N = a.length, cnt = 0;
        for(int i = 0; i < N; i++){
            for(int j = i + 1; j < N; j++){
                for (int k = j + 1; k  < N; k++){
                    if(a[i] + a[j] + a[k] == 0)
                        cnt += 1;
                }
            }
        }
    }
}

一种表示计时器的抽象数据类型：

1
2
3
4
5
6
7
8
9
10

public class StopWatch{
    private final long start;
    public StopWatch(){
        start = System.currentTimeMillis();
    }
    public double elapsedTime(){
        long now = System.currentTimeMillis();
        return (now - start) / 1000.0;
    }
}

1 基础编程模型

Java 四类八种类型

• 整型：byte, short, int, long
• 浮点型：float, double
• 布尔型：boolean
• 字符型：char

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

public static int binarySearch(int[] a, int key){
    int left = 0;
    int right = a.length - 1;
    while(left <= right){
        int mid = left + ((right - left) >>1);
        if(a[mid] > key){
            right = mid -1;
        }
        else if(a[mid] < key){
            left = mid + 1;
        }
        else{
            return mid;
        }
    }
    return -1;
}

数组

1. 颠倒数组中元素顺序

   1 2 3 4 5 6 7

   //注意 n 值、for 循环边界、以及循环体内 n - 1 - i int n = a.length; for(int i = 0; i < n/2; i++){ int temp = a[i]; a[i] = a[n - 1 - i]; a[i - 1 - i] = temp; }

2. 矩阵相乘

   1 2 3 4 5 6 7 8 9

   //假设a[n][n], b[n][n], c[n][n] int n = a.length; for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ for(int k = 0; k < n; k++){ c[i][j] += a[i][k] * b[k][j]; } } }

今天想来说说二分查找，因为最近笔者的同学在面试时正好遇到了，而自己以前还真没认真研究过。

说起二分查找，对算法和数据结构比较熟悉的都知道这是一个复杂度为 O(logN) 的典型分治算法，它的用途是在有序数组中查找某个数是否存在。但就是这么听起来很普通的算法却常常很难完全写对。

• 据D.Knuth在《计算机程序设计的艺术 第3卷：排序和查找》书中指出，虽然二分查找1946年就公诸于世，但1962年才有人写出没有 bug 的二分查找程序。
• 除此之外，就连我们熟悉的 Java 语言里 JDK 的二分查找 java.util.Arrays.binarySearch 中也曾有一个隐藏了10年之久bug!（文末附bug链接）不过，这个bug已经不是什么新鲜事了，是 JDK5 时代的产物了，不过我们可以再来回顾一下，看看我们平常是不是就在写bug，是不是真应了那个表情包“哟，写bug呢”🙊

1 问题来源

记得一开始学逻辑回归时候也不知道当时怎么想得，很自然就接受了逻辑回归的决策函数——sigmod函数:

与此同时，有些书上直接给出了该函数与将 $y$ 视为类后验概率估计 $p(y=1|x)$ 等价，即

并给出了二分类(标签 $y\in(0,1)$)情况下的判别方式：

但今天再回过头看的时候，突然就不理解了，一个函数值是怎么和一个概率联系起来了呢？有些人解释说因为 $h_{\theta}(x)$ 范围在0~1之间啊，可是数值在此之间还是没说明白和概率究竟有什么关系。所以，前几天看了一些资料，对个人而言比较好理解的还是从广义线性模型（Generalized Linear Models, GLM）来解释，至少这种方法能从概率出发直接推出 sigmod 函数。实际上，线性回归和逻辑回归都是广义线性模型的特例，从此出发，得到对应的决策函数就比较自然了。

环境

• 操作系统：Ubuntu 14.04
• Hadoop版本：Hadoop 2.6.5
• JDK版本：OpenJDK 1.7

创建Hadoop用户

创建用户

1

sudo useradd -m hadoop

为新用户设置密码

1

sudo passwd hadoop

为新用户添加权限

1

sudo adduser hadoop sudo

如果失败，则切换到root用户下，修改/etc/sudoers文件，将hadoop用户添加进去。

Python语言

简要概括一下Python语言在数据分析、挖掘场景中常用特性：

1. 列表（可以被修改），元组（不可以被修改）
2. 字典（结构）
3. 集合（同数学概念上的集合）
4. 函数式编程（主要由lambda()、map()、reduce()、filter()构成）

Python数据分析常用库

本文主要针对使用编译好的二进制文件安装mysql
如在mysql官网 (https://dev.mysql.com/downloads/file/?id=467234) 下载的：
mysql-5.6.35-linux-glibc2.5-x86_64.tar.gz

检测当前机器上是否已经安装mysql：
1、检测：

1

rpm -qa|grep -i mysql

2、卸载：

1
2
3

rpm -e mysql-libs-5.1.61-4.el6.x86_64 --nodeps
-e:--erase=<package>+   erase (uninstall) package
--nodeps:忽略依赖关系

3、开始安装mysql：
当前我使用的用户是 fighter

持久化选项

• 快照持久化：获得存储在内存里面的数据在某个时间点上的副本。
• AOF持久化（只追加文件append-only file）：会在执行命令时，将被执行的写命令写到硬盘里。

两种方案既可同时使用，也可单独使用，或都不使用，具体结合数据及应用决定。