发表于

本文基于JDK 1.8.0_211撰写，基于java.util.Arrays.sort()方法浅谈目前Java所用到的排序算法，仅个人见解和笔记，若有问题欢迎指证，着重介绍其中的TimSort排序，其源于Python，并于JDK1.7引入Java以替代原有的归并排序。

引入

Arrays.Sort方法所用的排序算法主要涉及以下三种：双轴快速排序（DualPivotQuicksort）、归并排序（MergeSort)、TimSort，也同时包含了一些非基于比较的排序算法：例如计数排序。其具体最终使用哪一种排序算法通常根据类型以及输入长度来动态抉择。

  • 输入数组类型为基础类型时，采用双轴快速排序，辅以计数排序；
1
2
3
java复制代码public static void sort(int[] a) {
    DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}
  • 输入数组类型为包装类型时，采用归并排序或TimSort（除非经过特殊的配置，否则默认采用TimSort）
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
java复制代码public static void sort(Object[] a) {
    if (LegacyMergeSort.userRequested)
      legacyMergeSort(a);
  else
    ComparableTimSort.sort(a, 0, a.length, null, 0, 0);
}
 
public static <T> void sort(T[] a, Comparator<? super T> c) {
    if (c == null) {
        sort(a);
  } else {
        if (LegacyMergeSort.userRequested)
            legacyMergeSort(a, c);
    else
       TimSort.sort(a, 0, a.length, c, null, 0, 0);
    }
}
 
/** To be removed in a future release. */
 private static <T> void legacyMergeSort(T[] a, Comparator<? super T> c) {
  T[] aux = a.clone();
  if (c==null)
      mergeSort(aux, a, 0, a.length, 0);
  else
    mergeSort(aux, a, 0, a.length, 0, c);
  }

排序稳定性

假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i] = r[j]，且 r[i] 在 r[j] 之前，而在排序后的序列中，r[i] 仍在 r[j] 之前，则称这种排序算法是稳定的；否则称为不稳定的。

稳定性的含义：如果我们需要在二次排序后保持原有排序的意义，就需要使用到稳定性的算法

例子：我们要对一组商品排序，商品存在两个属性：价格和销量。当我们按照价格从高到低排序后，要再按照销量对其排序，这时，如果要保证销量相同的商品仍保持价格从高到低的顺序，就必须使用稳定性算法。

快速排序与双轴快速排序

快速排序简介

单轴快速排序 即为我们最常见的一种快速排序方式，我们选取一个基准值（pivot），将待排序数组划分为两部分：大于pivot 和 小于pivot，再对这两部分进行单轴快速排序… 但是这种方式对于输入数组中有很多重复元素时效率不太理想。

单轴三取样切分快速排序 作为单轴快速排序的优化版本，其主要优化相同元素过多情况下的快排效率，同样选取一个基准值，但将待排序数组划分三部分： 大于pivot、等于pivot、大于pivot。

双轴快速排序选取两个 基准值pivot1，pivot2，且保证pivot1<=pivot2，其具体实现与三取样切分类似，不过时将待排序数组划分以下三部分：小于pivot，介于pivot1与pivot2之间，大于pivot2。

DualPivotQuicksort实现优化

Java在实现DualPivotQuickSort时，并未盲目使用双轴快速排序，而是基于输入长度选取排序算法。

（1）针对int、long、float、double四种类型，跟据长度选取的排序算法如下：

  • 当待排序数目小于47，采用插入排序
  • 当待排序数目小于286，采用双轴快排
  • 当待排序数目大于286，采用归并排序

我们暂且将其称之为一个标准的双轴快排

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
java复制代码static void sort(int[] a, int left, int right,
                     int[] work, int workBase, int workLen) {
        // Use Quicksort on small arrays
        if (right - left < QUICKSORT_THRESHOLD) {
            sort(a, left, right, true);
            return;
        }
        // Use MergingSort
       doMerge();
 }

private static void sort(int[] a, int left, int right, boolean leftmost) {
      // Use insertion sort on tiny arrays
      if (length < INSERTION_SORT_THRESHOLD) {
            doInertionSort();
      }
      doDualPivotQuickSort();
}

（2）针对short、char两种类型，根据长度选取的排序算法如下：

  • 当待排序数目小于3200，采用标准**双轴快排**；
  • 当待排序数目大于3200，采用计数排序（**CountingSort）**

（3）针对byte类型，根据长度选取的排序算法如下：

  • 当待排序数目小于29，采用插入排序；
  • 当待排序数目大于29，采用计数排序（**CountingSort）**

非基于比较排序算法-计数排序

计数排序与传统的基于比较的排序算法不同，其不通过比较来排序。我们常见的非基于比较的排序算法有三种：桶排序、计数排序（特殊桶排序）、基数排序，有兴趣的可以逐个去了解，这里主要讲解计数排序。

使用前提

使用计数排序待排序内容需要是一个有界的序列，且可用整数表示

引入

计数排序顾名思义即需要统计数组中的元素个数，通过另外一个数组的地址表示输入元素的值，数组的值表示元素个数。最后再将这个数组反向输出即可完成排序，见下方示例：

假设：一组范围在 0~10 之间的数字，9, 3, 5, 4, 9, 1, 2, 7, 8,1,3, 6, 5, 3, 4, 0, 10, 9, 7, 9

第一步：建立一个数组来统计每个元素出现的个数，因为是0~10，则建立如下数组 Count：

第二步：遍历输入数组，将获取到的内容放置到Count 数组对应的位置，使当前位置+1，例如当前为9：

以此类推，遍历完整个输入数组，则得到一个完整状态的Count：

这时候，Count中记录了输入数组所有的元素出现的次数，将Count数组按次数输出即可得到最终排序输出：

0, 1, 1, 2, 3, 3, 3, 4, 4, 5, 5, 6, 7, 7, 8, 9, 9, 9, 9, 10

计数排序的稳定性与最终实现

根据上面稳定性的定义，大家不难发现上面的实现过程不能保证基数排序的稳定性，而实际上计数排序是一个稳定的排序算法，下面我们通过上面那个例子来引出计数排序的最终实现。

例子：输入数组 [ 0，9，5，4，5 ]，范围0 ~ 9

第一步：将Count数组中所记录的内容进行更改，由记录当前元素的出现的次数 修正为 记录当前索引出现的次数和当前索引之前所有元素次数的和，这样在索引中存储的值就是其真实的排序后排位数，例如9的值为5，则9的排序后的位置就是第5位：

第二步：我们从后向前遍历原序列，此时为5，则在最终排序序列的位置为4（索引为3）的地方放置5，并将Count序列的5索引处的值-1。

以此类推：到第二个5时，Count数组中的值为3（索引为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
java复制代码/** The number of distinct byte values. */
private static final int NUM_BYTE_VALUES = 1 << 8;

static void sort(byte[] a, int left, int right) {
    int[] count = new int[NUM_BYTE_VALUES];
    
    // 建立count数组
    for (int i = left - 1; ++i <= right;
        count[a[i] - Byte.MIN_VALUE]++
    );

    // 从尾部开始遍历
    for (int i = NUM_BYTE_VALUES, k = right + 1; k > left; ) {

        while (count[--i] == 0);
        byte value = (byte) (i + Byte.MIN_VALUE);
        
        int s = count[i];

        do {
            a[--k] = value;
         } while (--s > 0);
     }        
}

TimSort

Timsort是工业级算法，其混用插入排序与归并排序，二分搜索等算法，亮点是充分利用待排序数据可能部分有序的事实，并且依据待排序数据内容动态改变排序策略——选择性进行归并以及galloping。另外TimSort是一个稳定的算法，其最好的执行情况要优于普通归并排序，最坏情况与归并排序相仿：

针对小数据优化

针对输入长度较短的数组排序，很多轻量级排序即可胜任，故TimSort在基于输入数组长度的条件下，做出如下优化：

当输入序列的长度小于基准值时，将采用插入排序直接对输入序列排序。基准值的选取：（1）Python：64（2）Java：32

此外上面提到的插入排序，Java的实现中，对这部分做了优化，严格来说这里使用的是二分插入排序。将插入排序与二分查找进行了结合。因为插入排序的索引左侧均是有序序列：

  • 传统意义上需要单个依次向前比较，直到找到新插入元素放置的位置；
  • 二分插入排序，则在此处采用二分查找来确认插入元素的放置位置。

TimSort简要流程

TimSort is a hybrid sorting algorithm that uses insertion sort and merge sort.

The algorithm reorders the input array from left to right by finding consecutive (disjoint) sorted segments (called “runs” from hereon). If the run is too short, it is extended using insertion sort. The lengths of the generated runs are added to an array named runLen. Whenever a new run is added to runLen, a method named mergeCollapse merges runs until the last 3 elements in runLen satisfy the following two conditions (the “invariant”):

  1. runLen[n-2] > runLen[n-1] + runLen[n]
  2. runLen[n-1] > runLen [n]

Here n is the index of the last run in runLen. The intention is that checking this invariant on the top 3 runs in runLen in fact guarantees that all runs satisfy it. At the very end, all runs are merged, yielding a sorted version of the input array.

TimSort算法通过找到连续的（不相交）排序的段（此后称为“Run”），如果Run过短，则使用插入排序扩充。生成的Run的长度被称添加到一个名为runLen数组中，每当将新Run添加到runLen时，名为mergeCollapse的方法就会尝试合并Run，直到runLen中的元素元素满足两个恒定的不等式。到最后，所有Run都将合并成一个Run，从而生成输入数组的排序版本。

基本概念 - Run

TimSort算法中，将有序子序列（升序序列和严格降序序列）称之为Run，例如如下将排序序列：1,2,3,4,5,4,3,6,8,10

则上面的序列所有的Run如下：1,2,3,4,5,5,3,2,2,6,8,10

TimSort中会区分其序列为升序还是降序，如果是降序会强行反转**Run**，使其成为升序，则上述的序列经过反转后即为：1,2,3,4,5,5,2,3,2,6,8,10

*注意：Run必须是升序（可以相等）和严格降序（不能相等），严格降序的原因是保证TimSort稳定性，因为降序需要反转。*

基本概念 - MinRun

当两个数组归并时，当这个数组Run的数目等于或略小于2的乘方时，效率最高（基本数学概念参考：listsort.txt）。

反过来说，我们需要得到一个Run**的最小长度，使得其划分的Run的数目达到上述标准准，即：选取32-64（16-32）这个范围作为MinRun的范围，使得原排序数组可以被MinRun分割成N份，这个N等于或略小于2**的乘方。

  • 如果当前的Run长度小于MinRun：尝试把后面的元素通过插入排序放入Run中，以尽量达到MinRun的长度（剩余长度满足的情况下）；
  • 如果当前的Run长度大于MinRun：不处理。

通过上述的操作我们就收获了一系列Run，将其放置到堆栈runLen中，并尝试对其进行归并：

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
java复制代码/**
     * A stack of pending runs yet to be merged. Run i starts at
     * address base[i] and extends for len[i] elements. It's always
     * true (so long as the indices are in bounds) that:
     *
     * runBase[i] + runLen[i] == runBase[i + 1]
     *
     * so we could cut the storage for this, but it's a minor amount,
     * and keeping all the info explicit simplifies the code.
     */
    private int stackSize = 0; // Number of pending runs on stack
    private final int[] runBase;
    private final int[] runLen;

     /*
      * 初始化部分截取
      * 分配runs-to-be-merged堆栈(不能扩大)
      */
    int stackLen = (len < 120 ? 5 : len < 1542 ? 10 : len < 119151 ? 24 : 49);
    runBase = new int[stackLen];
    runLen = new int[stackLen];

    /**
      * Pushes the specified run onto the pending-run stack.
      *
      * @param runBase index of the first element in the run
      * @param runLen  the number of elements in the run
      */
    private void pushRun(int runBase, int runLen) {
        this.runBase[stackSize] = runBase;
         this.runLen[stackSize] = runLen;
         stackSize++;
    }

归并原则 - 不等式

基于如下原因：

（1）堆栈runLen内存占用尽量减小，则其是线上具有固定大小，不考虑扩容（参考上述源码的注释）；

（2）让归并的两个Run的数目都尽量接近，更接近普通归并的模式，提高归并效率。

TimSort在runLen上制定了两个不等式以使runLen尽量贴近上面的条件：

  • Run[n-1] > Run[n] + Run[n+1]
  • Run[n] > Run[n+1]

当目前runLen满足这两个不等式时，则不进行归并，否则进行归并，因为TimSort时稳定的排序算法，则仅允许归并相邻的两个Run：

  • 如果不满足不等式一：归并Run[n]与Run[n-1]、Run[n+1]中长度较短的Run
  • 如果不满足不等式二：归并Run[n]与Run[n+1]

不变式的含义：

不变式一：从右至左读取长度，则待处理的runLen的增长至少与斐波那契额增长的速度一样快，则更使得两个归并的Run的大小更为接近；

不变式二：待处理的runLen按递减顺序排序。

通过以上两个推论可以推测runLen中的Run数目永远会收敛于一个确定的数，以此证明了只用极小的runLen堆栈就可以排序很长的输入数组，也正是因为如此在实现上不考虑扩容问题，如果需要详细数学例证可以查看文后Reference。

