0%

发表于 更新于 分类于
本文字数： 5.7k 阅读时长 ≈ 5 分钟

计数排序不是比较排序，他将数据的值转化为键存储在额外空间中，时间复杂度是线性的。他要求输入的数据必须是有确定范围的整数。

算法说明：

  1. 找出待排数组中的最大，最小元素
  2. 统计数组中每个值为 i 的元素出现的次数，存入索引数组的第 i 相中
  3. 对所有计数累加
  4. 反向填充目标数组：元素 i 放到新数组第 C[i] 位置，美方一个元素 C[i] - 1

时间/空间复杂度：O(n+k)

普通实现

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
32
33
34
35
36
37
38
39
public class CountingSort {
    public static void main(String[] args) {
        int[] arr = new Random().ints(0, 100).limit(10).toArray();
        System.out.println("Origin: " + Arrays.toString(arr));
        int[] result = countingSort(arr);
        System.out.println("After:  " + Arrays.toString(result));
    }

    private static int[] countingSort(int[] arr) {
        // 遍历数组，得到最大值
        int max = arr[0];  // 这里之前写的是 max = 0; 如果原数组包含负数就挂了。。
        for (int j : arr) {
            if (max < j) {
                max = j;
            }
        }
        
        // 根据这个值新建一个用于计数的数组, 比如原数组最大值为 2，新建的计数数组为 [0, 1, 2]，所以声明长度的时候为 max + 1
        int[] bucket = new int[max + 1];
        // 再次遍历数组，将对应的 bucket 下标坐 ++ 操作
        for (int i : arr) {
            bucket[i]++;
        }

        // 遍历 bucket 数组，将统计结果塞到新建结果集中
        int[] result = new int[arr.length];
        int index = 0;
        for (int i = 0; i < bucket.length; i++) {
            while (bucket[i] > 0) {
                result[index] = i;
                index++;
                bucket[i]--;
            }
        }
        return result;
    }
}
// Origin: [36, 7, 70, 84, 69, 65, 88, 11, 16, 87]
// After:  [7, 11, 16, 36, 65, 69, 70, 84, 87, 88]

步骤和思路很都简单明了，容易理解

稳定性

但是上面的实现有一个弊端，就是，他是不稳定的。。。。

所谓的稳定性，简单来说，如果原数组中，有两个相等的值 arr[i], arr[j]，在排序后他们的前后顺序还保持一致，那么就是稳定的。

好处：稳定的算法，第一个键排序的结果可以当作第二次排序的输入使用

PS：这个说法我大致有感觉，但是具体还是没把握。。。

保证稳定性的实现

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
public class CountingSort {
    public static void main(String[] args) {
        int[] arr = new Random().ints(0, 10).limit(10).toArray();
        System.out.printf("%-10s: %s%n", "Origin", Arrays.toString(arr));
        int[] result = countingSort(arr);
        System.out.printf("%-10s: %s%n", "After", Arrays.toString(result));
    }

    private static int[] countingSort(int[] arr) {
        int max = getMax(arr);

        // 根据这个值新建一个用于计数的数组, 比如原数组最大值为 2，新建的计数数组为 [0, 1, 2]，所以声明长度的时候为 max + 1
        int[] bucket = new int[max + 1];
        // 再次遍历数组，将对应的 bucket 下标做 ++ 操作
        for (int i : arr) {
            bucket[i]++;
        }
        System.out.printf("%-10s: %s%n", "Bucket", Arrays.toString(bucket));

        // 新建一个数组存储下标结束的值，用于保证排序稳定性
        int[] endIndex = new int[bucket.length];
        int sum = 0;
        for (int i = 0; i < endIndex.length; i++) {
            sum += bucket[i];
            endIndex[i] = sum;
        }
        System.out.printf("%-10s: %s%n", "endIndex", Arrays.toString(endIndex));

        // 遍历 bucket 数组，将统计结果塞到新建结果集中
        // 这一段实现踩了好多坑
        //  1. i 结束条件 >= 0，第一次实现没有把 = 纳入
        //  2. 后两句的 endIndex[arr[i]] 老是写成 endIndex[i]，对应关系还是没有写清楚
        int[] result = new int[arr.length];
        for (int i = arr.length - 1; i >= 0; i--) {
            result[endIndex[arr[i]] - 1] = arr[i];
            endIndex[arr[i]]--;
        }
        return result;
    }

    private static int getMax(int[] arr) {
        // 遍历数组，得到最大值
        int max = arr[0];
        for (int j : arr) {
            if (max < j) {
                max = j;
            }
        }
        return max;
    }
}

// Origin    : [4, 6, 8, 3, 8, 0, 0, 4, 3, 5]
// Bucket    : [2, 0, 0, 2, 2, 1, 1, 0, 2]
// endIndex  : [2, 2, 2, 4, 6, 7, 8, 8, 10]
// After     : [0, 0, 3, 3, 4, 4, 5, 6, 8, 8]

不是从 0 开始的实现

之前的实现还是有瑕疵，作为统计数组的下标都是从 0 开始的，在一开始统计最值的时候可以同时统计最小值，缩小样本空间，减少空间消耗

在之前的练习中理解了下标，值之间的对应关系，修改一下并不十分麻烦，挺好理解的。

有的示例中会把 bucket 和 endIndex 合并来减少内存开销，我觉得都 OK，这样写思路会清晰一点

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
public class CountingSort {
    public static void main(String[] args) {
        int[] arr = new Random().ints(0, 10).limit(10).toArray();
        System.out.printf("%-10s: %s%n", "Origin", Arrays.toString(arr));
        int[] result = countingSort(arr);
        System.out.printf("%-10s: %s%n", "After", Arrays.toString(result));
    }