实际代码是线上，Java、Python、Android保证不等式的手段是检查栈顶三个元素是否满足，即上述不等式的n取栈顶第二个，如果不满足则归并，归并完成后再继续检查栈顶三个直到满足为止。

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
java复制代码/**
     * Examines the stack of runs waiting to be merged and merges adjacent runs
     * until the stack invariants are reestablished:
     *
     *     1. runLen[i - 3] > runLen[i - 2] + runLen[i - 1]
     *     2. runLen[i - 2] > runLen[i - 1]
     *
     * This method is called each time a new run is pushed onto the stack,
     * so the invariants are guaranteed to hold for i < stackSize upon
     * entry to the method.
     */
    private void mergeCollapse() {
        while (stackSize > 1) {
            int n = stackSize - 2;
            if (n > 0 && runLen[n-1] <= runLen[n] + runLen[n+1]) {
                if (runLen[n - 1] < runLen[n + 1])
                    n--;
                mergeAt(n);
            } else if (runLen[n] <= runLen[n + 1]) {
                mergeAt(n);
            } else {
                break; // Invariant is established
            }
        }
    }

归并排序

归并优化一：内存优化

由于需要保证TimSort的稳定性，则归并排序不能采用原地排序，TimSort引入了临时数组来进行归并，并将参与归并的两个Run中较小的那个放置到临时数组中，以节省内存占用。同时区分从小开始归并和从大开始归并。

归并优化二：缩短归并Run长度

两个参与归并的Run，由很多部分其实时不用参与归并的（从Run的某个位置开始的前面或后面的元素均小于或大于另一个Run的全部元素，则这部分就可以不参与归并），加之归并两个Run是在原输入数组中是相邻，则我们考虑是否可以在去掉部分头尾元素，以达到缩短归并长度的目的：

（1）在RunA查找一个位置 I 可以正好放置RunB[0]，则 I 之前的数据都不用参与归并，在原地不需要变化；

（2）在RunB查找一个位置 J 可以正好放置RunA[Len-1]，则 J 之后的数据都不用参与归并，在原地不需要变化；

归并排序优化三：GallopingMode

在归并时有可能存在以下的极端情况：

RunA 的所有元素都小于RunB，如果这个情况下采用常规的归并效率肯定不理想

于是TimSort引入了GallopingMode，用来解决上述的问题，即当归并时，一个Run连续n的元素都小于另一个Run，则考虑是否有更多的元素都小于，则跳出正常归并，进入GallopingMode，当不满足Galloping条件时，再跳回到正常归并（不满足Galloping条件时强制使用Galloping效率低下）。如果RunA的许多元素都小于RunB，那么有可能RunA会继续拥有小于RunB的值（反之亦然），这个时候TimSort会跳出常规的归并排序进入Galloping Mode，这里规定了一个阈值**MIN_GALLOP，默认值为7**。

下面模拟一次Galloping，以mergeHi为例（从大开始归并）：

（1）例如此时RunA已经连续赢得7次归并，而RunB的元素还没有一次被选取，则已经达到阈值，进入GallopingMode：

进入GallopingMode，说明此时已经有RunA已经小于RunB末尾的7个数字，TimSort猜测会有更多的RunA的数字小于RunB，则进行以下操作：

以上则完成了一次Galloping，在这一次Galloping中，我们一次性将所有大于RunB[len-1]的RunA元素一次性移动（包括RunB[len-1]，放置到这次移动的RunA元素后），不需要再依次归并。

这时涉及到一个概念即是否继续执行Galloping，还是回到正常的归并？

我们判断这一次移动的元素个数是否还满足阈值（黄色），如果满足则继续，在RunA中寻找RunB[len-2]的位置，否则回到正常的归并。

Java版本实现中每次进入和退出Galloping会变更这个进入GallopingMode的阈值，应该是某种奖惩机制，这里不做说明。

TimSort 的实现缺陷

在Java8中TimSort的实现是有缺陷的，在极端复杂情况下可能会触发异常，其主要原因是如果只检查栈顶三个Run的不等式关系，没办法办证这个不等式在整个runLen堆栈上成立，参考以下示例：

不等式被破坏的代价，即为Run的归并时机被破坏，导致在某些极端情况下，会导致堆栈中的Run超过我们通过不等式推出来的那个收敛值导致溢出：ArrayOutOfBoundsException，这个Bug在后续版本已经修复：

提供的修复方案即为检查栈顶四个Run而非三个：

1
2
3
4
5
6
7
8
9
10
11
12
13
java复制代码private void newMergeCollapse() {
     while (stackSize > 1) {
       int n = stackSize - 2;
       if (   (n >= 1 && runLen[n-1] <= runLen[n] + runLen[n+1])
           || (n >= 2 && runLen[n-2] <= runLen[n] + runLen[n-1])) {
                if (runLen[n - 1] < runLen[n + 1])
                    n--;
            } else if (runLen[n] > runLen[n + 1]) {
                break; // Invariant is established
            }
            mergeAt(n);
        }
    }

有兴趣手动Debug这个问题的读者可以参考如下Git操作：github.com/Rekent/java…

部分源码注释