    private static int[] countingSort(int[] arr) {
        // 遍历数组，得到最值
        int max = arr[0];
        int min = arr[0];
        for (int j : arr) {
            if (max < j) {
                max = j;
            }
            if (min > j) {
                min = j;
            }
        }

        // 根据最值新建一个用于计数的数组, 比如原数组最大值为 4，最小值为 2，新建的计数数组为 [2，3，4]，所以声明长度的时候为 max - min + 1
        int[] bucket = new int[max - min + 1];
        // 再次遍历数组，将对应的 bucket 下标做 ++ 操作
        for (int i : arr) {
            bucket[i - min]++;
        }
        System.out.printf("%-10s: %s%n", "Bucket", Arrays.toString(bucket));

        // 新建一个数组存储下标结束的值，用于保证排序稳定性
        int[] endIndex = new int[bucket.length];
        int sum = 0;
        for (int i = 0; i < endIndex.length; i++) {
            sum += bucket[i];
            endIndex[i] = sum;
        }
        System.out.printf("%-10s: %s%n", "endIndex", Arrays.toString(endIndex));

        // 遍历 bucket 数组，将统计结果塞到新建结果集中
        int[] result = new int[arr.length];
        for (int i = arr.length - 1; i >= 0; i--) {
            result[endIndex[arr[i] - min] - 1] = arr[i];
            endIndex[arr[i] - min]--;
        }
        return result;
    }
}
// Origin    : [5, 1, 7, 6, 1, 0, 5, 2, 0, 3]
// Bucket    : [2, 2, 1, 1, 0, 2, 1, 1]
// endIndex  : [2, 4, 5, 6, 6, 8, 9, 10]
// After     : [0, 0, 1, 1, 2, 3, 5, 5, 6, 7]

继续演进

既然都写到这里了，直接在源代码基础上，直接将 bucket 和 endIndex 合并了，so easy

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
public class CountingSort {
    public static void main(String[] args) {
        int[] arr = new Random().ints(0, 10).limit(10).toArray();
        System.out.printf("%-10s: %s%n", "Origin", Arrays.toString(arr));
        int[] result = countingSort(arr);
        System.out.printf("%-10s: %s%n", "After", Arrays.toString(result));
    }

    private static int[] countingSort(int[] arr) {
        // 遍历数组，得到最值
        int max = arr[0];
        int min = arr[0];
        for (int j : arr) {
            if (max < j) {
                max = j;
            }
            if (min > j) {
                min = j;
            }
        }

        // 根据最值新建一个用于计数的数组, 比如原数组最大值为 4，最小值为 2，新建的计数数组为 [2，3，4]，所以声明长度的时候为 max - min + 1
        int[] bucket = new int[max - min + 1];
        // 再次遍历数组，将对应的 bucket 下标做 ++ 操作
        for (int i : arr) {
            bucket[i - min]++;
        }
        System.out.printf("%-10s: %s%n", "Bucket", Arrays.toString(bucket));

        // 新建一个数组存储下标结束的值，用于保证排序稳定性
        for (int i = 1; i < bucket.length; i++) {
            bucket[i] = bucket[i] + bucket[i - 1];
        }
        System.out.printf("%-10s: %s%n", "Index", Arrays.toString(bucket));

        // 遍历 bucket 数组，将统计结果塞到新建结果集中
        int[] result = new int[arr.length];
        for (int i = arr.length - 1; i >= 0; i--) {
            result[bucket[arr[i] - min] - 1] = arr[i]; // 下标计算注意一下，arr[i] - min 取出 bucket 存储的位置值，但是这个值比下标大1
            bucket[arr[i] - min]--;
        }
        return result;
    }
}
// Origin    : [1, 4, 6, 3, 9, 5, 0, 0, 9, 8]
// Bucket    : [2, 1, 0, 1, 1, 1, 1, 0, 1, 2]
// Index     : [2, 3, 3, 4, 5, 6, 7, 7, 8, 10]
// After     : [0, 0, 1, 3, 4, 5, 6, 8, 9, 9]

发表于 更新于 分类于
本文字数： 632 阅读时长 ≈ 1 分钟

今天在看 sourcegraph 这个开源工具的时候，发现他有提供终端查询接口的，但是要配置参数到 .zprofile 中, 突然想问一句 .zshrc 和 .zprofile 有什么关系？

.zprofile is basically the same as .zlogin except that it’s sourced before .zshrc while .zlogin is sourced after .zshrc.
According to the zsh documentation, “.zprofile is meant as an alternative to .zlogin for ksh fans; the two are not intended to be used together, although this could certainly be done if desired.”

PS: Ksh 是很早就出现的一种 shell

由上面的描述我们可以直到，zsh 的 config file 生效顺序为 zprofile -> zsh -> zlogin

实验

1
2
3
4
5
# shell 的 config file 是可以直接执行 cmd 的，在 .zprofile 和 .zshrc 中分别加上 "echo hello from .zprofile"
# 和 "echo hello from .zshrc". 新起一个终端会加载这两个配置，观察输出结果，和之前的描述一致

hello from .zprofile
hello from .zshrc

发表于 更新于 分类于
本文字数： 175 阅读时长 ≈ 1 分钟

使用 HomeBrew 安装软件各种卡断，搜索了一下，在 gitee 上看到一个很赞的项目，对 HomeBrew 进行了本土优化，速度很快 - HomebrewCN

突然对这个国内的 gitee 倍生好感，而且稍微撇了一下他的 UI，感觉要比 github 好看诶，666

有兴趣可以看一下他是怎么实现加速的，难道是将所有 HomeBrew 的相关安装包都在 gitee 上做了备份吗？！

发表于 更新于 分类于
本文字数： 488 阅读时长 ≈ 1 分钟

使用 requests lib 访问 HTTPS 网站的时候，如果关闭了认证，虽然访问可以继续，但是会抛 Warning 信息。

1
2
3
4
requests.get(request_url, headers=headers, verify=False)

# /Users/jack/.pyenv/versions/3.7.3/lib/python3.7/site-packages/urllib3/connectionpool.py:851: InsecureRequestWarning: Unverified HTTPS request is being made. Adding certificate verification is strongly advised. See: https://urllib3.readthedocs.io/en/latest/advanced-usage.html#ssl-warnings
#   InsecureRequestWarning)

按照提示，去对应的网页查看关闭提示信息的办法

1
2
import urllib3
urllib3.disable_warnings()

可行！ (●°u°●)​ 」

发表于 更新于 分类于
本文字数： 2.4k 阅读时长 ≈ 2 分钟

今天在查找某个 bug 的 root cause 的时候，发现一个 Class.getEnclosingClass() 的调用。从来没有用个这玩意儿，做下笔记。

定义

人话就是：返回这个类的外部类。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * Returns the immediately enclosing class of the underlying
 * class.  If the underlying class is a top level class this
 * method returns {@code null}.
 * @return the immediately enclosing class of the underlying class
 * @exception  SecurityException
 *             If a security manager, <i>s</i>, is present and the caller's
 *             class loader is not the same as or an ancestor of the class
 *             loader for the enclosing class and invocation of {@link
 *             SecurityManager#checkPackageAccess s.checkPackageAccess()}
 *             denies access to the package of the enclosing class
 * @since 1.5
 */
@CallerSensitive
public Class<?> getEnclosingClass() throws SecurityException

案件重现

以前有一段 code 组织形式如下，定义了一个 MyOuterClass，它有一个 field 动态实现了 MyAbsClass 这个抽象类。那么，当我们调用 MyOuterClass 实例的 field.getClass().getEcloseingClass() 的时候会返回外部类的 class name

1
2
3
4
5
6
7
8
9
10
11
12
public class Test {
    public static void main(String[] args) {
        System.out.println((new MyOuterClass()).field.getClass().getEnclosingClass().getSimpleName());
    }
}

abstract class MyAbsClass {}

class MyOuterClass {
    MyAbsClass field = new MyAbsClass() {};
}
// MyOuterClass

然后有个德国的 team 将这段代码重构了，形式如下。他们新建了一个类，继承了抽象类，并将原先的类成员变量声明的地方用这个新建类代替了。这种情况下，getEnclosingClass() 的调用方就变为一个 top level class 了，返回 null，随之导致 getSimpleName() 抛出 NPE 了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Test {
    public static void main(String[] args) {
        System.out.println((new MyOuterClass()).field.getClass().getEnclosingClass().getSimpleName());
    }
}

abstract class MyAbsClass {}

class MyAbsClassIns extends MyAbsClass {}

class MyOuterClass {
    MyAbsClass field = new MyAbsClassIns();
}
// Exception in thread "main" java.lang.NullPointerException
//     at reading.container.Test.main(Test.java:5)

其他的使用测试

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
public class Test {
    public static void main(String[] args) {
        new Person();
    }
}

class Person {
    {
        System.out.println("log when init person: " + getClass().getEnclosingClass());
        new Outer();
    }

    class Outer {
        {
            System.out.println("log when init Outer: " + getClass().getEnclosingClass());
            new Inner();
        }

        class Inner {
            {
                System.out.println("log when init Inner: " + getClass().getEnclosingClass());
            }
        }
    }
}
// log when init person: null
// log when init Outer: class reading.container.Person
// log when init Inner: class reading.container.Person$Outer

发表于 更新于 分类于
本文字数： 1.8k 阅读时长 ≈ 2 分钟

堆排序是一种利用堆特性的选择排序，复杂度为 O(nlogn)

堆是一颗完全二叉树

堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了

将数组映射为二叉树结构，对应关系如下

1
2
3
4
5
6
7
8
9
10
@startuml
(50) --> (45)
(50) --> (40)
(45) --> (20)
(45) --> (25)
(40) --> (35)
(40) --> (30)
(20) --> (10)
(20) --> (15)
@enduml
# 0 1 2 3 4 5 6 7 8
arr 50 45 40 20 25 35 30 10 15

该数组从逻辑上讲就是一个堆结构，我们用简单的公式来描述一下堆的定义就是：

大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]

小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]

下标与节点位置关系：

  • 下标为 i 的节点父节点下标： (i-1)/2 整数除法
  • 下标为 i 的节点的左孩子下标：i*2 + 1
  • 下标为 i 的节点的右孩子下标：i*2 + 2
  • 最后一个非叶子节点位置：(数组长度/2) - 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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
public class HeapSort {
    public static void main(String[] args) {
        int[] arr = new int[]{ 50, 45, 40, 20, 25, 35, 30, 10, 15 };
        System.out.println("Origin: " + Arrays.toString(arr));
        heapSort(arr);
        System.out.println("After:  " + Arrays.toString(arr));
    }

    private static void heapSort(int[] arr) {
        // 构建大顶堆, 即从最后一个非叶子节点开始对之前的节点分别做大顶堆调整
        // i=0 时也需要计算，指的时 0 号位元素的排序
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            heapify(arr, arr.length, i); // 起始点是最后一个节点，有时候我会写成 0
        }