贴出这部分只是方便读者在看完概念后对源码的时候有一个对应，方便后续再看细节
入口方法：

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
java复制代码static <T> void sort(T[] a, int lo, int hi, Comparator<? super T> c, T[] work, int workBase, int workLen) {
        assert c != null && a != null && lo >= 0 && lo <= hi && hi <= a.length;

        int nRemaining = hi - lo;
        if (nRemaining < 2) {
            return; // Arrays of size 0 and 1 are always sorted
        }

        // 如果小于32位，则不采用TimSort，而是采用二分插入排序对整个数组直接排序
        if (nRemaining < MIN_MERGE) {
            // 获取第一个序列（Run）
            int initRunLen = countRunAndMakeAscending(a, lo, hi, c);
            // 二分插入排序（从第一个Run后开始向前排序，第一个Run已经是增序了，不用再排）
            binarySort(a, lo, hi, lo + initRunLen, c);
            return;
        }

        MyTimSort<T> ts = new MyTimSort<>(a, c, work, workBase, workLen);
        // 根据当前排序数组长度生成最小的Run长度
        int minRun = minRunLength(nRemaining);
        do {
            // 识别下一个Run序列，返回这个Run的长度
            int runLen = countRunAndMakeAscending(a, lo, hi, c);

            // 如果当前的Run序列长度小于MinRun长度，则尝试扩展到MinRun的长度（从后面选取元素进行二分拆入排序）
            if (runLen < minRun) {
                // 如果剩余长度小于当前的MinRun，则补全为剩余的长度
                int force = nRemaining <= minRun ? nRemaining : minRun;
                binarySort(a, lo, lo + force, lo + runLen, c);
                runLen = force;
            }

            // 记录当前Run的起始Index以及Run长度
            ts.pushRun(lo, runLen);
            // 尝试合并
            ts.mergeCollapse();

            // 开始下一轮的Run寻找
            lo += runLen;
            nRemaining -= runLen;
        } while (nRemaining != 0);

        // 所有的Run都已经寻找完毕，必须合并所有Run
        assert lo == hi;
        ts.mergeForceCollapse();
        assert ts.stackSize == 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
50
51
52
53
54
java复制代码/**
     * 合并i以及i+1两个Run. Run i 一定是倒数第二个或者倒数第三个Run
     *
     * @param i 合并堆栈的索引
     */
    private void mergeAt(int i) {
        // i 一定是倒数第二个或者倒数第三个，换句话说，i一定是stackSize-2或者stackSize-3
        assert stackSize >= 2;
        assert i >= 0;
        assert i == stackSize - 2 || i == stackSize - 3;

        int base1 = runBase[i];
        int len1 = runLen[i];
        int base2 = runBase[i + 1];
        int len2 = runLen[i + 1];
        assert len1 > 0 && len2 > 0;
        assert base1 + len1 == base2;

        // 将i的长度更新len1+len2，即合并后的长度，如果是倒数第三个Run，则将倒数第一个长度合并到倒数第二个Run中（倒数第二个和倒数第三个Run合并了）
        // [RUN1,RUN2,RUN3] -> [RUN1+RUN2,RUN3] ; [RUN1,RUN2] -> [RUN1+RUN2]
        runLen[i] = len1 + len2;
        if (i == stackSize - 3) {
            runBase[i + 1] = runBase[i + 2];
            runLen[i + 1] = runLen[i + 2];
        }
        stackSize--;

        // 缩短归并长度：在Run1中寻找Run2的起始节点位置（Run2的首个元素应该放置Run1中的位置），可以忽略run1中先前的元素（因为其已经有序）
        int k = gallopRight(a[base2], a, base1, len1, 0, c);
        assert k >= 0;
        // ！！！ Run1 这个位置之前的可以省略不再排序，因为Run2所有元素都大于这个位置
        base1 += k;
        len1 -= k;
        // 如果剩余排序长度为0，则已经有序，不用再排序（Run1全体大于Run2）
        if (len1 == 0) {
            return;
        }

        // 缩短归并长度：在Run2中寻找Run1的最后一个元素应该放置的位置，！！！ Run2的这个位置后面可以省略不再排序，因为后面所有元素都大于Run1
        len2 = gallopLeft(a[base1 + len1 - 1], a, base2, len2, len2 - 1, c);
        assert len2 >= 0;
        // 如果剩余排序长度为0，则已经有序，不用再排序（Run2全体大于Run1）
        if (len2 == 0) {
            return;
        }

        // 并归两侧，选取较短的一方作为临时数组长度
        // mergeLo：将len1 放入临时数组，mergeHi：将len2 放入临时数组
        if (len1 <= len2) {
            mergeLo(base1, len1, base2, len2);
        } else {
            mergeHi(base1, len1, base2, len2);
        }
    }

底层归并以及Galloping：

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
123
124
java复制代码/**
     * 类似于mergeLo，除了这个方法应该只在len1 >= len2;如果len1 <= len2，则应该调用mergeLo。
     * (两个方法都可以在len1 == len2时调用。)
     *
     * @param base1 Run1的队首元素
     * @param len1  Run1的长度
     * @param base2 Run2的队首元素(？？？must be aBase + aLen)
     * @param len2  Run2的长度
     */
    private void mergeHi(int base1, int len1, int base2, int len2) {
        assert len1 > 0 && len2 > 0 && base1 + len1 == base2;

        T[] a = this.a; // For performance
        T[] tmp = ensureCapacity(len2);
        int tmpBase = this.tmpBase;
        System.arraycopy(a, base2, tmp, tmpBase, len2);

        int cursor1 = base1 + len1 - 1; 
        int cursor2 = tmpBase + len2 - 1; 
        int dest = base2 + len2 - 1; 

        // Move last element of first run and deal with degenerate cases
        a[dest--] = a[cursor1--];
        if (--len1 == 0) {
            System.arraycopy(tmp, tmpBase, a, dest - (len2 - 1), len2);
            return;
        }
        // 简化操作，如果Run2要合并的元素只有一个，这个元素不比Run1的最大值大，也不比当前Run1索引的最小值大（base1的位置是大于Run2队首元素的位置），故Run2这个元素应该放置到Run1第一个
        if (len2 == 1) {
            dest -= len1; // dest = dest - len1 (因前序dest已经-1，故是Run1队尾坐标)，dest:Run1应该开始合并的起始位置:[....{1},6,16,0,27]
            cursor1 -= len1; // cursor1 = cursor1 - len1 (因前序cursor1已经-1,故是Run1倒数第二坐标)，cursor1:dest的前序位置:[...{X},1,6,16,0,27]
            System.arraycopy(a, cursor1 + 1, a, dest + 1, len1); // [...{1,6,16},0,27] -> [...1,{1,6,16},27]，将Run要排序部分后移一位
            a[dest] = tmp[cursor2]; // [....1,1,6,16,27] -> [...0,1,6,16,27]，将tmp中的唯一元素放置到队首
            return;
        }

        Comparator<? super T> c = this.c; // Use local variable for performance
        int minGallop = this.minGallop; // " " " " "
        outer: while (true) {
            // 开始正常归并，并记录Run1、Run2 赢得选择的次数，如果大于minGallop则跳出进入GallopingMode
            int count1 = 0; // Number of times in a row that first run won
            int count2 = 0; // Number of times in a row that second run won

            /*
             * Do the straightforward thing until (if ever) one run
             * appears to win consistently.
             */
            do {
                assert len1 > 0 && len2 > 1;
                if (c.compare(tmp[cursor2], a[cursor1]) < 0) {
                    a[dest--] = a[cursor1--];
                    count1++;
                    count2 = 0;
                    if (--len1 == 0) {
                        break outer;
                    }
                } else {
                    a[dest--] = tmp[cursor2--];
                    count2++;
                    count1 = 0;
                    if (--len2 == 1) {
                        break outer;
                    }
                }
            } while ((count1 | count2) < minGallop);

            /*
             * 一方已经连续合并超过minGallop次，则进入GallopingMode
             */
            do {
                assert len1 > 0 && len2 > 1;
                count1 = len1 - gallopRight(tmp[cursor2], a, base1, len1, len1 - 1, c);
                if (count1 != 0) {
                    dest -= count1;
                    cursor1 -= count1;
                    len1 -= count1;
                    System.arraycopy(a, cursor1 + 1, a, dest + 1, count1);
                    if (len1 == 0) {
                        break outer;
                    }
                }
                a[dest--] = tmp[cursor2--];
                if (--len2 == 1) {
                    break outer;
                }

                count2 = len2 - gallopLeft(a[cursor1], tmp, tmpBase, len2, len2 - 1, c);
                if (count2 != 0) {
                    dest -= count2;
                    cursor2 -= count2;
                    len2 -= count2;
                    System.arraycopy(tmp, cursor2 + 1, a, dest + 1, count2);
                    if (len2 <= 1) {
                        break outer;
                    }
                }
                a[dest--] = a[cursor1--];
                if (--len1 == 0) {
                    break outer;
                }
                // 完成一次Galloping后对阈值做修改，并判断是否需要继续Galloping
                minGallop--;
            } while (count1 >= MIN_GALLOP | count2 >= MIN_GALLOP);
            if (minGallop < 0) {
                minGallop = 0;
            }
            minGallop += 2; // Penalize for leaving gallop mode
        } // End of "outer" loop
        this.minGallop = minGallop < 1 ? 1 : minGallop; // Write back to field

        if (len2 == 1) {
            assert len1 > 0;
            dest -= len1;
            cursor1 -= len1;
            System.arraycopy(a, cursor1 + 1, a, dest + 1, len1);
            a[dest] = tmp[cursor2]; // Move first elt of run2 to front of merge
        } else if (len2 == 0) {
            throw new IllegalArgumentException("Comparison method violates its general contract!");
        } else {
            assert len1 == 0;
            assert len2 > 0;
            System.arraycopy(tmp, tmpBase, a, dest - (len2 - 1), len2);
        }
    }

Reference

www.envisage-project.eu/proving-and…

svn.python.org/projects/py…

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

本文出自“淘系技术公众号”，为本人发表的文章

背景

在电商平台的架构体系中，商品数据是系统正常运转的基石，随着平台的发展，商品数据很容易突破亿级。在电商运营方面，平台通常需要举行各种大促，使用各种营销工具吸引消费者，因此需要对商品进行招商、选品、投放。

在大促招商后，平台会根据活动报名记录数据进行一系列的运营，活动报名记录通常根据某些维度进行了聚合，比如卖家聚合维度、活动聚合维度。对某一聚合维度的商品报名数据进行处理之前，首先需要获取这一聚合维度下面的所有数据。

如果数据量比较小，数据可以采用单库单表存储，获取某一聚合维度下面的所有数据也是比较简单的事情。但是，报名记录数据量通常非常大，需要采用分库分表存储数据，由于数据分散存储，获取分库分表数据将变得困难，特别是需要获取指定某一聚合维度的所有数据。比如，某个大促下面所有的报名记录有几千万条，因此不能使用单表存储，需要分库分表存储，这样就是导致获取某个大促的所有报名记录变得困难。

本文讲解方法的就是，如何高性能分布式地获取按维度聚合的分库分表数据。本文用大促报名记录模型来说明本文的方法，对于其他类似的模型也可以适用。

相关数据模型介绍

目前主流的数据存储方案还是MySql，虽然使用MySql存储大数量级数据需要进行复杂的水平拆分和垂直拆分，但是，MySql拥有优异的性能、灵活的索引方式等，这非常有利于复杂的业务需求。本文讨论基于Mysql数据库，存储引擎为Innodb，分库分表采用TDDL。为了更好的讲述本文的方法，接下来简单定义几个相关的数据模型，这些数据模型是大促技术体系中的一个缩影，能代表大多数业务的数据模型。

基础商品模型

基础商品模型描述的商品的基础属性，其他数据模型通过商品ID关联基础商品数据模型，基础商品模型通过卖家ID关联卖家模型，基础商品数据模型如下所示。基础商品数据量通常非常大，需要进行分库分表存储。对于基础商品表，通常查询方式会指定商品ID获取商品的基础信息，并且不会对该表有过多的查询方式，因此基础商品表通常使用商品ID作为分表键，即满足查询需求，又能够把数据均匀分布在所有分表中。

1
2
3
4
5
6
7
8
sql复制代码id                  bigint unsigned      主键ID
gmt_create          datetime             创建时间
gmt_modified        datetime             修改时间
item_id             bigint unsigned      商品ID
seller_id           bigint unsigned      商家ID
name                varchar              商品标题
price               bigint unsigned      商品价格
picture_url         varchar              商品图片url

活动数据模型

活动数据模型描述了一个活动的基础属性，活动数据模型如下所示。其中activity_id表示活动ID，major_id表示大促ID，一个大促下面存在多个活动，即一个大促ID可以关联多个活动ID，这种一对多的关系表示了它们之间的聚合关系，活动按照大促聚合维度进行了聚合。活动数据量通常不会非常大，因此通常采用单库单表存储。

1
2
3
4
5
6
7
8
sql复制代码id                  bigint unsigned      主键ID
gmt_create          datetime             创建时间
gmt_modified        datetime             修改时间
activity_id         bigint unsigned      活动ID
major_id            bigint unsigned      大促ID
name                varchar              活动名称
start_time          datetime             活动开始时间
end_time            datetime             活动结束时间

报名记录数据模型

报名记录数据模型描述了商品报名某个活动的报名信息，报名记录数据模型如下所示。一个商品可以报名多个活动，一个活动的报名记录可以由很多商家的商品报名组成。通过上面的数据模型，可以发现活动报名记录按照多种聚合维度进行了聚合，比如，卖家聚合维度、活动聚合维度、大促聚合维度。业务上需要对不同聚合维度的所有数据进行处理，因此就需要有一种方法能够高性能地获取某一聚合维度下的所有数据。

1
2
3
4
5
6
7
8
9
arduino复制代码id                  bigint unsigned      主键ID
gmt_create          datetime             创建时间
gmt_modified        datetime             修改时间
activity_id         bigint unsigned      活动ID
item_id             bigint unsigned      商品ID
seller_id           bigint unsigned      卖家ID
activity_price      bigint unsigned      商品活动价格
aount               bigint unsigned      优惠商品件数
buyer_limit         bigint unsigned      买家限购件数

其他相关方法描述

在进入本文主题之前，先描述下我了解到的解决该问题的相关方法。一些相关的方法通常采用商品ID作为活动报名记录表的分表键，这样数据可以比较均匀地分布到所有的分表中。对某一聚合维度的数据进行分布式获取时可以采用以下三种方案。

全表扫描方法

该方法思想很简单，只需对所有分表进行扫描，对每个分表进行处理时，可以采用索引提升获取数据的性能。这种方式实现简单，但是无法充分发挥分布式架构的性能，整体性能较低。

横向分片方法

  1. 根据聚合维度信息遍历所有分表得到每个分表的最大主键ID和最小主键ID，下图中min1表示分表1的最小主键ID、max1表示分表1的最大主键ID；
  2. 预估数据总量，数据总量等于每个分表中max-min相加的总和，如下图中count的计算公式；
  3. 根据预估数据总量count和固定每页大小划分成多个小任务进行分布式处理，下图中假设每页间隔大小为10，任务划如下图所示；
  4. 对每个小任务进行处理，每个小任务中包含主键范围，根据主键范围依次与每个表的最小主键和最大主键进行对比，判断该任务主键范围落在哪个表中，最后根据主键范围及其他条件获取数据。

缺点

  1. 对于数据分布稀疏的聚合维度，该方法会导致预估数据总量偏大很多，分批任务数量非常大，实际获取的数据可能很少，获取数据效率低；
  2. 该方案需要频繁重复的查询每个表中的最小和最大主键，获取数据的性能不高，容易造成数据库连接池满问题；
  3. 该方案分片处理方式实现复杂、不易于理解。

纵向分片方法

  1. 根据聚合维度信息遍历所有分表得到每个分表的最大主键ID和最小主键ID，下图中min1表示分表1的最小主键ID、max1表示分表1的最大主键ID；
  2. 预估数据总量，数据总量等于所有分表中的最大主键减最小主键，如下图中count的计算公式；
  3. 根据预估数据总量count和固定每页大小划分成多个小任务进行分布式处理，下图中假设每页间隔大小为10，任务划如下图所示；
  4. 对每个小任务进行处理，每个小任务中包含主键范围，遍历所有分表判断任务主键范围是否落在最小主键和最大主键之间，从符合条件的表中根据主键范围及其他条件获取数据。

缺点

  1. 对于数据分布密集的聚合维度，该方法会导致预估数据总量偏小很多，分片任务数量较少，每个任务包含大量数据，导致获取数据性能不高；
  2. 同样，该方案需要频繁重复的查询每个表中的最小和最大主键，获取数据的性能不高，容易造成数据库连接池满问题；
  3. 该方案分片处理方式实现复杂、不易于理解。

聚合维度降维方法

有了以上准备知识，本节开始讨论本文的方法。本文提出的方法采用聚合维度降维的思想，找到一条合适的降维路径将高聚合维度降低到低聚合维度，然后对最低聚合维度对数据进行分片处理。降维和分片的作用就是将大任务拆分成小任务，然后将小任务通过消息中间件进行分布式处理。

分库分表的设计

分片键的选择

分库分表的设计与业务相关性比较大，本文讨论一种比较常见的场景，适用于大多数的业务。分片键的选择直接影响数据分布、获取方式、获取的性能。分片键的选择有两大因素需要考虑，一个是数据获取方式，另一个是数据分布。数据获取方式需要根据具体的业务进行判断，比如，商品详情展示会根据商品ID查询基础商品表，圈品操作会根据活动ID或者卖家ID获取所有相关的商品。另外，数据需要比较均匀地分布到所有的分表中，这样才能保证不会因为数据倾斜导致获取数据时的性能问题。

基础商品表的分片键的选择有商品ID或者卖家ID。对于基础商品表，通常查询方式会指定商品ID获取商品的基础信息，并且不会对该表有过多的查询方式。因此，基础商品表采用商品ID作为分片键比较合适，根据商品ID对分表总数取模可以得到分表的位置。采用商品ID作为分片键可以比较均匀地将数据分布在所有表中。

报名记录表的分片键的选择有活动ID、商品ID、卖家ID。首先，可以排除活动ID作为分片键的选择，因为根据活动ID进行分库分表显然会导致数据倾斜严重。如果选择商品ID作为分表键，数据可以比较均匀分布到所有表中，但是根据聚合维度查询所有报名记录数据会出现性能问题，因为同一聚合维度的数据会分散到所有表中，获取数据时需要对所有表进行遍历，并且比较困难进行分布式处理。如果选择卖家ID作为分表键，同一个卖家的数据会聚合到同一个分表中，这样有利于对同一个卖家的数据进行获取，获取数据的效率也会非常高，但是在数据分布方面，个别超级卖家会拥有几十万以上的商品，特别是天猫超市卖家拥有超过2千万的商品，这些超级卖家都是电商平台自营的。

自定义分表键

从上面的分析可以知道，报名记录表采用商品ID或卖家ID作为分表键都不是非常合适的选择。如果同一聚合维度的数据分散到很多表中会导致获取性能不高，如果同一聚合维度的数据过度聚合到同一分表中会导致数据倾斜，同样也会导致获取性能不高。

本文介绍的方法，其中一个核心思想就是寻找一个合适的聚合维度将这个维度的数据聚合在同一分表中，既不会导致数据倾斜，有能够提高获取数据的性能。通过上面的分析可以知道卖家维度是比较合适的维度，但是，超级卖家会导致数据倾斜。因此，本文选择在卖家维度的基础上进行改进，采用自定义维度作为分表键，即在报名记录数据模型中增加一列sharding_key作为分表键。

对于普通卖家，自定义分表键sharding_key等于卖家ID。对于超级卖家，预先设置好该超级卖家存储的虚拟分表，比如，一个超级卖家所有的数据均匀分布到0-15号虚拟分表中，在业务逻辑层根据商品ID作为虚拟分表键对虚拟分表总数取模得到虚拟分表的序号，自定义分表键shardingKey就等于“#{卖家ID}_#{虚拟分表序号}”。流程图如下：
yuque_diagram.jpg

分布式获取的设计

某一聚合维度的报名记录数据总数可能超过亿级，如此庞大的数据总量如何高性能的获取，采用分布式方案是非常合适的。因此，需要将包含亿级数据的大任务拆分成小任务，然后将小任务分发给集群中所有的机器执行，本文采用消息中间件进行分发任务。

聚合维度的定义

数据之间具有一定的关联关系，多个数据可以与同一个标识相关联，而这多个数据就是根据同一个标识进行了聚合，我们把这个标识定义为一个聚合维度。

比如，一个卖家聚合维度相关的商品数据都属于同一个卖家，一个活动聚合维度相关的报名记录数据都报名了这一个活动，一个大促聚合维度相关的商品数据都参与了这个大促下面的某一个活动，一个自定义分表键聚合维度相关的报名记录数据都与这一自定义分表键相关。

最低聚合维度的定义

根据某一聚合维度可以直接在数据库具体某张表中获取到该聚合维度相关的所有数据，我们称这个聚合维度为最低聚合维度。因此，报名记录表中自定义分表键聚合维度属于最低聚合维度，因为根据一个自定义分表键聚合的报名记录数据都存储在同一个物理分表中，根据自定义分表键可以定位到具体的物理表。

聚合维度的降维

聚合维度之间也具有一定的关系，高聚合维度可以由低聚合维度组成。比如，在报名记录相关的数据模型中，一个大促聚合维度由多个活动聚合维度组成，一个活动聚合维度由多个卖家聚合维度组成，一个卖家聚合维度由一个或者多个自定义分片键聚合维度组成。从上面的关系可以得知，高聚合维度可以不断降维直到最低聚合维度，其实也就是，一个高聚合维度的大任务可以通过降维方式分解成许多最低聚合维度的小任务。一个大促聚合维度的降维过程如下所示：

如何实现高性能的降维也是比较关键的点，影响降维性能的核心应该是获取聚合维度组成部分的过程。大促ID与活动ID的关系存在活动表中，活动表是单库单表，因此只需要建立大促ID+活动ID的组合索引，查询大促ID相关的所有活动ID时就可以通过覆盖索引的方式获取，覆盖索引方式的查询性能很高。活动与报名卖家的关系存储在报名记录表中，报名记录表是根据自定义分片键作为分片键的分库分表，同样在报名记录表中建立活动ID+卖家ID的组合索引，查询活动ID关联的所有卖家ID时需要遍历所有物理表利用覆盖索引的方式获取，虽然需要遍历所有物理表，但是可以通过多线程处理，且使用覆盖索引查询方式的性能很高，因此获取活动相关卖家ID性能同样很高。而卖家ID与自定义分表键之间的关系属于配置关系，获取卖家相关的自定义分表键属于内存计算，性能非常高。

最低聚合维度的数据分片

得到最低聚合维度之后，我们可以直接获取到商品ID，但是，由于一个最低聚合维度相关的商品数据也有很多，为了提升商品数据获取性能，我们需要继续对数据进行分片，将一个小任务拆分成更多的小任务，充分利用集群分布式处理的能力。总体的数据分片思路如下所示：
yuque_diagram (2).jpg

最大最小主键ID获取

获取最大和最小主键ID的最简单方式是通过max和min函数，但最好不要使用这种方式，因为这种方式会因为访问数据行数过多导致性能问题。在上面讲述聚合维度的降维中提到需要建立活动ID+卖家ID的组合索引，其实可以将该索引改进一下，变成活动ID+卖家ID+自定义分表键的组合索引。这样便可以通过覆盖索引查询最大最小主键ID，性能更高，其中查询最大主键ID的SQL如下所示。

1
2
sql复制代码SELECT id FROM table WHERE activity_id = #{activityId} AND seller_id = #{sellerId} 
AND sharding_key = #{shardingKey} ORDER BY id DESC LIMIT 1

数据分片与获取

最低聚合维度相关的所有报名记录数据都在同一个物理表中，但这并不代表最低聚合维度相关的所有报名记录按主键ID连续分布在同一个物理表中，实际情况往往是数据非连续分散在物理表中，且有时分散范围很大。通过求主键ID的最大和最小值可以预估数据总量为最大值-最小值。如果按照预估数据总量和固定任务大小方式进行划分任务，当数据分布非常分散时，将产生大量的任务，实际其中大部分任务不包含任何报名记录数据。

固定任务大小方式划分任务
假设某最低聚合维度总共包含200条数据，最小主键ID（minId）=1000、最大主键ID（maxId）=10000000，预估数据总量为maxId-minId=9999000，每个任务固定分配500大小的数据，即需要划分9999000/500=19998个任务，第一任务的主键ID范围为[1000,1500)，最后一个任务的主键ID范围为[9999500,10000000]。

因此我们需要使用一种合理的算法对数据进行分片和获取，避免因为任务划分过多而导致性能下降，避免因为单个任务包含过多的数据而导致处理性能下降。

首先，我们采用动态任务大小方式进行数据分片，任务的大小会根据预估数据总量、集群机器总数、数据分布稀疏系数、初始任务大小按照一定的算法计算出来。算法计算流程如下：
yuque_diagram (3).jpg

然后，在数据获取方面，由于无法根据任务的主键ID范围判断任务实际包含的数据总数，为了避免一次性获取大量数据导致慢sql，我们需要采用主键ID作为游标的方式分批获取数据，流程图如下：
yuque_diagram (4).jpg

效果

使用本方案的产品在实际应用场景中，根据聚合维度获取数据的速度能够达到50000 QPS，在忽略业务处理耗时的情况下，该方案获取数据的速度可以达到更高。后续会在“在线数据圈选引擎”中继续进行压测验证。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

SpringBoot实战电商项目mall（40k+star）地址：github.com/macrozheng/…

摘要

记得之前使用Minikube安装K8S的时候，给分3G内存都嫌小！最近发现一个K8S的经量级实现K3S，最低0.5G内存就能运行起来，安装方便，和K8S用起来区别不大。推荐给大家，希望更多没高端机器的朋友也能够把K8S玩起来！

K3S简介

K3S是一个完全符合Kubernetes的发行版。可以使用单一二进制包安装（不到 100MB），安装简单，内存只有一半，最低0.5G内存就能运行。

为什么叫K3S？开发者希望K3S在内存占用方面只有K8S的一半，Kubernetes是一个10个字母的单词，简写为K8S。那么一半大小就是5个字母的单词，简写为K3S。

安装

使用官方提供的脚本安装十分方便，一个命令即可完成安装！

  • 使用脚本安装K3S，同时会安装其他实用程序，包括kubectl、crictl、ctr、k3s-killall.sh和k3s-uninstall.sh；
1
bash复制代码curl -sfL http://rancher-mirror.cnrancher.com/k3s/k3s-install.sh | INSTALL_K3S_MIRROR=cn sh -
  • 安装完成后提示如下信息，并且会将K3S注册为Linux中的服务；
1
2
3
4
5
6
7
8
9
10
bash复制代码Complete!
[INFO]  Creating /usr/local/bin/kubectl symlink to k3s
[INFO]  Creating /usr/local/bin/crictl symlink to k3s
[INFO]  Skipping /usr/local/bin/ctr symlink to k3s, command exists in PATH at /usr/bin/ctr
[INFO]  Creating killall script /usr/local/bin/k3s-killall.sh
[INFO]  Creating uninstall script /usr/local/bin/k3s-uninstall.sh
[INFO]  env: Creating environment file /etc/systemd/system/k3s.service.env
[INFO]  systemd: Creating service file /etc/systemd/system/k3s.service
[INFO]  systemd: Enabling k3s unit
[INFO]  systemd: Starting k3s
  • 可以查看下服务的运行状态，此时显示状态为active。
1
2
3
4
5
6
7
8
9
10
bash复制代码[root@linux-local k3s]# systemctl status k3s
● k3s.service - Lightweight Kubernetes
   Loaded: loaded (/etc/systemd/system/k3s.service; enabled; vendor preset: disabled)
   Active: active (running) since Thu 2021-01-28 10:18:39 CST; 2min 0s ago
     Docs: https://k3s.io
  Process: 14983 ExecStartPre=/sbin/modprobe overlay (code=exited, status=0/SUCCESS)
  Process: 14981 ExecStartPre=/sbin/modprobe br_netfilter (code=exited, status=0/SUCCESS)
 Main PID: 14986 (k3s-server)
    Tasks: 71
   Memory: 776.3M

使用

我们使用kubectl命令操作K3S与之前操作Minikube中的K8S并没有什么区别，这次还是创建一个Nginx的Deployment，然后通过创建Service将其暴露到外部访问。

创建集群

  • 由于K3S默认安装了kubectl工具，我们可以直接使用它，比如查看kubectl的版本号；
1
bash复制代码kubectl version
1
2
bash复制代码Client Version: version.Info{Major:"1", Minor:"20", GitVersion:"v1.20.2+k3s1", GitCommit:"1d4adb0301b9a63ceec8cabb11b309e061f43d5f", GitTreeState:"clean", BuildDate:"2021-01-14T23:52:37Z", GoVersion:"go1.15.5", Compiler:"gc", Platform:"linux/amd64"}
Server Version: version.Info{Major:"1", Minor:"20", GitVersion:"v1.20.2+k3s1", GitCommit:"1d4adb0301b9a63ceec8cabb11b309e061f43d5f", GitTreeState:"clean", BuildDate:"2021-01-14T23:52:37Z", GoVersion:"go1.15.5", Compiler:"gc", Platform:"linux/amd64"}
  • 还可以查看集群详细信息；
1
bash复制代码kubectl cluster-info
1
2
3
bash复制代码Kubernetes control plane is running at https://127.0.0.1:6443
CoreDNS is running at https://127.0.0.1:6443/api/v1/namespaces/kube-system/services/kube-dns:dns/proxy
Metrics-server is running at https://127.0.0.1:6443/api/v1/namespaces/kube-system/services/https:metrics-server:/proxy
  • 查看集群中的所有Node，可以发现K3S和之前的Minikube一样创建了一个单节点的简单集群。
1
bash复制代码kubectl get nodes
1
2
bash复制代码NAME          STATUS   ROLES                  AGE   VERSION
linux-local   Ready    control-plane,master   11m   v1.20.2+k3s1

部署应用

  • 指定好应用镜像并创建一个Deployment，这里创建一个Nginx应用；
1
bash复制代码kubectl create deployment nginx-deployment --image=nginx:1.10
  • 查看所有Deployment；
1
bash复制代码kubectl get deployments
1
2
bash复制代码NAME               READY   UP-TO-DATE   AVAILABLE   AGE
nginx-deployment   1/1     1            1           6s

查看应用

  • 查看Pod的详细状态，包括IP地址、占用端口、使用镜像等信息；
1
bash复制代码kubectl describe pods
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
bash复制代码Name:         nginx-deployment-597c48c9dd-j49bc
Namespace:    default
Priority:     0
Node:         linux-local/192.168.5.15
Start Time:   Thu, 28 Jan 2021 10:53:14 +0800
Labels:       app=nginx-deployment
              pod-template-hash=597c48c9dd
Annotations:  <none>
Status:       Running
IP:           10.42.0.7
IPs:
  IP:           10.42.0.7
Controlled By:  ReplicaSet/nginx-deployment-597c48c9dd
Containers:
  nginx:
    Container ID:   containerd://560bbeefc9c5714b92ae9d0a1305c2b8746082f4aa11791a2b6e1f4288254ef0
    Image:          nginx:1.10
    Image ID:       docker.io/library/nginx@sha256:6202beb06ea61f44179e02ca965e8e13b961d12640101fca213efbfd145d7575
    Port:           <none>
    Host Port:      <none>
    State:          Running
      Started:      Thu, 28 Jan 2021 10:53:16 +0800
    Ready:          True
    Restart Count:  0
    Environment:    <none>
    Mounts:
      /var/run/secrets/kubernetes.io/serviceaccount from default-token-fnrf7 (ro)
Conditions:
  Type              Status
  Initialized       True 
  Ready             True 
  ContainersReady   True 
  PodScheduled      True 
Volumes:
  default-token-fnrf7:
    Type:        Secret (a volume populated by a Secret)
    SecretName:  default-token-fnrf7
    Optional:    false
QoS Class:       BestEffort
Node-Selectors:  <none>
Tolerations:     node.kubernetes.io/not-ready:NoExecute op=Exists for 300s
                 node.kubernetes.io/unreachable:NoExecute op=Exists for 300s
Events:
  Type    Reason     Age   From               Message
  ----    ------     ----  ----               -------
  Normal  Scheduled  38s   default-scheduler  Successfully assigned default/nginx-deployment-597c48c9dd-j49bc to linux-local
  Normal  Pulled     38s   kubelet            Container image "nginx:1.10" already present on machine
  Normal  Created    38s   kubelet            Created container nginx
  Normal  Started    37s   kubelet            Started container nginx
  • 进入容器内部并执行bash命令，如果想退出容器可以使用exit命令。
1
bash复制代码kubectl exec -it nginx-deployment-597c48c9dd-j49bc -- bash

外部访问应用

  • 创建一个Service来暴露nginx-deployment这个Deployment：
1
bash复制代码kubectl expose deployment/nginx-deployment --name="nginx-service" --type="NodePort" --port=80
  • 查看所有Service的状态；
1
bash复制代码kubectl get services
1
2
3
bash复制代码NAME            TYPE        CLUSTER-IP    EXTERNAL-IP   PORT(S)        AGE
kubernetes      ClusterIP   10.43.0.1     <none>        443/TCP        77m
nginx-service   NodePort    10.43.29.39   <none>        80:31494/TCP   10s
  • 在Linux服务器上通过CURL命令即可访问Nginx服务，此时将打印Nginx主页信息；
1
bash复制代码curl localhost:31494
  • 相比Minikube在虚拟机中安装容器化应用，K3S直接在本机上安装，直接打开防火墙端口即可在外部访问；
1
2
3
4
bash复制代码# 开启端口
firewall-cmd --zone=public --add-port=31494/tcp --permanent
# 重启防火墙
firewall-cmd --reload

总结

K3S确实是一个很好用的K8S发行版本，不仅安装方便，而且内存占用也降低了。由于直接在本机上安装容器化应用，外部访问也方便了！

本文 GitHub github.com/macrozheng/… 已经收录，欢迎大家Star！

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

Servlet详解

1、Servlet是运行于支持Java的应用服务器中，用于交互式的浏览和修改数据，生成动态Web内容。

  • 我们要自定义一个Servlet广义上必须实现Servlet接口
  • Servlet接口有两个实现类，而HttpServlet又继承GenericServlet类，这两个类都是抽象类
    • GenericServlet
    • HttpServlet
  • 我们一般创建JavaWeb项目都是基于Http协议，所以创建Servlet都是继承HttpServlet

2、Servlet工作模式

  • 客户端发送请求至服务器
  • 服务器启动并接受客户端发送的请求，调用对应的Servlet处理请求，并生成响应内容将其传给服务器
  • 服务器将响应内容返回给客户端

3、Servlet的生命周期

1
2
3
4
5
6
7
java复制代码
public interface Servlet {
    void init(ServletConfig var1) throws ServletException;
 
    void service(ServletRequest var1, ServletResponse var2) throws ServletException, IOException;
 
    void destroy();
  • 当Servlet第一次被请求时，服务器就会调用init()方法初始化一个Servlet对象，但是这个方法在后续的请求中不会再次被调用，仅仅只会调用一次。在调用这个方法时，Servlet容器会传入一个ServletConfig对象来对Servlet对象进行初始化。
  • 每次客户端请求这个Servlet时，Servlet容器就会调用service()方法处理请求；在后续的请求中，Servlet容器就只会调用这个方法了。
  • 当服务器关闭或者停止时，Servlet容器就会调用destroy()销毁这个Servlet。
  • 每一个Servlet在容器中只会存在一个Servlet对象，是单例的

4、ServletContext对象

web容器在启动的时候，会为每一个web应用创建一个唯一的ServletContext对象，它代表了当前的web应用

共享数据

1
2
3
4
5
6
java复制代码@Override
    protected void doGet(HttpServletRequest req, HttpServletResponse resp) throws ServletException, IOException {
        // 使用ServletContext共享数据
        ServletContext servletContext = this.getServletContext();
        servletContext.setAttribute("username","Vecal");
    }
1
2
3
4
5
6
7
8
9
10
11
java复制代码@Override
    protected void doGet(HttpServletRequest req, HttpServletResponse resp) throws ServletException, IOException {
        //获取共享数据
        ServletContext context = this.getServletContext();
        String username = (String) context.getAttribute("username");

        resp.setContentType("text/html;charset=utf-8");
        resp.setCharacterEncoding("utf-8");

        resp.getWriter().print("姓名 ：" + username);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
xml复制代码<!-- 配置Servlet映射 -->
<servlet>
        <servlet-name>hello</servlet-name>
        <servlet-class>com.vecal.servlet.HelloServlet</servlet-class>
    </servlet>
    <servlet-mapping>
        <servlet-name>hello</servlet-name>
        <url-pattern>/hello</url-pattern>
    </servlet-mapping>

    <servlet>
        <servlet-name>get</servlet-name>
        <servlet-class>com.vecal.servlet.GetServlet</servlet-class>
    </servlet>
    <servlet-mapping>
        <servlet-name>get</servlet-name>
        <url-pattern>/get</url-pattern>
    </servlet-mapping>

获取初始化参数

1
2
3
4
5
xml复制代码<!-- 自定义初始化参数 -->
<context-param>
    <param-name>url</param-name>
    <param-value>jdbc:mysql://localhost:3306/mybatis</param-value>
</context-param>
1
2
3
4
5
6
java复制代码@Override
    protected void doGet(HttpServletRequest req, HttpServletResponse resp) throws ServletException, IOException {
        ServletContext context = this.getServletContext();
        String url = context.getInitParameter("url");
        resp.getWriter().print(url);
    }

请求转发

1
2
3
java复制代码// 请求转发
ServletContext context = this.getServletContext();
context.getRequestDispatcher("/initParam").forward(req,resp);

读取资源文件

  • 在java目录下新建资源文件
  • 在resources目录下新建资源文件

都会被打包放到了同一目录下：classes，这个路径统称为 classpath: 路径

如果发现在java目录中的资源文件没有被打包放在classes目录下，需要在pom.xml中进行以下配置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
xml复制代码<build>
      <resources>
        <resource>
            <directory>src/main/resources</directory>
            <excludes>
                <exclude>**/*.properties</exclude>
                <exclude>**/*.xml</exclude>
             </excludes>
            <filtering>false</filtering>
        </resource>
        <resource>
            <directory>src/main/java</directory>
            <includes>
                <include>**/*.properties</include>
                <include>**/*.xml</include>
            </includes>
            <filtering>false</filtering>
        </resource>
    </resources>
</build>
1
2
3
4
5
6
7
8
9
10
11
12
13
java复制代码@Override
protected void doGet(HttpServletRequest req, HttpServletResponse resp) throws ServletException, IOException {
        // 读取配置文件
        ServletContext context = this.getServletContext();
        InputStream in = context.getResourceAsStream("/WEB-INF/classes/db.properties");
        Properties prop = new Properties();
        prop.load(in);

        String username = prop.getProperty("username");
        String password = prop.getProperty("password");

        resp.getWriter().print(username + ":" + password);
    }

5、HttpServletResponse

web服务器在接收到客户端的http请求，针对这个请求，分别创建了一个代表请求的HttpServletRequest对象，一个代表响应的HttpServletResponse对象

  • 如果要获取客户端请求的一些数据参数，使用HttpServletRequest
  • 如果要响应一些数据给客户端，使用HttpServletResponse

1. 向浏览器发送数据

1
2
3
java复制代码ServletOutputStream getOutputStream() throws IOException;

PrintWriter getWriter() throws IOException;

2. 设置响应头

1
2
3
4
5
6
7
java复制代码void setCharacterEncoding(String var1);

void setContentLength(int var1);

void setContentLengthLong(long var1);

void setContentType(String var1);

3. 响应状态码

1
2
3
4
java复制代码int SC_OK = 200;
int SC_FOUND = 302;
int SC_BAD_REQUEST = 400;
int SC_INTERNAL_SERVER_ERROR = 500;

4. 下载文件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
java复制代码@Override
protected void doGet(HttpServletRequest request, HttpServletResponse response) throws ServletException, IOException {
        // 1.获取图片路径
        String realPath = "D:\\How2JTest\\project\\javaweb-02-servlet\\response\\target\\response\\WEB-INF\\classes\\黄濑凉太.jpg";
        // 2.获取文件名
        String fileName = realPath.substring(realPath.lastIndexOf("/") + 1);
        System.out.println("文件下载的路径： " + realPath);
        // 3.设置响应头,URLEncoder.encode()处理文件名中文乱码问题
        response.setHeader("Content-Disposition","attachment;filename=" + URLEncoder.encode(fileName,"UTF-8"));
        // 4.获取文件流
        FileInputStream in = new FileInputStream(realPath);
        // 5.设置缓冲区
        int len = 0;
        byte[] buffer = new byte[1024];

        // 6.写出文件
        ServletOutputStream os = response.getOutputStream();
        while ((len = in.read(buffer)) != -1){
            os.write(buffer, 0, len);
        }

        os.close();
        in.close();
    }

5. 实现重定向

  • URL地址栏会发生改变
1
2
3
4
5
java复制代码@Override
protected void doGet(HttpServletRequest req, HttpServletResponse response) throws ServletException, IOException {
    // 请求重定向，url地址栏会发生改变
    response.sendRedirect("/r/down");
}

6、HttpServletRequest

HttpServletRequest代表客户端的请求，用户通过http协议访问服务器，HTTP服务器会将所有的请求信息封装到这个对象中。

1.获取前端传递的参数

1
2
3
4
java复制代码// 获取指定名称的一个参数
String getParameter(String var1);
// 获取指定名称的多个参数
String[] getParameterValues(String var1);

7、请求和转发的区别

面试题：请你聊一聊转发和重定向的区别？

相同点:

  • 页面都会实现跳转

不同点：

  • 请求转发时，URL地址栏不会发生改变
  • 请求重定向时，URL地址栏会发生改变

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

1 概述

Gradle由于构建速度比Maven快，且比Maven灵活，因此很多后端的应用都使用了Gradle进行构建，但一个问题是，Gradle的多模块项目比较难构建，再加上Gradle的更新非常快，这就给构建一个多模块Gradle项目造成了不少的困难。

基于此出发点，本文提供了两种形式的使用Gradle构建的Spring Boot多模块项目：

  • Java + Gradle
  • Kotlin + Gradle + Kotlin DSL

为了减少出现各种错误的概率，步骤做得非常详细（多图预警），文末也附上了源码，下面就一起来看看吧。

2 环境

  • Gradle 7.4
  • Spring Boot 2.6.4
  • Kotlin 1.6.10
  • OpenJDK 17

3 Java + Gradle

主要步骤：

  • 使用Spring Initializer创建项目
  • 修改build.gradle
  • 创建模块
  • 编写模块
  • 运行
  • 测试

3.1 创建项目

直接使用IDEA提供的Spring Initializer即可，构建工具选择Gradle：

在这里插入图片描述

依赖：

在这里插入图片描述

构建完成后删除src目录，因为根目录属于管理模块目录不提供运行的应用：

在这里插入图片描述

3.2 修改build.gradle

这是最复杂的一步，并且Gradle版本更新的话步骤可能会不一样，首先在底部添加一个空的subprojects：

在这里插入图片描述

接着把dependencies以及tasks.name('test')移动进去：

在这里插入图片描述

最后一步是，在subprojects开头，添加插件apply，根据默认初始化创建的plugins，逐一添加。

比如这里默认使用了三个插件：

在这里插入图片描述

apply到subprojects中：

在这里插入图片描述

3.3 创建模块

File -> New -> Module：

在这里插入图片描述

输入模块名即可，这里的例子是创建两个模块：

  • service
  • app

在这里插入图片描述

在这里插入图片描述

创建好后如图所示：

在这里插入图片描述

完成创建之后，把两个模块中的build.gradle除了repositories之外的全部删去，仅保留repositories：

在这里插入图片描述

3.4 编写模块

3.4.1 service模块

首先创建包，根据根目录中的build.gradle中的group创建：

在这里插入图片描述

在这里插入图片描述

接着编写一个叫TestService的带@Service注解的类，里面包含一个test方法：

在这里插入图片描述

同时修改service模块的build.gradle，添加bootJar以及jar选项：

1
2
3
4
5
6
7
bash复制代码bootJar{
    enabled = false
}

jar{
    enabled = true
}

在这里插入图片描述

3.4.2 app模块

同样先创建包：

在这里插入图片描述

接着在app模块的build.gradle添加service模块的依赖：

在这里插入图片描述

再创建启动类以及一个Controller：

在这里插入图片描述

代码如下：

1
2
3
4
5
6
7
8
9
10
11
java复制代码package com.example.app;

import org.springframework.boot.SpringApplication;
import org.springframework.boot.autoconfigure.SpringBootApplication;

@SpringBootApplication(scanBasePackages = "com.example")
public class Application {
    public static void main(String[] args) {
        SpringApplication.run(Application.class,args);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
java复制代码package com.example.controller;

import com.example.service.TestService;
import lombok.RequiredArgsConstructor;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.web.bind.annotation.GetMapping;
import org.springframework.web.bind.annotation.RestController;

@RestController
@RequiredArgsConstructor(onConstructor = @__(@Autowired))
public class TestController {
    private final TestService service;
    @GetMapping("/test")
    public String test(){
        return service.test();
    }
}

注意，因为Spring Boot无法自动识别其他模块下的类，所以需要手动处理一下，有三种方法：

  • 第一种：使用@Import，也就是@Import(TestService.class)
  • 第二种：使用scanBasePackageClasses，也就是@SpringBootApplication(scanBasePackageClasses={TestService.class})
  • 第三种：使用scanBasePackages，也就是例子中的代码@SpringBootApplication(scanBasePackages = "com.example")

3.5 运行

接下来就可以运行了，可以直接点击Application旁边的绿色小三角：

在这里插入图片描述

或者从运行配置中选择Application运行（IDEA自动创建的，原来的那个JavaGradleApplication带一个×是因为启动文件已经删除了，可以顺便把该配置删除）：

在这里插入图片描述

没问题的话就可以成功运行了：

在这里插入图片描述

同时浏览器访问localhost:8080/test会出现test字样：

在这里插入图片描述

3.6 测试

创建包和测试类：

在这里插入图片描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
java复制代码package com.example.test;

import com.example.service.TestService;
import org.junit.jupiter.api.Test;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.boot.test.context.SpringBootTest;

@SpringBootTest(classes = TestService.class) //需要引入对应的类
public class JavaGradleTest {
    @Autowired
    private TestService service;

    @Test
    public void test() {
        System.out.println(service.test());
    }
}

接着进行测试：

在这里插入图片描述

当然测试也可以跑一下Gradle中的任务：

在这里插入图片描述

3.7 打包

打包的话直接运行bootJar即可：

在这里插入图片描述

会在build/libs下生成JAR包：

在这里插入图片描述

测试：

在这里插入图片描述

在这里插入图片描述

再次访问localhost:8080/test没有问题。

这样使用Java+Gradle构建一个多模块的Spring Boot项目就成功了。

4 Kotlin + Gradle + Kotlin DSL

Kotlin DSL在原生Gradle（Groovy DSL）的基础上进行改进，但同时语法也变得更加陌生，难度因此也加大了不少，不过这并没有难倒笔者。构建多模块的基本步骤与上面类似：

  • 使用Spring Initializer创建项目
  • 修改build.gradle.kts
  • 创建模块
  • 编写模块
  • 运行
  • 测试

4.1 创建项目

选择Kotlin+Gradle：

在这里插入图片描述

依赖：

在这里插入图片描述

同样删除src：

在这里插入图片描述

4.2 修改build.gradle.kts

同样在尾部添加一个空的subprojects：

在这里插入图片描述

把dependencies以及tasks移动进去：

在这里插入图片描述

最后在subprojects开始处apply插件，根据默认的插件进行apply：

在这里插入图片描述

代码如下：

1
2
3
4
5
6
bash复制代码apply{
    plugin("org.springframework.boot")
    plugin("io.spring.dependency-management")
    plugin("org.jetbrains.kotlin.jvm")
    plugin("org.jetbrains.kotlin.plugin.spring")
}

plugins中的kotlin是org.jetbrains.kotlin的简写，在subprjects中注意加上即可。

4.3 创建模块

File -> New -> Module，把一些必要选项勾选上：

在这里插入图片描述

这里同样创建两个模块：

  • service
  • app

在这里插入图片描述

在这里插入图片描述

同样把两个模块中的**build.gradle.kts删除其他部分留下repositories**：

在这里插入图片描述

4.4 编写模块

4.4.1 service模块

首先根据根目录的build.gradle.kts创建包：

在这里插入图片描述

在这里插入图片描述

编写TestService：

在这里插入图片描述

最后修改build.gradle.kts，加上tasks.bootJar与tasks.jar：

1
2
3
4
5
6
7
bash复制代码tasks.bootJar{
    enabled = false
}

tasks.jar{
    enabled = true
}

在这里插入图片描述

4.4.2 app模块

先创建包：

在这里插入图片描述

添加对service模块的依赖：

在这里插入图片描述

再创建一个启动类以及一个Controller：

在这里插入图片描述

代码如下：

1
2
3
4
5
6
7
8
9
10
11
kotlin复制代码package com.example.app

import org.springframework.boot.SpringApplication
import org.springframework.boot.autoconfigure.SpringBootApplication

@SpringBootApplication(scanBasePackages = ["com.example"])
class Application

fun main(args:Array<String>) {
    SpringApplication.run(Application::class.java,*args)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
kotlin复制代码package com.example.app.controller

import com.example.service.TestService
import org.springframework.beans.factory.annotation.Autowired
import org.springframework.web.bind.annotation.GetMapping
import org.springframework.web.bind.annotation.RestController

@RestController
class TestController {
    @Autowired
    lateinit var service: TestService

    @GetMapping("/test")
    fun test() = service.test()
}

4.5 运行

点击main旁边的绿色小三角即可：

在这里插入图片描述

运行成功：

在这里插入图片描述

同样可以访问localhost:8080/test：

在这里插入图片描述

4.6 测试

创建包与测试类：

在这里插入图片描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
kotlin复制代码package com.example.test

import com.example.service.TestService
import org.junit.jupiter.api.Test
import org.springframework.beans.factory.annotation.Autowired
import org.springframework.boot.test.context.SpringBootTest

@SpringBootTest(classes = [TestService::class])
class KotlinTest {
    @Autowired
    lateinit var service: TestService

    @Test
    fun test() {
        println(service.test())
    }
}

直接点击小三角测试即可：

在这里插入图片描述

测试通过。

4.7 打包

bootJar即可：

在这里插入图片描述

同样会在libs下生成JAR：

在这里插入图片描述

运行测试后没有问题，这样Kotlin+Gradle+Kotlin DSL的多模块Spring Boot项目就算创建完成了。

5 源码

附上两个例子的源码：

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于
  1. 下载链接

PyCharm for Windows ：www.jetbrains.com/pycharm/dow…

PyCharm for Mac ：www.jetbrains.com/pycharm/dow…

PyCharm for Linux ：www.jetbrains.com/pycharm/dow…

  1. 安装步骤

下载完成后，双击 exe 文件

选择安装目录，Pycharm需要的内存较多，建议将其安装在D盘或者E盘，不建议放在系统盘C盘：

选好路径后，点击 Next ，创建桌面快捷方式等一系列选项参照下图勾选！

最后默认安装即可，直接点击Install。

7、耐心的等待两分钟左右。

之后就会得到下面的安装完成的界面

点击Finish，Pycharm安装完成。

接下来对Pycharm进行配置，双击运行桌面上的Pycharm图标，进入下图界面：

选择Do not import settings，之后选择OK，进入下一步。

下面是选择主题

-> 这里默认选择黑色(左边黑色,右边白色)

-> 点击Next:Featured plugins

建议选择Darcula主题，该主题更有利于保护眼睛。

至此，PyCharm 就安装完成。

教程 PDF 下载

《PyCharm中文指南》下载链接：wws.lanzous.com/ijNfUmcm90f

系列导读

文章最后给大家介绍两个我自己写的在线文档：

第一个文档：PyCharm 中文指南 1.0 文档

整理了 100 个 PyCharm 的使用技巧，为了让新手能够直接上手，我花了很多的时间录制了上百张 GIF 动图，有兴趣的前往在线文档阅读。

第二个文档：PyCharm 黑魔法指南 1.0 文档

系统收录各种 Python 冷门知识，Python Shell 的多样玩法，令人疯狂的 Python 炫技操作，Python 的超详细进阶知识解读，非常实用的 Python 开发技巧等。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

⭐️ 本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 [彭旭锐] 和 [BaguTree Pro] 知识星球提问。

在 Android 生态中主要有 C++、Java、Kotlin 三种语言 ，它们的关系不是替换而是互补。其中，C++ 的语境是算法和高性能，Java 的语境是平台无关和内存管理，而 Kotlin 则融合了多种语言中的优秀特性，带来了一种更现代化的编程方式。

本文是 Kotlin 编程与跨平台系列的第 3 篇文章，完整文章目录请移步到文章末尾~

历史上的今天

2000 年 2 月 29 日，R 1.0.0 正式发布。
R 语言最初是由新西兰奥克兰大学的罗斯·伊哈卡和罗伯特·杰特曼开发的，由来由 “R 开发核心团队” 负责。R 是基于 S 语言的一个 GNU 计划项目，语法来自 Schema，主要用于统计分析、绘图和数据挖掘。RStudio 是针对 R 语言设计的广泛使用的集成开发环境。
—— 《了不起的程序员》

前言

扩展是 Kotlin 的一种语言特性，即：在不修改类 / 不继承类的情况下，向一个类添加新函数或者新属性。扩展使我们可以合理地遵循开闭原则，在大多数情况下是比继承更好的选择。

目录

前置知识

这篇文章的内容会涉及以下前置 / 相关知识，贴心的我都帮你准备好了，请享用~

  1. 为什么要使用扩展？

在 Java 中，我们习惯于把通用代码封装到工具类中，诸如 StringUtils、ViewUtils 等，例如：

StringUtils.java

1
2
3
typescript复制代码public static void firstChar(String str) {
    ...
}

在使用时，我们就需要调用StringUtils.firstChar(str)。然而，这种传统的调用方式不够简单直接，表意性也不够强，会让调用方忽略 String 和 firstChar() 间的强联系。另外，调用方也希望省略 StringUtils 类名，让 firstChar() 看起来更像是 String 内部的一个属性和方法，像这样："str".firstChar()。

要实现这种方式，在 Java 中就需要修改或继承 String 类，然而 String 是 JDK 中的 final 类，不能修改或继承。

这个时候可以使用 Kotlin 扩展来解决这个问题，我们可以把 firstChar 定义为 String 的扩展函数：

StringUtils.kt

1
2
3
4
5
kotlin复制代码定义 String 的扩展函数

fun String.firstChar() {
    ...
}

此时，在使用时可以采用"str".firstChar()的方式。在这里我们扩展了 String 类，却没有修改或继承 String。

总结：扩展是 Kotlin 中的一种特性，可以 在不修改类 / 不继承类的情况下，向一个类添加新函数或者新属性，更符合开闭原则。

开闭原则（OCP，Open Closed Principle）

开闭原则是面向对象软件设计的原则之一，即：对扩展开放，而对修改是封闭的。

  1. 扩展函数 & 扩展属性

2.1 声明扩展

声明扩展非常简单，只需要在声明时增加「类或者接口名」。这个类的名称称为 接收者类型（receiver type），调用这个扩展的对象称为 接收者对象。大多数情况下，扩展会声明为「顶级成员」，例如：

Utils.kt

1
2
3
4
5
6
7
8
9
10
kotlin复制代码声明扩展函数：
fun <T : Any?> MutableList<T>.exchange(fromIndex: Int, toIndex: Int) {
    val temp = this[fromIndex]
    this[fromIndex] = this[toIndex]
    this[toIndex] = temp
}

声明扩展属性：
val MutableList<Int>.sumIsEven
    get() = this.sum() % 2 == 0

在使用时，就可以直接像使用普通成员函数 / 属性一样：

xxx.kt

1
2
3
4
5
6
7
ini复制代码val list = mutableListOf(1,2,3)

使用扩展函数：
list.exchange(1,2)

使用扩展属性：
val isEven = list.sumIsEven

提示： MutableList 是接收者类型，list 是接收者对象。

在扩展函数内部，你可以像 「成员函数」 那样使用this来引用接受者对象，当然有时也可以省略，例如：

1
2
3
kotlin复制代码声明扩展属性：
val MutableList<Int>.sumIsEven
    get() = this.sum() % 2 == 0 // 省略了 this.sum() 中的 this

2.2 可空接收者

在 第 2.1 节 中使用了「非空的接收者类型」来定义扩展（MutableList 没有关键词?），当使用「可空变量」调用扩展时，会报编译时错误。例如：

1
2
kotlin复制代码val list:MutableList<Int>? = null
list.sumIsEven // Only safe (?.) or non-null asserted (!!.) calls are allowed on a nullable receiver of type MutableList<Int>?

根据提示，我们知道可以 使用「可空的接收者类型」来定义扩展，同时还要在内部使用null == this来对接收者对象进行判空。例如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
kotlin复制代码可空接收者类型的扩展函数
fun <T : Any?> MutableList<T>?.exchange(fromIndex: Int, toIndex: Int) {
    if (null == this) return
    val temp = this[fromIndex]
    this[fromIndex] = this[toIndex]
    this[toIndex] = temp
}

可空接收者类型的扩展属性
val MutableList<Int>?.sumIsEven: Boolean
    get() = if (null == this)
        false
    else
        this.sum() % 2 == 0

2.3 在 Java 中调用

扩展的本质：扩展函数是定义在类外部的静态函数，函数的第一个参数是接收者类型的对象。这意味着调用扩展时不会创建适配对象或者任何运行时的额外消耗。

在 Java 中，我们只需要像调用普通静态方法那样调用扩展即可。例如：

xxx.java

1
2
3
4
5
6
7
ini复制代码ArrayList<Integer> list = new ArrayList<>(3);

使用扩展函数：
UtilsKt.exchange(list, 1, 2);

使用扩展属性：
boolean isEven = UtilsKt.getSumIsEven(list);

2.4 扩展的作用域

当你定义了一个扩展之后，它不会自动在整个项目内生效。在其它包路径下，需要使用improt导入。例如：

1
2
3
arduino复制代码import Utils.exchange
或
import Utils.*

当你在不同包中定义了 「重名扩展」，并且需要在同一个文件中去使用它们，那么你需要使用as关键字重新命名。例如：

1
2
3
4
arduino复制代码import Utils.exchange as swap

使用时：
list.swap(0,1)

2.5 注意事项

  • 1、扩展函数不能访问 private 或 protected 成员

扩展函数或扩展属性本质上是定义在类外部的静态方法，因此扩展不可能打破类的封装性而去调用 private 或 protected 成员；

  • 2、不能重写扩展函数

扩展函数在 Java 中会被编译为静态函数，并不是类的一部分，不具备多态性。尽管你可以给父类和子类都定义一个同名的扩展函数，看起来像是方法重写，但实际上两个函数没有任何关系。当这个函数被调用时，具体调用的函数版本取决于变量的 「静态类型」，而不是 「动态类型」。

静态方法调用

关于 Java 方法调用的本质，在我之前写过的一篇文章里系统分析过：Java | 方法调用的本质（含重载与重写区别）。静态方法调用在编译后生成invokestatic 字节码指令，它的处理逻辑如下：

  • 1、编译阶段：确定方法的符号引用，并固化到字节码中方法调用指令的参数中；
  • 2、类加载解析阶段：根据符号引用中类名，在对应的类中找到简单名称与描述符相符合的方法，如果找到则将符号引用转换为直接引用；否则，按照继承关系从下往上依次在各个父类中搜索；
  • 3、调用阶段：符号引用已经转换为直接引用；调用invokestatic不需要将对象加载到操作数栈，只需要将所需要的参数入栈就可以执行invokestatic指令。
  • 3、如果类的成员函数和扩展函数拥有相同的签名，成员函数优先
  • 4、扩展属性没有支持字段，不会保存任何状态

扩展属性是没有状态的，必须定义 getter 访问器。因为不可能给现有的 Java 类添加额外的字段，所以也就没有地方可以存储支持字段。举个例子，以下代码是编译错误的：

1
2
3
4
5
kotlin复制代码val MutableList<Int>?.sumIsEven: Boolean = true // (X) Initializer is not allowed here because this property has no backing field
    get() = if (null == this)
        false
    else
        this.sum() % 2 == 0
  1. 标准库中的函数

在 Kotlin 标准库中，定义了一系列通用的内联函数：T.apply、T.also、T.let、T.run、with。你是否清楚理解它们的用法 & 本质，它们都是扩展函数吗？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
kotlin复制代码val str1: String = "".run {
    println(this.length)
    this
}

val str2: String = with("") {
    println(this.length)
    this
}

val str3: String = "".apply {
    println(this.length)
}

val str4: String = "".also {
    println(it.length)
}

val str5: String = "".let {
    println(it.length)
    it
}

在上面的示例中，我们看到有的函数作用域内使用了this，而其它又使用了it。这两个关键字到底引用的是什么，为什么会有差别呢？

我们先找到这些函数的声明：

standard.kt

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
kotlin复制代码public inline fun <R> run(block: () -> R): R { 
    return block()
}

public inline fun <T, R> T.run(block: T.() -> R): R {
    return block()
}

public inline fun <T, R> with(receiver: T, block: T.() -> R): R {
    return receiver.block()
}

public inline fun <T> T.apply(block: T.() -> Unit): T {
    block()
    return this
}

public inline fun <T> T.also(block: (T) -> Unit): T {
    block(this)
    return this
}

public inline fun <T, R> T.let(block: (T) -> R): R {
    return block(this)
}

一脸懵逼，别急，我们梳理一下：

函数 参数1 参数2 返回值
run / ()->R R
T.run / T.()->R R
with T T.()->R R
T.apply / T.()->Unit T
T.also / (T)->Unit T
T.let / (T)->R R

还是一脸懵逼，那我提几个问题：

  • runvsT.run，差了一个T，区别是什么？
    区别在于：run是普通函数，T.run是扩展函数。run中的this是声明的类对象（顶级函数除外），T.run中的this是接收者对象；
  • T.()->Unitvs(T)->Unit，或者T.()->Rvs(T)->R，T 的位置不同，区别是什么？
    区别在于：T.()->Unit中的 T 是接收者类型，(T)->Unit中的 T 是函数参数；
  • 为什么with用this，let用it？
+ run、with、apply 函数中的参数 block 是 **「T 的扩展函数」**，所以采用 this 是扩展函数的接收者对象（receiver）。另外因为 block 没有参数，所以不存在 it 的定义。
+ also 和 let 参数 block 是 **「参数为 T 的函数」**，所以采用 it 是唯一参数（argument）。另外因为 block 不是扩展函数，所以不存在 this 的定义。

lambda 表达式

lambda 表达式本质上是 「可以作为值传递的代码块」。在老版本 Java 中，传递代码块需要使用匿名内部类实现，而使用 lambda 表达式甚至连函数声明都不需要，可以直接传递代码块作为函数值。

当 lambda 表达式只有一个参数，可以用it关键字来引用唯一的实参。

  1. 扩展的应用场景

在这一节里，我们来介绍一些在 Android 开发中使用扩展的应用场景。

4.1 封装工具 Utils

在 Java 中，我们习惯于把通用代码封装到工具类中。传统 Java 的工具方法的调用方式不够简单直接，表意性也不够强，会让调用方忽略 String 和 firstChar() 间的强联系。另外，调用方也希望省略 StringUtils 类名，让 firstChar() 看起来更像是 String 内部的一个属性和方法。这些需求对 Kotlin 扩展来说都不是问题。

4.2 解决烦人的 findViewById

在 Android 中，经常会调用 findViewById() 来找到视图树中的某一个 View 实例，例如：

1
2
ini复制代码旧版 SDK：loginButton = (Button) findViewById(R.id.btn_login);
新版 SDK：loginButton = findViewById(R.id.btn_login);

提示： 新版的 SDK 中，findViewById() 是一个泛型方法，所以你就不再需要进行强制类型转换。

1
2
3
4
5
> less复制代码public <T extends View> T findViewById(@IdRes int id) {
>    return getWindow().findViewById(id);
> }
> 
>

通常，我们会定义一个实例变量或者局部变量来承载 findViewById() 的返回值，很多时候，这些变量都只是 “临时变量” ，在进行事件绑定 / 赋值之后就没有很大的用处了。如果你面对一些比较复杂的界面，你甚至需要定义几十行临时变量！

能不能省略这些临时变量，直接操作R.id.*呢？答案是可以的，我们可以利用 Kotlin 「高阶函数 + 扩展函数」。例如：

1
2
3
4
5
6
7
kotlin复制代码fun Int.onClick(click: () -> Unit) {
    findViewById<View>(this).apply {
        setOnClickListener {
            click()
        }
    }
}

此时，我们可以直接使用R.id.*来绑定点击事件（R.id* 本质就是一个整数类型）：

1
2
3
perl复制代码R.id.btn_login.onClick {
    // do something
}

这样就简洁多了，我们就不再需要定义一堆临时变量了。不过，你每次都需要写R.id前缀，这似乎也很多余，能不能再省略呢？确实可以，我们需要使用 Kotlin 为 Android 量身定制的 Gradle 插件：kotlin-android-extensions。

1
arduino复制代码apply plugin : 'kotlin-android-extension'

此时，我们可以直接用组件的 id 来操作 View 实例，例如：
MainActivity .java

1
2
3
perl复制代码btn_login.setOnClickListener{
    // do something
}

我们试试反编译这段代码，可以看到kotlin-android-extensions插件自动在 Activity 类中插入了以下代码：

MainActivity.class

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
kotlin复制代码public class MainActivity extends AppCompatActivity {

    private HashMap _$_findViewCache;

    @Override
    protected void onCreate(@Nullable Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);

        ((Button) this._$_findViewCache(id.btn_login)).setOnClickListener((View.OnClickListener) null.INSTANCE);
    }

    public View _$_findCachedViewById(int var1) {
        if (this._$_findViewCache == null) {
            this._$_findViewCache = new HashMap();
        }
        View var2 = (View) this._$_findViewCache.get(Integer.valueOf(var1));
        if (var2 == null) {
            var2 = findViewById(var1);
            this._$_findViewCache.put(Integer.valueOf(var1), var2);
        }
        return var2;
    }

    public void _$_clearFindViewByIdCache() {
        if (this._$_findViewCache != null) {
            this._$_findViewCache.clear();
        }
    }
}

可以看到，在访问R.id.*控件时，先在缓存集合_$_findViewCache中查找，有就直接返回，没有就通过 findViewById() 进行查找，并添加到缓存集合中。

另外还提供了一个_$_clearFindViewByIdCache()方法，用于在彻底替换界面视图时清除彻底缓存。在 Fragment#onDestroyView() 中，会调用该方法清除缓存，而 Activity 中没有。

4.3 简洁的 LeetCode 题解

在解算法题时，使用扩展函数可以让代码更简洁，表意性更强。举个例子，我们需要交换数组中的两个位置上的元素。相对于传统的写法，可以看到扩展函数的写法意思更清楚。

1
2
3
4
5
6
7
8
9
kotlin复制代码fun swap(arr: IntArray, from: Int, to: Int) {
    ...
}
swap(arr,0,1)

fun IntArray.swap(from: Int, toInt) {
    ...
}
arr.swap(0,1)
  1. 总结
  • 扩展可以在不修改类 / 不继承类的情况下，向一个类添加新函数或者新属性，更符合开闭原则。相对于传统 Java 的工具方法的调用方式更简单直接，表意性更强；
  • 扩展函数是定义在类外部的静态函数，函数的第一个参数是接收者类型，调用扩展时不会创建适配对象或者任何运行时的额外消耗。在 Java 中，我们只需要像调用普通静态方法那样调用扩展即可；
  • 标准库提供的函数中，run、with、apply 函数中的参数 block 是「T 的扩展函数」，所以采用 this 是扩展函数的接收者对象（receiver）；also 和 let 参数 block 是「参数为 T 的函数」，所以采用 it 是唯一参数（argument）。

参考资料

推荐阅读

Kotlin 编程与跨平台系列完整目录如下（2023/07/11 更新）：

⭐️ 永远相信美好的事情即将发生，欢迎加入小彭的 Android 交流社群~

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

在这里插入图片描述

导语｜这是一篇go基本语法快速入门文章，学习该文章时，默认读者已安装成功Golang环境，若环境未安装成功，可自行百度。

原文地址：mp.weixin.qq.com/s/zvVzP0juP…

目录

  • 环境安装
  • 输出语句
  • Go语言关键字
  • 类型
    • 数据类型
    • 变量定义
      • var关键字定义
      • 简短模式
      • 多变量赋值
    • 常量
    • iota关键字
    • 运算符
  • 函数
  • 条件语句和循环语句
    • 条件语句
    • 循环语句
  • 数据
    • 数组
    • 字符串
    • 切片
      • 初始化slice
      • 示例
    • map字典
    • 结构体struct
  • 接口
    • 语法
    • 示例
  • 总结

环境安装

安装地址：www.cnblogs.com/aaronthon/p/10587487.html

输出语句

无论学那一门语言，首先先学该语言的输出语句。俗话说得好，输出”Hello, World!”，代表你入门成功！！！

1
2
3
4
5
6
7
go复制代码package main

import "fmt"

func main() {
  fmt.Println("Hello, World!")
}

接下来，一起学习go的基本语法，十分钟解决完战斗，走起！！！

Go语言关键字

首先先认识一下Go语言中关键字，心里有个印象，让初学者有个眼熟就行。记不住没关系，我会在下面语法反复提到。在这里之所以提出来，就是让你们看一下，看的看的就记住了。
在这里插入图片描述

类型

数据类型

在 Go 编程语言中，数据类型用于声明函数和变量。

数据类型的出现是为了把数据分成所需内存大小不同的数据，编程的时候需要用大数据的时候才需要申请大内存，就可以充分利用内存。

Go 语言按类别有以下几种数据类型：
在这里插入图片描述

变量定义

在数学概念中，变量表示没有固定值且可改变的数。但从计算机系统实现角度来看，变量是一段或多段用来存储数据的内存。

作为静态类型语言，go变量总是有固定的数据类型，类型决定了变量内存的长度和存储格式。我们只能修改变量值，无法改变类型。

var关键字定义

关键字var用于定义变量，和C不同，类型被放在变量后面。若显式提供初始值，可省略变量类型，由编译器推断。

1
2
go复制代码var X int // 自动初始化为零
var y = false // 自动推断为bool的类型

可一次性定义多个变量，类型可相同也可不相同。

1
2
go复制代码var x,y int
var a,b = 100, "abc"

简短模式

变量定义时，除var关键字外，还可使用更加简短的变量定义和初始化语法。

1
2
3
4
5
6
7
8
go复制代码package main

import "fmt"

func main() {
  x := 10 // 使用 := 进行定义并初始化
  fmt.Println(x) // 输出语句 10
}

使用简短模式的一些限制：

  • 定义变量，同时显式初始化。
  • 不能提供数据类型。
  • 只能用在函数内部，不能用在全局变量中。

多变量赋值

进行多变量赋值操作时，首先计算出等号右边值，然后再依次完成赋值操作。

1
2
3
4
5
6
7
8
9
go复制代码package main

import "fmt"

func main(){
  x, y := 10, 20
  x, y = y+3, x+2  // 先计算等号右边值，然后再对x、y变量赋值
  fmt.Println(x, y) // 输出语句  结果为：23 12
}

常量

常量表示运行时恒定不可改变的值，通常是一些字面量。使用常量就可用一个易于阅读理解的标识符号来代替”魔法数字”，也使得在调整常量值时，无须修改所有引用代码。

常量值必须是编译期可确定的字符、字符串、数字或布尔值。可指定常量类型，或由编译器通过初始化推断。

在go语言中，使用关键字const来定义常量。

1
2
go复制代码const x, y int = 10, 20
const a,b = "迈莫coding", "欢迎小伙伴"

示例：

1
2
3
4
5
6
7
8
9
10
11
go复制代码package main

import "fmt"

const (
   a, b string = "迈莫coding", "欢迎小伙伴"
)

func main() {
   fmt.Println(a,b) // 迈莫coding 欢迎小伙伴
}

iota关键字

Go中没有明确意思上的enum(枚举)定义，不过可以借用iota标识符实现一组自增常量值来实现枚举类型。

1
2
3
4
5
go复制代码const (
  a = iota // 0
  b        // 1
  c        // 2
)

变量a、b、c的值分别为0、1、2，原因是因为使用iota进行自增时，后续自增值按照序递增。通俗点是每新增一行，iota值加一。

若在中途中断iota自增，则必须显示恢复，如下所示：

1
2
3
4
5
6
7
8
go复制代码const (
  a = iota // 0
  b        // 1
  c = 100  // 100
  d        // 100 (与上一行常量值表达式一致)
  e = iota // 4 (恢复iota自增，计数包括c、d)
  f        // 5
)

运算符

运算符使用方式和其他语言基本一样，在这里就不一一介绍了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
go复制代码package main
import "fmt"
func main() {
   var a int = 21
   var b int = 10
   var c int
   c = a + b
   fmt.Println(c) // 31
   c = a - b
   fmt.Println(c) // 11
   c = a / b
   fmt.Println(c) // 2
   c = a % b
   fmt.Println(c) // 1
   a++
   fmt.Println(a) // 22
   a=21   // 为了方便测试，a 这里重新赋值为 21
   a--
   fmt.Println(a) // 20
}

函数

函数就是将复杂的算法过程分解为若干较小任务，进行拆分，易于维护。函数被设计成相对独立，通过接收输入参数完成一段算法指令，输出或存储相关结果。因此，函数还是代码复用和测试的基本单元。

关键字func用于定义函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
go复制代码package main

import "fmt"

// 定义 Write函数 返回值有两个，一个为name，一个age为
func Write() (name string, age int) {
   return "迈莫coding", 1
}

// 定义 Read函数
func Read(name string, age int) {
   fmt.Println(name, " 已经 ", age, " 岁了")
}

func main() {
   Read(Write()) // 迈莫coding  已经  1  岁了
}

条件语句和循环语句

条件语句

条件语句需要开发者通过指定一个或多个条件，并通过测试条件是否为 true 来决定是否执行指定语句，并在条件为 false 的情况在执行另外的语句。

下图展示了程序语言中条件语句的结构：

在这里插入图片描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
go复制代码package main

import "fmt"

func main() {
  x := 3
  
  if x > 5 {
    fmt.Println("a")
  } else if x < 5 && x > 0 {
    fmt.Println("b")
  } else {
    fmt.Println("c")
  }
}

循环语句

在不少实际问题中有许多具有规律性的重复操作，因此在程序中就需要重复执行某些语句。

以下为大多编程语言循环程序的流程图：

在这里插入图片描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
go复制代码package main

import "fmt"

func main() {
  for i := 0; i < 5; i++ {
    if i == 4 {
      continue
    } else if i == 5 {
      break
    }     
    fmt.Println(i)
  }
}

数据

数组

Go 语言提供了数组类型的数据结构。

数组是具有相同唯一类型的一组已编号且长度固定的数据项序列，这种类型可以是任意的原始类型例如整型、字符串或者自定义类型。

在这里插入图片描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
go复制代码package main

import "fmt"

func main() {
  var arr1 [4]int // 元素自动初始化为零
  fmt.Println(arr1) // [0 0 0 0]
  
  arr2 := [4]int{1,2} // 其他未初始化的元素为零
  fmt.Println(arr2) // [1 2 0 0]
  
  arr3 := [4]int{5, 3:10} // 可指定索引位置初始化
  fmt.Println(arr3) // [5 0 0 10]
  
  arr4 := [...]int{1,2,3} // 编译器按照初始化值数量确定数组长度
  fmt.Println(arr4) // [1 2 3]
  
  t := len(arr4) // 内置函数len(数组名称)表示数组的长度
  fmt.Println(t) // 3
}

字符串

字符串默认值不是nil，而是””。

1
2
3
4
5
6
7
8
9
go复制代码package main

import "fmt"

func main() {
  var str string
  str = "迈莫coding欢迎小伙伴"
  fmt.Println(str)
}

切片

切片(slice)本身不是动态数组或动态指针。只是它内部采用数组存储数据，当数组长度达到数组容量时，会进行动态扩容。

大白话就是切片功能和Java中的List集合类似，动态添加数据。不像数组(array)长度是固定的，需要事先知道数据长度。

初始化slice

1
go复制代码x := make([]int, 1) // 通过make关键字进行slice初始化

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
go复制代码package main

import "fmt"

func main() {
    // 方式一
    a := make([]int,5) // 初始化长度为5的slice,默认值为零
    for i := 0; i <5; i++ {
       a = append(a, i)
    }
    a = append(a, 6)
    fmt.Println(a) // [0 0 0 0 0 0 1 2 3 4 6] 

    // 方式二    
    var a []int
    for i := 0; i < 5; i++ {
       a = append(a, i)
    }
    fmt.Println(a) // [0 1 2 3 4]
}

map字典

map字典也是使用频率比较高的数据结构。将其作为语言内置类型，从运行时层面进行优化，可获得更高效类型。

作为无序键值对集合，字典key值必须是支持相等运算符的数据类型，比如数字、字符串、指针、数组、结构体，以及对应接口类型。

map字典功能和Java中的map集合功能类似。

字典是应用类型，使用make函数或初始化表达语句来创建。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
go复制代码package main

import "fmt"

func main() {
   // 定义 变量strMap
   var strMap map[int]string
   // 进行初始化
   strMap = make(map[int]string)
   
   // 给map 赋值
   for i := 0; i < 5; i++ {
      strMap[i]  = "迈莫coding"
   }
   
   // 打印出map值
   for k, v := range strMap{
      fmt.Println(k, ":", v)
   }
  
  // 打印出map 长度
  fmt.Println(len(strMap))   
}

结构体struct

结构体(struct)将多个不同类型命名字段(field)序列打包成一个复合类型。

字段名必须唯一，可用”_“补位，支持使用自身指针类型成员。字段属性为基本数据类型。

学过Java就可以进行类比，结构体struct可以类比为Java中的类，结构体struct中字段属性可以类比为Java中类成员变量，结构体struct的方法可以类比为Java中类成员方法。

结构体(struct)语法如下：

1
2
3
4
go复制代码type user struct {
  name string // 字段name 其数据类型为string
  age int // 字段age 其数据类型为int 
}

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
go复制代码package main

import "fmt"

type user struct {
   name string
   age  int
}

// 结构体user Read方法
func (u *user) Read() string {
   return fmt.Sprintf("%s 已经 %d 岁了", u.name, u.age)
}

func main() {
   // 初始化
   u := &user{
      name: "迈莫coding",
      age:  1,
   }
   fmt.Println(u.name, "已经", u.age, "岁了")
   // 调用结构体user的 Read方法
   fmt.Println(u.Read()) // 迈莫coding 已经 1 岁了
}

接口

接口代表一个调用契约，是多个方法声明的集合。

接口解除了类型依赖，有助于减少用户可视方法，屏蔽内部结构和实现细节。在Go语言中，只要目标类型方法集内包含接口声明的全部方法，就被视为实现了该接口，无须做显示声明。当然，目标类型可实现多个接口。

大白话，接口是多个方法声明的集合，若一个struct类实现接口中所有方法，即表示该类实现了指定接口。

语法

1
2
go复制代码type user interface{
}

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
go复制代码package main

import "fmt"

// 定义接口 包含公共方法
type user interface{
  talking()
}

// 定义一个struct类
type memo struct{
}

// 实现接口user中方法talking
func (m *memo) talking() {
  fmt.Println("迈莫coding欢迎您...")
}

func main() {
  mm := memo{}
  mm.talking()
}

总结

文章介绍了Go语言的基本语法，适合零小白查看，使其快速上手Go语言项目开发，但文章毕竟是快速入门，有许多没讲过的知识点，需读者自行学习，也可关注我，和我一起学习Go语言。

文章也会持续更新，可以微信搜索「 迈莫coding 」第一时间阅读。每天分享优质文章、大厂经验、大厂面经，助力面试，是每个程序员值得关注的平台。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

通常会对多列索引缺乏理解，常见的错误是将很多列设置独立索引，或者是索引列使用错误的次序。我们在下一篇讨论索引列次序的问题，首先看一下多列独立索引的情况，以下面的表结构为例：

1
2
3
4
5
6
7
8
sql复制代码CREATE TABLE test (
  c1 INT,
  c2 INT,
  c3 INT,
  KEY(c1),
  KEY(c2),
  KEY(c3),
);

使用这种索引策略通常是一些权威的建议（例如在WHERE条件中用到的条件列增加索引）的结果。事实上，这是大错特错的，要评分的话顶多给1颗星。这种方式的索引与真正优化的索引相比，要慢上几个数量级。有时候当你不能设计三星以上的索引时，去关注优化行次序或者创建覆盖索引都比忽略WHERE条件强。

覆盖索引（covering index）指一个查询语句的执行只用从索引中就能够取得，不必从数据表中读取。也可以称之为实现了索引覆盖。 当一条查询语句符合覆盖索引条件时，MySQL只需要通过索引就可以返回查询所需要的数据，这样避免了查到索引后再返回表操作，减少I/O提高效率。 如，表covering_index_sample中有一个普通索引 idx_key1_key2(key1,key2)。当我们通过SQL语句：select key2 from covering_index_sample where key1 = ‘keytest’;的时候，就可以通过覆盖索引查询，无需再从数据表找数据行。

对很多列创建独立的索引在很多情况下，并不能帮助MySQL改善性能。MySQL 5.0及更新的版本可以使用索引合并策略对这类设计进行些许的优化 —— 这种方式允许在有多列索引的数据表中的查询中限制在索引的使用去定位所需的数据行。

index merge 是对多个索引分别进行条件扫描，然后将它们各自的结果进行合并(intersect/union)

早期的MySQL版本只能使用一个索引，因此当没有索引辅助时，MySQL通常进行全表扫描。例如在film_actor表有一个film_id和actor_id索引，但是在WHERE条件中同时使用这两个索引并不是一个好的选择：

1
sql复制代码SELECT film_id, actor_id FROM film_actor WHERE actor_id = 1 OR film_id = 1;

在早期的MySQL版本中，除非你像下面的语句一样将两个查询联合起来，否则这个查询会导致全表扫描。

1
2
sql复制代码SELECT film_id, actor_id FROM film_actor WHERE actor_id = 1 UNION ALL 
SELECT film_id, actor_id FROM film_actor WHERE film_id = 1 AND actor_id <> 1;

在MySQL 5.0之后的版本中，查询会同时使用两个索引并且合并最终的结果。需要三个变体的算法实现这个过程：

  1. 使用OR条件获取并集（union）数据
  2. 使用AND条件获取交集数据
  3. 将上面两个步骤的数据的交集再取并集。

上面有点费解，其实应该是分布使用单个条件（以便使用索引）查出全部数据，然后再组合数据。下面使用EXPLAIN查看一下。

1
sql复制代码EXPLAIN SELECT `film_id`,`actor_id` FROM `film_actor` WHERE `actor_id`=1 OR `film_id`=1

image
可以看到查询方式是全表扫描，但是使用了Extra做优化。MySQL在处理负责查询时会使用这种技巧，因此你可能会在Extra中看到嵌套操作。这种索引合并的策略有些时候会发挥很好的作用，但更多的时候应该当作是对差劲索引使用的一个指示：

  1. 当服务器使用交集索引（通常是使用AND条件），通常意味着你需要一个索引包含所有相关的列，而不是独立的索引列再组合。
  2. 当服务器使用并集索引（通常是使用OR条件），有时候缓存、排序和合并操作会占用很多的CPU和内存资源，尤其是索引并不都是具备筛选的时候，这会导致扫描返回大量的数据行供合并操作。
  3. 记住优化器并不承担这些成本——它仅仅是优化随机页读取的数量。这会使得查询“掉价”，导致全表扫描造成事实上更慢。CPU和内存的高占用会影响并发查询，但这些影响在你单独运行查询语句时并不会发生。因此，有时候像在MySQL 4.1版本那样重写那些使用UNION的查询会得到更优的效果。

当你使用EXPLAIN分析的时候看到了索引合并，你应该检查查询语句和表结构，看看是不是最优的方式。你可以使用optimizer_switch（优化开关）禁用索引合并来检查。

再将film_actor的索引改为联合索引(删除原先的两列独立索引film_id和actor_id)看一下效果，可以看到此时避免了全表查询。

1
sql复制代码ALTER TABLE film_actor ADD INDEX `sindex` (`film_id`,`actor_id`);

image

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

正确地创建和使用索引对于查询性能十分重要。由于存在很多种特殊场景的优化和行为，因此有很多种方式去有效选择和使用索引。因此，决定如何使用索引这一项技能是需要经验和时间的积累去培养的。以下会介绍一些如何有效使用索引的方法。

隔离数据列

通常，我们会发现查询语句会妨碍MySQL使用索引。除非在查询语句中列是独立的，否则MySQL不会使用这些列的索引。“隔离”的意思是索引列不应该成为表达式的一部分或者在一个查询函数体中。例如下面的例子就不会命中actor_id这个索引。

1
sql复制代码SELECT `actor_id` FROM `actor` WHERE `actor_id` + 1 = 2;

对于人来说，很容易知道查询条件实际是actor_id = 4，但是MySQL不会这么处理，因此养成简化WHERE判决条件的习惯，这意味着索引列独立地在比较操作符的一侧。下面是另外一个普遍错误的案例：

1
sql复制代码SELECT ... WHERE TO_DAYS(CURRENT_DATE) - TO_DAYS(date_col) <= 10;

前缀索引和索引的选择性

有时候需要在很长字符的列上建立索引，但这样会导致索引占据的空间很大且查询变慢。一个策略是使用哈希索引模拟，但有时候这未必是足够好，这个时候该怎么做？

通常是可以将索引列前面的部分字符建立索引来替换全字段索引提高性能和节省空间。但这种方式会使得选择性变差。索引的选择性是指独立的索引值筛选出的数据占整个数据集合的比例。高选择性的索引可以让MySQL过滤掉更多无关的数据。例如，一个唯一索引的选择性是1。
列的前缀通常在选择性方面已经能够提供足够好的性能。如果使用BLOB或TEXT或非常长的VARCHAR字段列，你必须定义前缀索引，以为MySQL不允许做全长度索引。

你需要在使用更长的前缀以获得更好的选择性和足够短的前缀以节省存储空间之间平衡。为了确定一个合适的前缀长度，查找出最高频的值，然后和最频繁的前缀进行比较。例如以城市数据表为例，我们可以使用如下的语句统计：

1
sql复制代码SELECT COUNT(*) as cnt, `name` FROM `common_city` GROUP BY `name` ORDER BY cnt DESC LIMIT 10

image.png

可以看到这些城市名称出现的次数比较多。现在我们可以使用1个字的前缀查找最为频繁的城市名称前缀。

1
sql复制代码SELECT COUNT(*) as cnt, LEFT(`name`, 1) as pref FROM `common_city` GROUP BY pref ORDER BY cnt DESC LIMIT 10

image.png

可以看到1个字找出来的数据集更多了，这会导致独立选中的机会越少，因此需要调整一下前缀的长度。例如调到3个字。

1
sql复制代码SELECT COUNT(*) as cnt, LEFT(`name`, 3) as pref FROM `common_city` GROUP BY pref ORDER BY cnt DESC LIMIT 10

image.png

可以看到这和全长度的相差不多，那实际三个字的前缀就够了（原文使用的是英文城市数据表，字符会更多）。另外一种方式是使用不同长度的前缀数量与全字段数量的比例评估多少合适。例如：

1
2
3
4
5
6
sql复制代码SELECT 
  COUNT(DISTINCT LEFT(`name`, 1)) / COUNT(`name`) as pref1, 
  COUNT(DISTINCT LEFT(`name`, 2)) / COUNT(`name`) as pref2, 
  COUNT(DISTINCT LEFT(`name`, 3)) / COUNT(`name`) as pref3, 
  COUNT(DISTINCT LEFT(`name`, 4)) / COUNT(`name`) as pref4 
FROM `common_city`

image.png

数值越接近于1效果越好，但是也可以看到，随着前缀长度的加长改善的空间越小。只看平均值并不是一个好主意，还需要检查一下最坏情况。也许会觉得3-4个字足够了，但是如果数据分布很不均匀，那可能会存在陷阱。因此还需要检查一下前缀少的是不是存在一个前缀对应的数据与其他相比极其多的情况。最后可以给指定的列加前缀索引。

1
sql复制代码ALTER TABLE `common_city` ADD KEY (name(3));

前缀索引在节省空间和提高效率方面表现不错，但是也有缺陷，那就是在ORDER BY和GROUP BY上无法使用索引（实际验证在MySQL 5.7以上版本也有用）。另外一种常见的场景是在较长的十六进制字符串中，例如存储的sessionId，取前8位前缀做索引将过滤很多无关数据，效果很好。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%