        // 已经是大顶堆了，先交换，在调整，一直重复 n-1 次
        for (int i = arr.length - 1; i > 0; i--) {
            swap(arr, 0, i);
            heapify(arr, i, 0);
        }

    }

    private static void heapify(int[] arr, int length, int pos) {
        int largest = pos;
        int lson = pos * 2 + 1;
        int rson = pos * 2 + 2;

        // lson < length, 不包含相等的情况，不然数组越界了
        if (lson < length && arr[largest] < arr[lson]) {
            largest = lson;
        }

        if (rson < length && arr[largest] < arr[rson]) {
            largest = rson;
        }

        if (largest != pos) {
            swap(arr, largest, pos);
            heapify(arr, length, largest);
        }
    }

    private static void swap(int[] arr, int pos1, int pos2) {
        int tmp = arr[pos1];
        arr[pos1] = arr[pos2];
        arr[pos2] = tmp;
    }
}

Refer

发表于 更新于 分类于
本文字数： 4.6k 阅读时长 ≈ 4 分钟

为什么要拷贝

因为方便，如果我有一个类有好多属性，固然可以用 new Object + set attribute 的方式达到拷贝的目的，但是麻烦。。。

如何拷贝

  1. 实现 Cloneable 接口，否则会抛 CloneNotSupportedException
  2. 重写 clone 方法，修改修饰符为 public
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
public class CloneTest {
    public static void main(String[] args) {
        Person person = new Person(1, "jack");
        System.out.println(person);
        Person clone = person.clone();
        System.out.println(clone);
    }
}

class Person implements Cloneable {
    int age;
    String name;

    // constructor + toString


    @Override
    public Person clone() {
        Person clone = null;
        try {
            clone = (Person)super.clone();
        } catch (CloneNotSupportedException e) {
            e.printStackTrace();
        }
        return clone;
    }
}

// Person{age=1, name='jack'}
// Person{age=1, name='jack'}

浅拷贝(shallow) Vs 深拷贝(deep)

浅拷贝

引用类型(接口，对象等复杂类型)的成员变量不会做拷贝，克隆对象会持有和原对象同一个引用

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**
* 修改 Person 类定义，新增一个引用类型的成员变量 Address
* 为原型 person 设置 Address 变量，并设置值为 shanghai
* clone 一个 person，然后修改 Address 值为 hangzhou
* 由于是浅拷贝，持有的 Address 引用是同一个，所以两个 Person 实例的 Address 都改变了
*/
public class CloneTest {
    public static void main(String[] args) throws CloneNotSupportedException {
        Person person = new Person(1, "jack");
        Address addr = new Address("shanghai");
        person.addr = addr;

        Person clone = person.clone();
        addr.addr = "hangzhou";

        System.out.println(person);
        System.out.println(clone);
    }
}

class Person implements Cloneable {
    int age;
    String name;
    Address addr;

    // constructor + toString

    @Override
    public Person clone() {
        Person clone = null;
        try {
            clone = (Person)super.clone();
        } catch (CloneNotSupportedException e) {
            e.printStackTrace();
        }
        return clone;
    }
}

class Address {
    String addr;

    // constructor + toString 
}

上面这种表现方式和我们想要的有很大的出入, 我们想要的是连这些 field 也一起拷贝，深拷贝由此而来

深拷贝

在浅拷贝的基础上，你还需要做如下事情

  1. 成员变量也需要实现 Cloneable 接口并重写 clone 方法
  2. 在原来 clone 方法后面，添加成员变量的 clone 调用并赋值
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
public class CloneTest {
    public static void main(String[] args) throws CloneNotSupportedException {
        Person person = new Person(1, "jack");
        Address addr = new Address("shanghai");
        person.addr = addr;

        Person clone = person.clone();
        addr.addr = "hangzhou";

        System.out.println(person);
        System.out.println(clone);
    }
}

class Person implements Cloneable {
    int age;
    String name;
    Address addr;

    // constructor + toString

    @Override
    public Person clone() {
        Person clone = null;
        try {
            clone = (Person)super.clone();
        } catch (CloneNotSupportedException e) {
            e.printStackTrace();
        }
        clone.addr = addr.clone(); // field 的 clone 调用和赋值
        return clone;
    }
}

class Address implements Cloneable {
    String addr;

    // constructor + toString

    @Override
    protected Address clone() {
        Address addr = null;
        try {
            addr = (Address) super.clone();
        } catch (CloneNotSupportedException e) {
            e.printStackTrace();
        }
        return addr;
    }
}

// Person{age=1, name='jack', addr=Address{addr='hangzhou'}}
// Person{age=1, name='jack', addr=Address{addr='shanghai'}}

解决多层 clone 问题

如果需要复制的对象包含很多成员变量，或者潜逃了很多层，那么重写 clone 也会变得相当麻烦，这个时候可以使用 Serializable 接口来简化序列化操作

这种实现不需要实现 Cloneable 接口，只需要相关的类实现 Serializable 接口即可，感觉就是代码看着会复杂一点，其他倒是没什么弊端

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
public class CloneTest {
    public static void main(String[] args) throws CloneNotSupportedException {
        Person person = new Person(1, "jack");
        Address addr = new Address("shanghai");
        person.addr = addr;

        Person clone = person.clone();
        addr.addr = "hangzhou";

        System.out.println(person);
        System.out.println(clone);
    }
}

class Person implements Serializable {
    private static final long serialVersionUID = -926205369611773951L;
    int age;
    String name;
    Address addr;

    // constructor + toString

    @Override
    public Person clone() {
        Person clone = null;
        try {
            // 将该对象序列化成流,因为写在流里的是对象的一个拷贝，而原对象仍然存在于JVM里面。所以利用这个特性可以实现对象的深拷贝
            ByteArrayOutputStream baos = new ByteArrayOutputStream();
            ObjectOutputStream oos = new ObjectOutputStream(baos);
            oos.writeObject(this);
            // 将流序列化成对象
            ByteArrayInputStream bais = new ByteArrayInputStream(baos.toByteArray());
            ObjectInputStream ois = new ObjectInputStream(bais);
            clone = (Person) ois.readObject();
        } catch (IOException | ClassNotFoundException e) {
            e.printStackTrace();
        }
        return clone;
    }
}

class Address implements Serializable {
    private static final long serialVersionUID = -1360519918551295988L;
    String addr;

    // constructor + toString
}
// Person{age=1, name='jack', addr=Address{addr='hangzhou'}}
// Person{age=1, name='jack', addr=Address{addr='shanghai'}}

发表于 更新于 分类于
本文字数： 1.5k 阅读时长 ≈ 1 分钟

希尔排序是快排的一个变种，是首个突破 O(n2) 的排序算法。但是为什么说他快，看了一些知乎上的解释，这是一种实现简单，但是证明很难的算法。要用到很多数学概念，这里就算了。

算法说明：

  1. 取一个固定的步长(通常为待排数组长度的一半), 将数组分组，进行插入排序。
    1. 这里的分组并不是对半分，举例如下：假设有数组 [0, 1, 2, 3, 4, 5, 6, 7] 取步长 4，则 0，4 为一组，1，5为一组依次类推
    2. 分组后的排序，因为只有两个数比较，我也看到有直接用比较之后交换的，不一定是插入排序
  2. 将固定步长取半重复之前的运算规则
  3. 直到排序完步长为 1 的情况，排序结束

时间复杂度：

平均和最好： O(nlongn)
最坏： O(n2)

实现

说实话，道理我都懂，但是在看 Java 版本的希尔排序实现的时候，我看是看了半天，加上搜索视频教程和本地 debug 才理解下来的，他别是在这个交替进行的点，奇数个元素分组规则上，卡了挺久的。

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 ShellSort {
    public static void main(String[] args) {
        int[] sample = new Random().ints(0, 100).limit(11).toArray();
        System.out.println("Origin: " + Arrays.toString(sample));
        shellSort(sample);
        System.out.println("After:  " + Arrays.toString(sample));
    }

    private static void shellSort(int[] sample) {
        // 步长操作
        // 边界条件为 step > 0, 当 step = 1 时，即对整个 arr 做一次插入排序
        for (int step = sample.length / 2; step > 0; step /= 2) {
            //分组进行插入排序，这里需要注意的是，这个插入排序是交替进行的，这里困惑了很久
            for (int i = step; i < sample.length; i++) {
                // 以步长为基本单位做插入排序
                int j = i - step;
                // j >= 0, 0 的时候也是合法的
                while (j >= 0 && sample[j] > sample[j + step]) {
                    // 典型的通过中间变量交换值的逻辑
                    int temp = sample[j + step];
                    sample[j + step] = sample[j];
                    sample[j] = temp;
                    j = j - step;
                }
            }
        }
    }
}

// Origin: [84, 32, 55, 3, 57, 68, 75, 71, 12, 43, 50]
// After:  [3, 12, 32, 43, 50, 55, 57, 68, 71, 75, 84]

细节分析

以 [84, 32, 55, 3, 57, 68, 75, 71, 12, 43, 50] 为例子分析

第一次分组，对半分，由于元素格式 11 个，步长 5，将整个数组分为了五组

num elements
1 84, 68, 50
2 32, 75
3 55, 71
4 3, 12
5 57, 43

我一开始以为代码实现的时候会先将 1 组中的各个元素抽出来，然后做一次插入排序，然后进行下第二组排序，一次类推。但实际上，在实现过程中，他会先将一组中第1，2 个元素用插入排序排完，然后直接跳到第二组，对1，2号元素排序，依次类推。等五个组的1，2 号元素都排完了，再回到第一组，对3号元素进行插入排序

发表于 更新于 分类于
本文字数： 6.6k 阅读时长 ≈ 6 分钟

Nosql 概述

单机数据库：

  1. 数据量如果太大，一个机器放不下
  2. 数据的索引，一个机器内存放不下
  3. 访问量，一个服务器承受不了

Memcached(缓存) + MySQL+ 垂直拆分

网站 80% 的情况都是在读数据，每次都查 DB 就十分慢，采用缓存保证效率

发展过程：优化数据结构和索引 -> 文件缓存(IO) -> Memcached

分库分表 + 水平拆分 + MySQL 集群

  • ISAM：早期，表锁，效率低
  • Innodb: 行所

如今，数据量大，变化快，MySQL 不太适用这种场景了

MySQL 也不适合存储比较大的文件，博客，图片。表大，效率低，需要专门的数据库

为什么用 NoSQL

用户信息爆发式增长，NoSQL 可以解决上面的问题

NoSQL = Not Only SQL

关系型数据库 = 表 + 行 + 列

泛指非关系型数据库，随着 web2.0 互联网的诞生，传统的关系型数据库很难对付，尤其是超大规模的高并发社区。

很多数据类型，比如个人信息，社交网络，地理位置不需要一个固定格式，不需要过多操作就能横向操作

特点

  1. 方便扩展
  2. 大数据量高性能 (redis 写 8w/s, 读 11w/s, NoSQL 的缓存记录级，是一种细粒度的缓存，性能会比较高)
  3. 数据类型是多样型的(不需要事先设计数据库)

RDBMS Vs NoSQL

RDBMS

  • 结构化组织(表/列)
  • SQL
  • 数据和关系都存在单独的表中
  • 数据操作语言，数据定义语言(DSL, DML)
  • 严格的一致性

NoSQL

  • 不仅仅是SQL
  • 没有固定的查询语言
  • 存储类型多样(键值，文档，列存储，图形数据-社交关系)
  • 最终一致性
  • CAP定理和BASE 异地多活
  • 高性能，高可用，高可扩

3v + 3高

3v: 主要描述问题

  1. 海量Volume
  2. 多样Variety
  3. 实时Velocity

3 高:

  1. 高并发
  2. 高可扩
  3. 高性能

真实情况：NoSQL + RDBMS

典型电商网站分析

  1. 商品基本信息，名称，价格，商家信息，存关系型数据库
  2. 商品描述，评论(文字较多) MongoDB
  3. 图片，分布式文件系统 FastDFS, 淘宝 TFS，Google GFS， Hadoop HDFD, 阿里云 OSS
  4. 商品关键字，搜索，solr, ES, ISearch
  5. 商品热门的波段信息，内存数据库，Redis, Tair, Memcache
  6. 商品交易 - 第三方接口

NoSQL 四大分类

KV键值对:

  • 新浪： Redis
  • 美团：Redis + Tair
  • 阿里，百度：Redis + memocache

文档型数据库(bson)

  • MongoDB(一般需要掌握)
    • MongoDB 是一个给予分布式文件存储的数据库，C++ 编写，主要用来处理大量文档
    • MongoDB 是一个介于关系型数据库和非关系型数据库的中间产品

列存储数据库：

  • HBase
  • 分布式文件系统

图关系数据库：

  • 社交网络
  • Neo4j

Redis 入门

Remote Dictionary Server: c，基于内存，可持久化， KV，多语言 API

能干嘛

  1. 内存存储，可持久化(RDB, AOF)
  2. 效率高，可高速缓存
  3. 发布订阅系统
  4. 地图信息分析
  5. 计数器 - 订阅量，计时器

安装

CentOS:

  1. 下载 redis 安装包 redis.xx.tar.gz
  2. 放到 /opt 下， tar -zxcf redis.xx.tar.gz, 加压后的文件包含配置文件 redis.conf
  3. cd 到加压文件下 yum install gcc-c++ 安装 gcc
  4. make 编译程序 + make install
  5. redis 默认安装路径 /usr/local/bin
  6. redis 配置文件 copy 到安装目录下 mkdir myconfig + cp /opt/redis-6.0.6/redis.conf .
  7. redis 默认不是后台启动，修改一下 daemonize yes
  8. redis-server myconfig/redis.config 运行

PS: 6.0.6 版本的 redis 自带配置文件了。。。

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
32
33
make install
cd src && make install
make[1]: Entering directory `/opt/redis-6.0.6/src'

Hint: It's a good idea to run 'make test' ;)

    INSTALL install
    INSTALL install
    INSTALL install
    INSTALL install
    INSTALL install
make[1]: Leaving directory `/opt/redis-6.0.6/src'

# 启动提示
redis-server redis.conf
9841:C 30 Apr 2021 22:15:30.703 # oO0OoO0OoO0Oo Redis is starting oO0OoO0OoO0Oo
9841:C 30 Apr 2021 22:15:30.703 # Redis version=6.0.6, bits=64, commit=00000000, modified=0, pid=9841, just started
9841:C 30 Apr 2021 22:15:30.703 # Configuration loaded

redis-cli -p 6379   # 客户端链接测试
127.0.0.1:6379> ping
PONG
127.0.0.1:6379> set name jack
OK
127.0.0.1:6379> get name
"jack"
127.0.0.1:6379> keys *
1) "name"
127.0.0.1:6379> shutdown    # 推出
not connected> exit
[root@iZuf6jaqcwqwkqvydc5mscZ bin]# ps -ef | grep redis
root      9850  5506  0 22:19 pts/0    00:00:00 grep --color=auto redis

PS: centos 默认的 gcc 版本是 4.8.5 在编译 redis 时会报错，需要升级到 5.3 以上才行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
gcv -v # 查看版本

make distclean # 清除编译生成的文件

yum -y install centos-release-scl   # 安装新版本 gcc
yum -y install devtoolset-9-gcc devtoolset-9-gcc-c++ devtoolset-9-binutils

# 需要注意的是scl命令启用只是临时的，退出shell或重新打开一个shell就会恢复原系统gcc版本
scl enable devtoolset-9 bash
gcc -v

#执行以下命令永久使用
echo "source /opt/rh/devtoolset-9/enable" >> /etc/profile
# 注：执行完此命令后，其它的shell窗口需要关闭重新打开才生效。
# 重新打开shell窗口，再次编译

性能测试

自带的性能测试工具 redis-benchmark

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 测试 100 个并发，每个并发 100 000 个请求
redis-benchmark -h localhost -p 6379 -c 100 -n 100000


# ====== SET ======
#   100000 requests completed in 1.44 seconds         # 100 000 个请求 1.44 秒完成
#   100 parallel clients                              # 100 个并发 
#   3 bytes payload
#   keep alive: 1
#   host configuration "save": 900 1 300 10 60 10000
#   host configuration "appendonly": no
#   multi-thread: no

# 49.47% <= 1 milliseconds
# 99.96% <= 2 milliseconds
# 100.00% <= 2 milliseconds
# 69492.70 requests per second

基础知识

redis 默认有 16 个数据库(redis.conf - databases 16), 默认用第一个，可以通过 select n 修改

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
127.0.0.1:6379> dbsize  # 查看大小
(integer) 5
127.0.0.1:6379> select 3 # 换数据库
OK
127.0.0.1:6379[3]> dbsize
(integer) 0
127.0.0.1:6379> keys *    # 查看已有的 key
1) "mylist:{tag}"
2) "key:{tag}:__rand_int__"
3) "myhash:{tag}:__rand_int__"
4) "counter:{tag}:__rand_int__"
5) "name"
127.0.0.1:6379> flushdb   # 清空数据库
OK
127.0.0.1:6379> keys *
(empty array)
127.0.0.1:6379[1]> flushall # 清空所有数据库
OK

PS: 八卦，为什么端口时 6379 - 作者追星

Redis 时单线程的！

Redis 基于内存操作， CPU 不是瓶颈，瓶颈在内存和带宽

Redis 为 C 语言开发， 10w+ QPS, 完全不比 Memecache 差

Redis 为什么单线程还这么快？

  1. 误区：高性能的服务器一定是多线程？
  2. 误区：多线程一定比单线程效率高

核心：redis 是将所有数据全部存放在内存中的，省去了上下文切换的时间

Redis-key

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
127.0.0.1:6379> exists name # 判断是否存在
(integer) 1
127.0.0.1:6379> move name 1 # 移除 key
(integer) 1
127.0.0.1:6379> set name jack
OK
127.0.0.1:6379> expire name 10  # 设置过期时间, 单位s
(integer) 1
127.0.0.1:6379> ttl name      # 查看 key 剩余时间
(integer) 7
127.0.0.1:6379> ttl name
(integer) 2
127.0.0.1:6379> ttl name
(integer) -2
127.0.0.1:6379> get name
(nil)
127.0.0.1:6379> ttl name
(integer) -2
127.0.0.1:6379> type name   # 查看类型
string
127.0.0.1:6379> set key v1
OK
127.0.0.1:6379> append key "hello"  # 追加，如果不存在则新加
(integer) 7
127.0.0.1:6379> get key
"v1hello"
127.0.0.1:6379> strlen key  # 给出字符串长度
(integer) 7
127.0.0.1:6379> append key "world"
(integer) 12
127.0.0.1:6379> set views 0
OK
127.0.0.1:6379> incr views  # +1 操作
(integer) 1
127.0.0.1:6379> get views
"1"
127.0.0.1:6379> decr views # -1 操作
(integer) 0
127.0.0.1:6379> decr views
(integer) -1
127.0.0.1:6379> incrby views 10 # +10
(integer) 9
127.0.0.1:6379> decrby views 4 # -4
(integer) 5

### 字符串操作
127.0.0.1:6379> set key "hello,jack"
OK
127.0.0.1:6379> getrange key 0 3  # sub string 
"hell"
127.0.0.1:6379> getrange key 0 -1 # 取全部字符串
"hello,jack"

### 替换
127.0.0.1:6379> set key2 asdfghj
OK
127.0.0.1:6379> setrange key2 1 xx  # 从第 n 位开始替换
(integer) 7
127.0.0.1:6379> get key2
"axxfghj"

###
# setex - set with expire 
# setnx - set if not exist

127.0.0.1:6379> setex key3 30 hello # 添加并设置过期时间
OK
127.0.0.1:6379> ttl key3
(integer) 27
127.0.0.1:6379> setnx key4 redis    # 如果不存在就添加，否则失败
(integer) 1
127.0.0.1:6379> keys *
1) "key"
2) "key4"
3) "key2"
4) "key3"
127.0.0.1:6379> setnx key4 redis2
(integer) 0
127.0.0.1:6379> get key4
"redis"
127.0.0.1:6379> keys *
1) "key"
2) "key4"
3) "key2"


## 批量操作
127.0.0.1:6379> mset k1 v1 k2 v2 k3 v3
OK
127.0.0.1:6379> keys *
1) "k3"
2) "k1"
3) "k2"
127.0.0.1:6379> mget k1 k2 k3
1) "v1"
2) "v2"
3) "v3"
127.0.0.1:6379> msetnx k1 v1 k4 v4  # 由于是原子操作，所以 k4 没有加成功
(integer) 0
127.0.0.1:6379> keys *
1) "k3"
2) "k1"
3) "k2"

## 对象转化
# 需要保存一个 user: {id:1, name:zhangsan, age:2} 对象时，可以这么做
# user:{id}:{field}
127.0.0.1:6379> mset user:1:name zhangsan user:1:age 2
OK
127.0.0.1:6379> mget user:1:name user:1:age
1) "zhangsan"
2) "2"

## getset 先 get 再 set
127.0.0.1:6379> getset db redis # 如果不存在 返回 nil
(nil)
127.0.0.1:6379> get db
"redis"
127.0.0.1:6379> getset db mongodb # 如果存在，获取并更新
"redis"
127.0.0.1:6379> get db
"mongodb"

发表于 更新于 分类于
本文字数： 3.2k 阅读时长 ≈ 3 分钟

走进 Linux 系统

开机会启动很多程序，Windows 叫服务(service)，Linux 叫守护进程(daemon)

关机

linux 中没有报错，即成功

1
2
3
4
5
sync            # 同步数据

shutdown -h now # 马上关机

reboot          # 重启

目录结构

  1. 一切皆文件
  2. 根目录 /，所有文件都挂载在这个节点下
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
ls
# bin  boot  dev  etc  home  lib  lib64  media  mnt  opt  proc  root  run  sbin  srv  sys  tmp  usr  var
# bin: binary, 存放经常使用的命令
# boot: 启动 Linux 时使用的一些核心文件，包括连接文件和镜像文件
# dev: device, 存放外部设备，Linux 中访问设备和访问文件是一样的
# *etc: 存放所有系统管理所需的配置文件和子目录
# home: 用户主目录，每个用户有一个自己的目录，以自己命名
# lib: 系统最基本的动态连接共享库，类似于 Windows 的 dll 文件
# mnt: 系统提供目录为用户临时挂载文件系统，如光驱等
# lost+found: 一般为空，当系统非正常关机时，这里就会存放一些文件
# media: 媒体设备，U盘，光驱等
# *opt: 额外安装的软件所摆放的位置，比如安装一个数据库什么的，默认为空
# proc: 虚拟目录，系统映射，不管
# *root: 管理员目录
# sbin: s for super user, 村系统管理员使用的管理程序
# srv: 存放一些服务启动后需要提取的数据
# sys: linux2.6之后一个很大的变化，2.6后该目录下新出现一个文件系统 sysfs
# tmp: 临时文件，用完就丢
# *usr: 非常重要的目录，用户很多应用程序和文件都放在这个目录下，类似 Windows 的 program files 目录
# usr/bin: 系统用户使用的应用程序
# usr/sbin: 超级用户使用的应用程序
# usr/src: 内核源代码默认放置位置
# var: 放不断扩充的东西，比如日志
# run: 临时文件系统，存储系统启动以来的信息。重启时，这个目录下的文件应该被删除或清空
# www: 存放服务器网站相关资源，环境，网站目录

常用基本命令

1
2
3
mkdir -p f1/f2/f3   # 递归创建文件夹
rmdir -p f1         # 递归删除
rmdir f1            # 如果有子文件，删除会失败

内容查看

1
2
3
4
5
6
cat # 顺序
tac # 倒叙
nl  # 带行号

less 比 more 好，功能多，向下查询 /，向上查询 ？
tail -n 20 # 最后20行

链接

硬链接：A…B, 假设 B 是 A 的硬连接，那么他们指向同一个文件，允许一个文件多个路径，用这种机制可以放置误删
软连接：类似 Windows 下的快捷方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
touch f1

echo "hello" > f1

ln f1 f2 # 创建硬链接

ln -s f1 f3 # 创建软链接

rm f1

cat f2      # f1, f2 硬连接，删除还存在
# hello

cat f3      # f1, f3 软链接，删除即不见
# cat: f3: No such file or directory

账户管理

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
useradd -m jack002 # 创建 user 并在 home 下创建对应的文件夹
# root@945e2e63f891:/home# ls
# f2  f3  jack  jack002
# Linux 一切皆文件，添加用户其实就是往某一个文件中写入用户信息 /etc/passwd

userdel -r jack002 # 删除 user 并清空文件夹

usermod -d /home/233 jack002 # 修改用户目录, 233 并不存在，但是对应的信息还是设置到 passwd 中去了，所以修改前必须先手动创建文件夹
# root@945e2e63f891:/home# cat /etc/passwd
# jack002:x:1001:1001::/home/233:/bin/sh
# root@945e2e63f891:/home# ls
# f2  f3  jack  jack002

root@945e2e63f891:/home#
# root: 当前用户
# 945e2e63f891: 主机名
# /home: 当前路径
# '#' 超级用户

su username # 切换用户
# $: 提示符也会跟着改

exit # 退出用户切换

hostname # 查看主机名
hostname xxx # 修改主机名，需要重联生效

passwd username # 修改密码

passwd -l username # 锁用户
passwd -d username # 用户密码清空，也不能登陆

用户组管理

本质是对 /etc/group 进行修改

1
2
3
4
5
6
7
8
9
10
11
12
13
# -g        # 指定 gid, 不指定就自增
groupadd jackgroup
# root@945e2e63f891:/# cat /etc/group
# jackgroup:x:1002:
# jack520:x:520:

groupdel jackgroup # 删除 group

# -n    # 修改 id
# -G    # 设置用户组
groupmod -g 555 -n jack555 jack520

newgroup root # 切换组

拓展

/etc/passwd

1
2
jack002:x:1001:1001::/home/jack002:/bin/sh
用户名：密码（不可见，所以是x）：用户标识号（自增）：组标识号：注释性描述：主目录：登陆 shell

密码放在 /etc/shadow 加密过的 jack002:$6$/me.SpanXkOPad04$XO/jFHniPIenQQXFZhSOfwL7eQ0hQ..X5EWNigGrfh8sqZ6KA8wAFQtzCPpwgf.Ov9RIVp8hr9GcXB3un4Oax1:18746:0:99999:7:::

磁盘管理

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
32
df # 列出整体磁盘使用量
# root@945e2e63f891:/# df -h
# Filesystem      Size  Used Avail Use% Mounted on
# overlay          59G   21G   35G  38% /
# tmpfs            64M     0   64M   0% /dev
# tmpfs           7.9G     0  7.9G   0% /sys/fs/cgroup
# shm              64M     0   64M   0% /dev/shm
# /dev/vda1        59G   21G   35G  38% /etc/hosts
# tmpfs           7.9G     0  7.9G   0% /proc/acpi
# tmpfs           7.9G     0  7.9G   0% /sys/firmware
du # 当前磁盘使用量
# root@945e2e63f891:/home# du -a
# 4       ./jack002/.bashrc
# 4       ./jack002/.profile
# 4       ./jack002/.bash_logout
# 16      ./jack002
# 4       ./f2
# 4       ./jack/f1/f2/f3
# 8       ./jack/f1/f2
# 12      ./jack/f1
# 16      ./jack
# 0       ./f3
# 40      .

du -sm /*       # 系统根目录下每个文件夹占用空间
# 5       /bin
# 1       /boot
# 0       /dev

mount /dev/jack /mnt/jack # 将外部设备 jack 挂载到 mnt 下，实现访问

umount -f /mnt/jakc # 强制卸载

进程管理

  1. 每个进程都有父进程
  2. 两种运行方式：前台，后台
  3. 服务基本都是后台运行，程序都是前台运行
  4. 每个进程都有一个 id 号
1
2
3
4
5
6
7
8
9
10
11
12
# -a 当前终端运行的所有进程信息
# -u 一用户的信息显示进程
# -x 显示后台运行进程的参数
ps # 查看当前正在运行的进程信息
# ps -aux       
# ps -ef 可以查看父进程

# -p 显示父 id
# -u 显示组信息
pstree -pu # 进程树

kill -9 pid # 结束进程