tim_xiao

tim_xiao 查看完整档案

广州编辑  |  填写毕业院校  |  填写所在公司/组织 xiaohome.net 编辑
编辑

后端程序员
关注 php python golang

个人动态

tim_xiao 回答了问题 · 4月6日

nginx首页默认配置问题

通过location重新匹配路径到/www 就可以吧 不清楚楼主是这个意思吗

关注 2 回答 1

tim_xiao 发布了文章 · 4月6日

redis入门教程3-客户端

php

1:php-redis

c语言开发,效率较高。在使用前需要安装phpredis扩展。缺点是有些涉及底层的代码需要查看对应的C代码。一些框架(比如thinkphp)在操作redis时会优先使用php-redis。总体推荐使用

2:predis/predis

使用php开发的redis客户端。效率相对php-redis来说会低一些。不需要安装对应扩展。在一些框架中(laravel)会优先使用。据说后期将不再维护。

go

go-redis

github上star较多的一款go redis客户端。

查看原文

赞 1 收藏 1 评论 0

tim_xiao 提出了问题 · 4月1日

docker 生产环境部署和监控

docker生产环境持续集成有什么好的实践方案吗,配合jenkins使用。不想每次都重新打包整个容器。另外就是生产环境docker性能监控如何实践比较好呢

关注 2 回答 1

tim_xiao 回答了问题 · 3月28日

Git子仓库如何操作?

主仓库和子仓库(子模块)提交是分开的

通过 git submodule add xxxx [dir] 添加子仓库到指定目录

git submodule init 初始化子仓库

具体步骤 参考这里

关注 4 回答 3

tim_xiao 回答了问题 · 3月26日

解决php有没有异步执行的函数?

如果不用swoole的话 也是有其他办法的

1:fastcgi_finish_request将响应返回给客户端 在去执行后续费时的业务逻辑
https://www.php.net/manual/zh...

2:队列解耦,将费时的业务逻辑放入队列处理

关注 2 回答 2

tim_xiao 发布了文章 · 3月26日

linux进程常见信号

使用swoole进行进程相关编程时,经常会遇到关于进程信号的问题,在这里做一个整理

查看信号列表

[vagrant@localhost tmp]$ kill -l
 1) SIGHUP     2) SIGINT     3) SIGQUIT     4) SIGILL     5) SIGTRAP
 6) SIGABRT     7) SIGBUS     8) SIGFPE     9) SIGKILL    10) SIGUSR1
11) SIGSEGV    12) SIGUSR2    13) SIGPIPE    14) SIGALRM    15) SIGTERM
16) SIGSTKFLT    17) SIGCHLD    18) SIGCONT    19) SIGSTOP    20) SIGTSTP
21) SIGTTIN    22) SIGTTOU    23) SIGURG    24) SIGXCPU    25) SIGXFSZ
26) SIGVTALRM    27) SIGPROF    28) SIGWINCH    29) SIGIO    30) SIGPWR
31) SIGSYS    34) SIGRTMIN    35) SIGRTMIN+1    36) SIGRTMIN+2    37) SIGRTMIN+3
38) SIGRTMIN+4    39) SIGRTMIN+5    40) SIGRTMIN+6    41) SIGRTMIN+7    42) SIGRTMIN+8
43) SIGRTMIN+9    44) SIGRTMIN+10    45) SIGRTMIN+11    46) SIGRTMIN+12    47) SIGRTMIN+13
48) SIGRTMIN+14    49) SIGRTMIN+15    50) SIGRTMAX-14    51) SIGRTMAX-13    52) SIGRTMAX-12
53) SIGRTMAX-11    54) SIGRTMAX-10    55) SIGRTMAX-9    56) SIGRTMAX-8    57) SIGRTMAX-7
58) SIGRTMAX-6    59) SIGRTMAX-5    60) SIGRTMAX-4    61) SIGRTMAX-3    62) SIGRTMAX-2
63) SIGRTMAX-1    64) SIGRTMAX    

swoole 中使用signal进行异步信号监听,特别注意不能用户阻塞的程序中,不然会导致注册的监听回调函数得不到调度.

// swoole用来设置异步信号监听
Swoole\Process::signal(int $signo, callable $callback): bool
// swoole用来向进程发送信号 默认SIGTERM
Swoole\Process::kill(int $pid, int $signo = SIGTERM): bool

参考

SIGCHLD(17)

子进程退出的时候会向其父进程发送一个SIGCHLD信号

Swoole\Process::signal(SIGCHLD, function ($sig) {
    //必须为false,非阻塞模式
    while ($ret = Swoole\Process::wait(false)) {
        echo "PID={$ret['pid']}\n";
    }
});

swoole监听SIGCHLD信号,设置回调函数对子进程进行非阻塞回收

SIGTERM(15)

正常结束的信号,kill命令默认信号.

// 默认发送信号 SIGTERM
Swoole\Process::kill(int $pid, int $signo = SIGTERM): bool

SIGKILL(9)

强制进程退出。一般情况下使用SIGTERM即可。SIGKILL会导致进程立刻退出,不会做相关清理性工作

SIGINT(2)

键盘终止信号 相当于输出 Ctrl+C 快捷键

Swoole\Process::signal(SIGINT, function () {
    echo "INT\n";
});
Swoole\Timer::tick(5000, function () {

});

Swoole\Event::wait();

SIGHUP(1)

用在用户终端连接结束时发出(正常和非正常都包括),通知统一session内的各个作业。如果程序中 没有捕捉该信号,默认当当前进程退出。

Swoole\Process::signal(SIGHUP, function ($sig) {
    $myPid = getmypid();
    // 需要人工kill掉进程
    Swoole\Process::kill($myPid);
});

SIGUSR1(10)

用户用来设置自定义信号

查看原文

赞 0 收藏 0 评论 0

tim_xiao 赞了文章 · 3月19日

常见排序算法总结和 Go 标准库排序源码分析

前言

排序算法是数组相关算法的基础知识之一,它们的经典思想可以用于很多算法之中。这里详细介绍和总结 7 种最常见排序算法,并用 Go 做了实现,同时对比这几种算法的时间复杂度、空间复杂度和稳定性 。后一部分是对 Go 标准库排序实现的源码阅读和分析, 理解官方是如何通过将以上排序算法进行组合来提高排序性能,完成生产环境的排序实践。

排序算法分类

常见的这 7 种排序算法分别是:

  • 选择排序
  • 冒泡排序
  • 插入排序
  • 希尔排序
  • 归并排序
  • 快速排序
  • 堆排序

我们可以根据算法特点像复杂度、是否比较元素、内外部排序等特点对它们做分类,比如上面的算法都是内部排序的。一般可以基于算法是否比较了元素,将排序分为两类:

  1. 比较类排序:通过比较来决定元素间的相对次序。由于其平均时间复杂度不能突破$O(N\log N)$,因此也称为非线性时间比较类排序。
  2. 非比较类排序:不通过比较来决定元素间的相对次序。它可以突破基于比较排序的时间下界,以线性时间运行,因此也称为线性时间非比较类排序。主要实现有: 桶排序、计数排序和基数排序。

通过这个的分类,可以先有一个基本的认识,就是比较类排序算法的平均时间复杂度较好的情况下是 $O(N\log N)$(一遍找元素 $O(N)$,一遍找位置$O(\log N)$)。

注: 有重复大量元素的数组,可以通过三向切分快速排序, 将平均时间复杂度降低到 $O(N)$

比较类排序算法

因为非比较排序有其局限性,所以它们并不常用。本文将要介绍的 7 种算法都是比较类排序。

选择排序

原理:遍历数组, 从中选择最小元素,将它与数组的第一个元素交换位置。继续从数组剩下的元素中选择出最小的元素,将它与数组的第二个元素交换位置。循环以上过程,直到将整个数组排序。

时间复杂度分析:$O(N^{2})$。选择排序大约需要 $N^{2}/2$ 次比较和 $N$ 次交换,它的运行时间与输入无关,这个特点使得它对一个已经排序的数组也需要很多的比较和交换操作。

selection_sort

实现

// 选择排序 (selection sort)
package sorts

func SelectionSort(arr []int) []int {

    for i := 0; i < len(arr); i++ {
        min := i
        for j := i + 1; j < len(arr); j++ {
            if arr[j] < arr[min] {
                min = j
            }
        }

        tmp := arr[i]
        arr[i] = arr[min]
        arr[min] = tmp
    }
    return arr
}

冒泡排序

原理:遍历数组,比较并将大的元素与下一个元素交换位置, 在一轮的循环之后,可以让未排序i的最大元素排列到数组右侧。在一轮循环中,如果没有发生元素位置交换,那么说明数组已经是有序的,此时退出排序。

时间复杂度分析: $O(N^{2})$

buble_sort

实现:

// 冒泡排序 (bubble sort)
package sorts

func bubbleSort(arr []int) []int {
    swapped := true
    for swapped {
        swapped = false
        for i := 0; i < len(arr)-1; i++ {
            if arr[i+1] < arr[i] {
                arr[i+1], arr[i] = arr[i], arr[i+1]
                swapped = true
            }
        }
    }
    return arr
}

插入排序

原理:数组先看成两部分,排序序列和未排序序列。排序序列从第一个元素开始,该元素可以认为已经被排序。遍历数组, 每次将扫描到的元素与之前的元素相比较,插入到有序序列的适当位置。

时间复杂度分析:插入排序的时间复杂度取决于数组的排序序列,如果数组已经部分有序了,那么未排序元素较少,需要的插入次数也就较少,时间复杂度较低。

  • 平均情况下插入排序需要 $N^{2}/4$ 次比较以及 $N^{2}/4$ 次交换;
  • 最坏的情况下需要 $N^{2}/2$ 比较以及 $N^{2}/2$ 次交换,最坏的情况是数组都是未排序序列(倒序)的;
  • 最好的情况下需要 $ N-1$ 次比较和 0 次交换,最好的情况就是数组已经是排序序列。

insertion_sort

实现

// 插入排序 (insertion sort)
package sorts

func InsertionSort(arr []int) []int {
    for currentIndex := 1; currentIndex < len(arr); currentIndex++ {
        temporary := arr[currentIndex]
        iterator := currentIndex
        for ; iterator > 0 && arr[iterator-1] >= temporary; iterator-- {
            arr[iterator] = arr[iterator-1]
        }
        arr[iterator] = temporary
    }
    return arr
}

希尔排序

原理:希尔排序,也称递减增量排序算法,实质是插入排序的优化(分组插入排序)。对于大规模的数组,插入排序很慢,因为它只能交换相邻的元素位置,每次只能将未排序序列数量减少 1。希尔排序的出现就是为了解决插入排序的这种局限性,通过交换不相邻的元素位置,使每次可以将未排序序列的减少数量变多。

希尔排序使用插入排序对间隔 d 的序列进行排序。通过不断减小 d,最后令 d=1,就可以使得整个数组是有序的。

时间复杂度:$O(dN*M)$, M 表示已排序序列长度,d 表示间隔, 即 N 的若干倍乘于递增序列的长度

shell_sort

实现

// 希尔排序 (shell sort)
package sorts

func ShellSort(arr []int) []int {
    for d := int(len(arr) / 2); d > 0; d /= 2 { 
        for i := d; i < len(arr); i++ {
            for j := i; j >= d && arr[j-d] > arr[j]; j -= d {
                arr[j], arr[j-d] = arr[j-d], arr[j]
            }
        }
    }
    return arr
}

归并排序

原理: 将数组分成两个子数组, 分别进行排序,然后再将它们归并起来(自上而下)。

具体算法描述:先考虑合并两个有序数组,基本思路是比较两个数组的最前面的数,谁小就先取谁,取了后相应的指针就往后移一位。然后再比较,直至一个数组为空,最后把另一个数组的剩余部分复制过来即可。

再考虑递归分解,基本思路是将数组分解成leftright,如果这两个数组内部数据是有序的,那么就可以用上面合并数组的方法将这两个数组合并排序。如何让这两个数组内部是有序的?可以二分,直至分解出的小组只含有一个元素时为止,此时认为该小组内部已有序。然后合并排序相邻二个小组即可。

归并算法是分治法 的一个典型应用, 所以它有两种实现方法:

  1. 自上而下的递归: 每次将数组对半分成两个子数组再归并(分治)
  2. 自下而上的迭代:先归并子数组,然后成对归并得到的子数组

时间复杂度分析: $O(N\log N)$

merge_sort

实现

// 归并排序 (merge sort)
package sorts

func merge(a []int, b []int) []int {

    var r = make([]int, len(a)+len(b))
    var i = 0
    var j = 0

    for i < len(a) && j < len(b) {

        if a[i] <= b[j] {
            r[i+j] = a[i]
            i++
        } else {
            r[i+j] = b[j]
            j++
        }

    }

    for i < len(a) {
        r[i+j] = a[i]
        i++
    }
    for j < len(b) {
        r[i+j] = b[j]
        j++
    }

    return r

}

// Mergesort 合并两个数组
func Mergesort(items []int) []int {

    if len(items) < 2 {
        return items

    }

    var middle = len(items) / 2
    var a = Mergesort(items[:middle])
    var b = Mergesort(items[middle:])
    return merge(a, b)

}

快速排序

原理:快速排序也是分治法的一个应用,先随机拿到一个基准 pivot,通过一趟排序将数组分成两个独立的数组,左子数组小于或等于 pivot,右子数组大于等于 pivot。 然后可在对这两个子数组递归继续以上排序,最后使整个数组有序。

具体算法描述

  1. 从数组中挑选一个切分元素,称为“基准” (pivot)
  2. 排序数组,把所有比基准值小的元素排到基准前面,所有比基准值大的元素排到基准后面(相同元素不对位置做要求)。这个排序完成后,基准就排在数组的中间位置。这个排序过程称为“分区” (partition)
  3. 递归地把小于基准值元素的子数组和大于基准值的子数组排序

空间复杂度分析:快速排序是原地排序,不需要辅助数据,但是递归调用需要辅助栈,最好情况下是递归 $\log 2N$ 次,所以空间复杂度为 $O(\log 2N)$,最坏情况下是递归 $N-1$次,所以空间复杂度是 $O(N)$。

时间复杂度分析

  • 最好的情况是每次基准都正好将数组对半分,这样递归调用最少,时间复杂度为 $O(N \log N)$
  • 最坏的情况是每次分区过程,基准都是从最小元素开始,对应时间复杂度为 $O(N^{^{2}})$

算法改进

  1. 分区过程中更合理地选择基准(pivot)。直接选择分区的第一个或最后一个元素做 pivot 是不合适的,对于已经排好序,或者接近排好序的情况,会进入最差情况,时间复杂度为 $O(N^{2})$
  2. 因为快速排序在小数组中也会递归调用自己,对于小数组,插入排序比快速排序的性能更好,因此在小数组中可以切换到插入排序
  3. 更快地分区(三向切分快速排序):对于有大量重复元素的数组,可以将数组切分为三部分,分别对应小于 pivot、等于 pivot 和大于 pivot 切分元素

quick_sort

实现

// 三向切分快速排序 (quick sort)
package sorts

import (
    "math/rand"
)

func QuickSort(arr []int) []int {

    if len(arr) <= 1 {
        return arr
    }

    pivot := arr[rand.Intn(len(arr))]

    lowPart := make([]int, 0, len(arr))
    highPart := make([]int, 0, len(arr))
    middlePart := make([]int, 0, len(arr))

    for _, item := range arr {
        switch {
        case item < pivot:
            lowPart = append(lowPart, item)
        case item == pivot:
            middlePart = append(middlePart, item)
        case item > pivot:
            highPart = append(highPart, item)
        }
    }

    lowPart = QuickSort(lowPart)
    highPart = QuickSort(highPart)

    lowPart = append(lowPart, middlePart...)
    lowPart = append(lowPart, highPart...)

    return lowPart
}

堆排序

原理:堆排序是利用“堆积”(heap)这种数据结构的一种排序算法。因为堆是一个近似完全二叉树结构,满足子节点的键值或索引小于(或大于)它的父节点。

具体算法描述

  1. 将待排序数组构建成大根堆,这个堆为初始的无序区
  2. 将堆顶元素 $R_{1}$ 与最后一个元素 $R_{n}$ 交换,此时得到新的无序区($R_{1},R_{2},...R_{n-1}$)和新的有序区($R_{n}$),并且满足 $R_{1,2,...n-1}<= R_{n}$
  3. 由于交换后新的堆顶 $R_{1}$可能违反堆的性质,需要对当前无序区调整为新堆,然后再次将 $R_{1}$与无序区最后一个元素交换,得到新的无序区 $R_{1},R_{2}...R_{n-2}$ 和新的有序区$R_{n-1},R_{n}$。不断重复此过程直到有序区的元素个数为$n-1$,则整个排序过程完成

时间复杂度分析:一个堆的高度为 $\log N$,因此在堆中插入元素和删除最大元素的时间复杂度为 $O(\log N)$。堆排序会对 N 个节点进行下沉操作,因为时间复杂度为 $O(N \log N)$

heap_sort

实现

// 堆排序 (heap sort)
package sorts

type maxHeap struct {
    slice    []int
    heapSize int
}

func buildMaxHeap(slice []int) maxHeap {
    h := maxHeap{slice: slice, heapSize: len(slice)}
    for i := len(slice) / 2; i >= 0; i-- {
        h.MaxHeapify(i)
    }
    return h
}

func (h maxHeap) MaxHeapify(i int) {
    l, r := 2*i+1, 2*i+2
    max := i

    if l < h.size() && h.slice[l] > h.slice[max] {
        max = l
    }
    if r < h.size() && h.slice[r] > h.slice[max] {
        max = r
    }
    if max != i {
        h.slice[i], h.slice[max] = h.slice[max], h.slice[i]
        h.MaxHeapify(max)
    }
}

func (h maxHeap) size() int { return h.heapSize } 

func HeapSort(slice []int) []int {
    h := buildMaxHeap(slice)
    for i := len(h.slice) - 1; i >= 1; i-- {
        h.slice[0], h.slice[i] = h.slice[i], h.slice[0]
        h.heapSize--
        h.MaxHeapify(0)
    }
    return h.slice
}

算法复杂度比较

下面是各排序算法的复杂度和稳定性比较:

排序算法时间复杂度(平均)时间复杂度(最好)时间复杂度(最坏)空间复杂度稳定性备注
选择排序$O(N^{2})$$O(N^{2})$$O(N^{2})$$O(1)$不稳定
冒泡排序$O(N^{2})$$O(N)$$O(N^{2})$$O(1)$稳定
插入排序$O(N^{2})$$O(N)$$O(N^{2})$$O(1)$稳定时间复杂度和初始顺序有关
希尔排序$O(N^{1.3})$$O(N)$$O(N^{2})$$O(1)$不稳定改进版插入排序
归并排序$O(N \log N)$$O(N \log N)$$O(N \log N)$$O(N)$稳定
快速排序$O(N \log N)$$O(N \log N)$$O(N^{2})$$O(N \log N)$不稳定
堆排序$O(N \log N)$$O(N \log N)$$O(N \log N)$$O(1)$不稳定无法利用局部性原理

注:

  • 稳定:如果 a 原本在 b 前面,而 a=b,排序之后 a 仍然在 b 的前面。
  • 不稳定:如果 a 原本在 b 的前面,而 a=b,排序之后 a 可能会出现在 b 的后面。

对比这里排序的时间复杂度,归并排序、快速排序和堆排序的平均时间复杂度都是 $O(N \log N)$。但是再比较最坏的情况, 可以看到堆排序的下界也是 $O(N \log N)$,而快排最坏的时间复杂度是 $O(N^{2})$。 你可能会问,按分析结果来说,堆排序应该是实际使用的更好选择,但为什么业界的排序实现更多是快速排序?

实际上在算法分析中,大 $O$ 的作用是给出一个规模的下界,而不是增长数量的下界。因此,算法复杂度一样只是说明随着数据量的增加,算法时间代价增长的趋势相同,并不是执行的时间就一样,这里面有很多常量参数的差别,比如在公式里各个排序算法的前面都省略了一个$c$,这个$c$ 对于堆排序来说是100,可能对于快速排序来说就是10,但因为是常数级所以不影响大 $O$。

这里有一份平均排序时间的 Benchmark 测试数据(数据集是随机整数,时间单位 s):

数据规模快速排序归并排序希尔排序堆排序
1000 w0.751.221.773.57
5000 w3.786.299.4826.54
1亿7.6513.0618.7961.31

因为堆排序每次取一个最大值和堆底部的数据交换,重新筛选堆,把堆顶的X调整到位,有很大可能是依旧调整到堆的底部(堆的底部X显然是比较小的数,才会在底部),然后再次和堆顶最大值交换,再调整下来,可以说堆排序做了许多无用功。

总结起来就是,快排的最坏时间虽然复杂度高,但是在统计意义上,这种数据出现的概率极小,而堆排序过程里的交换跟快排过程里的交换虽然都是常量时间,但是常量时间差很多。

Go 标准库排序源码分析

梳理完最常用的7种排序算法后,我们继续来看下 Go 在标准库里是怎么做的排序实现。

标准库的 sort 包的目录树如下(以 Go 1.15.5为例):

$ tree . 
.
├── example_interface_test.go // 提供对 []struct 排序的 example
├── example_keys_test.go // 根据 struct 里对某一字段的自定义比较,来对 []struct 排序的 example 
├── example_multi_test.go // 根据用户定义好的 less 方法做排序的 example
├── example_search_test.go // sort.Search 提供对排序数组二分查找某一元素的 example
├── example_test.go // 基本的各种数组排序的 example
├── example_wrapper_test.go // 对 sort.Interface 接口的实现 (封装),排序的 example
├── export_test.go
├── genzfunc.go
├── search.go // 二分查找的实现
├── search_test.go
├── slice.go
├── slice_go113.go
├── slice_go14.go
├── slice_go18.go
├── sort.go // 主要代码,提供对 slice 和自定义集合的排序实现
├── sort_test.go
└── zfuncversion.go

其中带有 example_* 前缀的文件是 sort 包的示例代码,有官方 example 来说明排序的使用方法。很有必要看一遍,可以理解 sort 包怎么使用,和在一些相对复杂场景下如何排序。

排序的主要代码在 sort.go 这个文件里。实现的排序算法有: 插入排序(insertionSort)、堆排序(heapSort)、快速排序(quickSort)、希尔排序(ShellSort)和归并排序(SymMerge)。

sort 包根据稳定性,将排序方法分为两类:不稳定排序和稳定排序

不稳定排序

不稳定排序入口函数是 Sort(data interface),为支持任意元素类型的 slice 的排序,sort 包定义了一个 Interface 接口和接受该接口参数类型的 Sort 函数:

// A type, typically a collection, that satisfies sort.Interface can be
// sorted by the routines in this package. The methods require that the
// elements of the collection be enumerated by an integer index.
type Interface interface {
    // Len is the number of elements in the collection.
    Len() int
    // Less reports whether the element with
    // index i should sort before the element with index j.
    Less(i, j int) bool
    // Swap swaps the elements with indexes i and j.
    Swap(i, j int)
}

// Sort sorts data.
// It makes one call to data.Len to determine n, and O(n*log(n)) calls to
// data.Less and data.Swap. The sort is not guaranteed to be stable.
func Sort(data Interface) {
    n := data.Len()
    quickSort(data, 0, n, maxDepth(n))
}

只要排序数组的元素类型实现了 sort.Interface , 就可以通过 sort.Sort(data)进行排序。其中 maxDepth(n) 是快排递归的最大深度,也是快排切换堆排的阈值,它的实现:

// maxDepth returns a threshold at which quicksort should switch
// to heapsort. It returns 2*ceil(lg(n+1)).
func maxDepth(n int) int {
    var depth int
    for i := n; i > 0; i >>= 1 {
        depth++
    }
    return depth * 2
}

需要注意的一点是, sort.Sort 调用的 quickSort 排序函数,并不是最常见的快排(参考本文 3.6 小节), quickSort的整体框架比较复杂,流程如下:

func quickSort(data Interface, a, b, maxDepth int) {
    // a是第一个索引,b 是最后一个索引。如果 slice 长度大于 12,会一周走下面排序循环
    for b-a > 12 {
        // 如果递归到了最大深度, 就使用堆排序
        if maxDepth == 0 {
            heapSort(data, a, b)
            return
        }
        // 循环一次, 最大深度 -1, 相当于又深入(递归)了一层
        maxDepth--
        // 这是使用的是 三向切分快速排序,通过 doPivot 进行快排的分区
        // doPivot 的实现比较复杂,a 是数据集的左边, b 是数据集的右边,
        // 它取一点为轴,把不大于中位数的元素放左边,大于轴的元素放右边,
        // 返回小于中位数部分数据的最后一个下标,以及大于轴部分数据的第一个下标。
        // 下标位置 a...mlo,pivot,mhi...b
        // data[a...mlo] <= data[pivot]
        // data[mhi...b] > data[pivot]
        mlo, mhi := doPivot(data, a, b)
        // 避免较大规模的子问题递归调用,保证栈深度最大为 maxDepth
        // 解释:因为循环肯定比递归调用节省时间,但是两个子问题只能一个进行循环,另一个只能用递归。这里是把较小规模的子问题进行递归,较大规模子问题进行循环。
        if mlo-a < b-mhi {
            quickSort(data, a, mlo, maxDepth)
            a = mhi // i.e., quickSort(data, mhi, b)
        } else {
            quickSort(data, mhi, b, maxDepth)
            b = mlo // i.e., quickSort(data, a, mlo)
        }
    }

    // 如果元素的个数小于 12 个(无论是递归的还是首次进入), 就先使用希尔排序,间隔 d=6
    if b-a > 1 {
        // Do ShellSort pass with gap 6
        // It could be written in this simplified form cause b-a <= 12
        for i := a + 6; i < b; i++ {
            if data.Less(i, i-6) {
                data.Swap(i, i-6)
            }
        }
        insertionSort(data, a, b)
    }
}

这里 insertionSort 的和3.3节实现的插排的实现是一样的; heapSort 这里是构建最大堆,通过 siftDown 来对 heap 进行调整,维护堆的性质:

// siftDown implements the heap property on data[lo, hi).
// first is an offset into the array where the root of the heap lies.
func siftDown(data Interface, lo, hi, first int) {
    root := lo
    for {
        child := 2*root + 1
        if child >= hi {
            break
        }
        if child+1 < hi && data.Less(first+child, first+child+1) {
            child++
        }
        if !data.Less(first+root, first+child) {
            return
        }
        data.Swap(first+root, first+child)
        root = child
    }
}

func heapSort(data Interface, a, b int) {
    first := a
    lo := 0
    hi := b - a

    // Build heap with greatest element at top.
    for i := (hi - 1) / 2; i >= 0; i-- {
        siftDown(data, i, hi, first)
    }

    // Pop elements, largest first, into end of data.
    for i := hi - 1; i >= 0; i-- {
        data.Swap(first, first+i)
        siftDown(data, lo, i, first)
    }
}

在上面快速排序的原理我们有提到过:如果每次分区过程,基准(pivot)都是从最小元素开始,那么对应时间复杂度为$O(N^{^{2}})$ , 这是快排最差的排序场景。为避免这种情况,quickSort 里的 doPivot 选取了两个基准,进行三向切分,提高快速排序的效率:doPivot 在切分之前,先使用 medianOfThree 函数选择一个肯定不是最大和最小的值作为轴,放在了切片首位。然后把不小于 data[pivot] 的数据放在了 $[lo, b)$ 区间,把大于 data[pivot] 的数据放在了 $(c, hi-1]$ 区间(其中 data[hi-1] >= data[pivot])。即 slice 会被切分成三个区间:

$$ \left\{\begin{matrix} data[lo, b-1) \\ data[b-1, c) \\ data[c, hi) \end{matrix}\right.$$

doPivot的实现如下:

// Quicksort, loosely following Bentley and McIlroy,
// ``Engineering a Sort Function,'' SP&E November 1993.

// medianOfThree moves the median of the three values data[m0], data[m1], data[m2] into data[m1].
func medianOfThree(data Interface, m1, m0, m2 int) {
    // sort 3 elements
    if data.Less(m1, m0) {
        data.Swap(m1, m0)
    }
    // data[m0] <= data[m1]
    if data.Less(m2, m1) {
        data.Swap(m2, m1)
        // data[m0] <= data[m2] && data[m1] < data[m2]
        if data.Less(m1, m0) {
            data.Swap(m1, m0)
        }
    }
    // now data[m0] <= data[m1] <= data[m2]
}

func doPivot(data Interface, lo, hi int) (midlo, midhi int) {
    m := int(uint(lo+hi) >> 1) // Written like this to avoid integer overflow.
    if hi-lo > 40 {
        // Tukey's ``Ninther,'' median of three medians of three.
        s := (hi - lo) / 8
        medianOfThree(data, lo, lo+s, lo+2*s)
        medianOfThree(data, m, m-s, m+s)
        medianOfThree(data, hi-1, hi-1-s, hi-1-2*s)
    }
    medianOfThree(data, lo, m, hi-1)

    // Invariants are:
    //    data[lo] = pivot (set up by ChoosePivot)
    //    data[lo < i < a] < pivot
    //    data[a <= i < b] <= pivot
    //    data[b <= i < c] unexamined
    //    data[c <= i < hi-1] > pivot
    //    data[hi-1] >= pivot
    pivot := lo
    a, c := lo+1, hi-1

    for ; a < c && data.Less(a, pivot); a++ {
    }
    b := a
    for {
        for ; b < c && !data.Less(pivot, b); b++ { // data[b] <= pivot
        }
        for ; b < c && data.Less(pivot, c-1); c-- { // data[c-1] > pivot
        }
        if b >= c {
            break
        }
        // data[b] > pivot; data[c-1] <= pivot
        data.Swap(b, c-1)
        b++
        c--
    }
    // If hi-c<3 then there are duplicates (by property of median of nine).
    // Let's be a bit more conservative, and set border to 5.
    protect := hi-c < 5
    if !protect && hi-c < (hi-lo)/4 {
        // Lets test some points for equality to pivot
        dups := 0
        if !data.Less(pivot, hi-1) { // data[hi-1] = pivot
            data.Swap(c, hi-1)
            c++
            dups++
        }
        if !data.Less(b-1, pivot) { // data[b-1] = pivot
            b--
            dups++
        }
        // m-lo = (hi-lo)/2 > 6
        // b-lo > (hi-lo)*3/4-1 > 8
        // ==> m < b ==> data[m] <= pivot
        if !data.Less(m, pivot) { // data[m] = pivot
            data.Swap(m, b-1)
            b--
            dups++
        }
        // if at least 2 points are equal to pivot, assume skewed distribution
        protect = dups > 1
    }
    if protect {
        // Protect against a lot of duplicates
        // Add invariant:
        //    data[a <= i < b] unexamined
        //    data[b <= i < c] = pivot
        for {
            for ; a < b && !data.Less(b-1, pivot); b-- { // data[b] == pivot
            }
            for ; a < b && data.Less(a, pivot); a++ { // data[a] < pivot
            }
            if a >= b {
                break
            }
            // data[a] == pivot; data[b-1] < pivot
            data.Swap(a, b-1)
            a++
            b--
        }
    }
    // Swap pivot into middle
    data.Swap(pivot, b-1)
    return b - 1, c
}

稳定排序

sort 包中使用的稳定排序算法为 symMerge, 这里用到的归并排序算法是一种原址排序算法:首先,它把 slice 按照每 blockSize=20 个元素为一个 slice,进行插排;循环合并相邻的两个 block,每次循环 blockSize 扩大二倍,直到 blockSize > n 为止。

func Stable(data Interface) {
    stable(data, data.Len())
}

func stable(data Interface, n int) {
    blockSize := 20 // 初始 blockSize 设置为 20
    a, b := 0, blockSize
    // 对每个块(以及剩余不足blockSize的一个块)进行查询排序
    for b <= n {
        insertionSort(data, a, b)
        a = b
        b += blockSize
    }
    insertionSort(data, a, n)

    for blockSize < n {
        a, b = 0, 2*blockSize
        // 每两个 blockSize 进行合并
        for b <= n {
            symMerge(data, a, a+blockSize, b)
            a = b
            b += 2 * blockSize
        }
        // 剩余一个多 blockSize 进行合并
        if m := a + blockSize; m < n {
            symMerge(data, a, m, n)
        }
        blockSize *= 2
    }
}

// SymMerge merges the two sorted subsequences data[a:m] and data[m:b] using
// the SymMerge algorithm from Pok-Son Kim and Arne Kutzner, "Stable Minimum
// Storage Merging by Symmetric Comparisons", in Susanne Albers and Tomasz
// Radzik, editors, Algorithms - ESA 2004, volume 3221 of Lecture Notes in
// Computer Science, pages 714-723. Springer, 2004.
//
// Let M = m-a and N = b-n. Wolog M < N.
// The recursion depth is bound by ceil(log(N+M)).
// The algorithm needs O(M*log(N/M + 1)) calls to data.Less.
// The algorithm needs O((M+N)*log(M)) calls to data.Swap.
//
// The paper gives O((M+N)*log(M)) as the number of assignments assuming a
// rotation algorithm which uses O(M+N+gcd(M+N)) assignments. The argumentation
// in the paper carries through for Swap operations, especially as the block
// swapping rotate uses only O(M+N) Swaps.
//
// symMerge assumes non-degenerate arguments: a < m && m < b.
// Having the caller check this condition eliminates many leaf recursion calls,
// which improves performance.
func symMerge(data Interface, a, m, b int) {
    // Avoid unnecessary recursions of symMerge
    // by direct insertion of data[a] into data[m:b]
    // if data[a:m] only contains one element.
    if m-a == 1 {
        // Use binary search to find the lowest index i
        // such that data[i] >= data[a] for m <= i < b.
        // Exit the search loop with i == b in case no such index exists.
        i := m
        j := b
        for i < j {
            h := int(uint(i+j) >> 1)
            if data.Less(h, a) {
                i = h + 1
            } else {
                j = h
            }
        }
        // Swap values until data[a] reaches the position before i.
        for k := a; k < i-1; k++ {
            data.Swap(k, k+1)
        }
        return
    }

    // Avoid unnecessary recursions of symMerge
    // by direct insertion of data[m] into data[a:m]
    // if data[m:b] only contains one element.
    if b-m == 1 {
        // Use binary search to find the lowest index i
        // such that data[i] > data[m] for a <= i < m.
        // Exit the search loop with i == m in case no such index exists.
        i := a
        j := m
        for i < j {
            h := int(uint(i+j) >> 1)
            if !data.Less(m, h) {
                i = h + 1
            } else {
                j = h
            }
        }
        // Swap values until data[m] reaches the position i.
        for k := m; k > i; k-- {
            data.Swap(k, k-1)
        }
        return
    }

    mid := int(uint(a+b) >> 1)
    n := mid + m
    var start, r int
    if m > mid {
        start = n - b
        r = mid
    } else {
        start = a
        r = m
    }
    p := n - 1

    for start < r {
        c := int(uint(start+r) >> 1)
        if !data.Less(p-c, c) {
            start = c + 1
        } else {
            r = c
        }
    }

    end := n - start
    if start < m && m < end {
        rotate(data, start, m, end)
    }
    if a < start && start < mid {
        symMerge(data, a, start, mid)
    }
    if mid < end && end < b {
        symMerge(data, mid, end, b)
    }
}

// Rotate two consecutive blocks u = data[a:m] and v = data[m:b] in data:
// Data of the form 'x u v y' is changed to 'x v u y'.
// Rotate performs at most b-a many calls to data.Swap.
// Rotate assumes non-degenerate arguments: a < m && m < b.
func rotate(data Interface, a, m, b int) {
    i := m - a
    j := b - m

    for i != j {
        if i > j {
            swapRange(data, m-i, m, j)
            i -= j
        } else {
            swapRange(data, m-i, m+j-i, i)
            j -= i
        }
    }
    // i == j
    swapRange(data, m-i, m, i)
}

以上是稳定排序方法 Stable的全部代码。

排序 example

为应用 sort 包里排序函数 Sort不稳定排序),我们需要让被排序的 slice 类型实现 sort.Interface接口,以整形切片为例:

type IntSlice []int

func (p IntSlice) Len() int  { return len(p) }
func (p IntSlice) Less(i, j int) bool { return p[i] < p[j] }
func (p IntSlice) Swap(i, j int) { p[i], p[j] = p[j], p[i] }

func main() {
 sl := IntSlice([]int{89, 14, 8, 9, 17, 56, 95, 3})
 fmt.Println(sl) // [89 14 8 9 17 56 95 3]
 sort.Sort(sl)
 fmt.Println(sl) // [3 8 9 14 17 56 89 95]
}

总结

本文主要详细介绍了我们常见的7种排序算法的原理,实现和时间复杂度分析,并阅读 Go 源码里 sort 包的实现,分析官方如何通过将以上排序算法进行组合来提高排序性能,完成生产环境的排序实践。

参考

查看原文

赞 18 收藏 10 评论 0

tim_xiao 发布了文章 · 3月18日

redis入门教程2-常用命令

查看redis相关信息

INFO [section]

# 直接输入info将返回当前redis所有相关信息
127.0.0.1:6379> info

当只需要显示其中部分信息的时候,info后面加对应需要查看的信息。例如需要查看redis客户端信息使用 info clients

127.0.0.1:6379> info clients
# Clients
connected_clients:1
client_longest_output_list:0
client_biggest_input_buf:0
# keyspace 提供每个数据库的主字典统计,包括key总数,过期key总数
127.0.0.1:6379> info keyspace
# Keyspace
db0:keys=8,expires=0,avg_ttl=0
db3:keys=2,expires=0,avg_ttl=0

参考:

连接相关

AUTH

为redis服务请求设置一个密码

SELECT index

切换数据库,下标从0开始

127.0.0.1:6379> select 2
(error) NOAUTH Authentication required.
127.0.0.1:6379> auth 123456
OK
# 通过select命令切换数据库
127.0.0.1:6379> select 1
OK
127.0.0.1:6379[1]> get 111
(nil)

参考:

客户端相关

CLIENT LIST

返回所有客户端数据

127.0.0.1:6379[1]> CLIENT LIST
id=19 addr=127.0.0.1:33639 fd=8 name= age=593 idle=0 flags=N db=1 sub=0 psub=0 multi=-1 qbuf=0 qbuf-free=32768 obl=0 oll=0 omem=0 events=r cmd=client

参考: http://redis.cn/commands/clie...

CONFIG GET parameter
CONFIG SET parameter value

用户在运行期间设置和读取配置。通过CONFIG GET *可以查看所有可设置的配置

参考

CLIENT KILL kill链接

具体信息查看文档即可

key相关

列出当前库下所有key 查看具体key的过期时间

# 生产环境谨慎使用
127.0.0.1:6379[2]> keys *
1) "phpredis"
# -1表示永久有效 
127.0.0.1:6379[2]> ttl phpredis
(integer) -1
# -2 表示不存在或者已过期
127.0.0.1:6379[2]> ttl phpredis2
(integer) -2

参考:

关于redis的三种模式

  • standalone 单机模式
  • Sentinel 哨兵模式
  • cluster 集群模式
查看原文

赞 0 收藏 0 评论 0

tim_xiao 回答了问题 · 3月14日

把大量key通过hash算法映射到两台服务器,问题来了,如何保证数据均匀分布?

有很多hash均匀分布的算法,但是都是相对的均匀分布

关注 4 回答 3

tim_xiao 发布了文章 · 3月14日

redis入门教程1-基础数据结构

redis是基于C语言开发的一个开源非关系型内存数据库(key/value型数据库)

特点

  • 支持数据持久化
  • 存储结构支持多种数据结构 String list Set ZSet Hash
  • 支持数据备份 master-slave 模式数据备份

优势

  • 高性能
  • 丰富的数据结构
  • 原子性,支持事务
  • 丰富的特性 (publish/subscribe, 通知, key 过期)

应用

缓存,数据库,消息中间件等

安装并启动

如下图所示
安装.png

客户端

redis-cli

使用 redis-cli -h 查看帮助信息

参考网站


数据结构-Strings 字符串类型

redis中最基本的数据类型,一个key对应一个value

二进制安全 可以包含 数字 字符串 图片 序列化对象等

string类型可以用来存储缓存,session,计数器(redis单线程模式,一个命令执行完 后才会执行下一个命令)等

常用命令 set get del

127.0.0.1:6379> set name 123
OK
127.0.0.1:6379> get name
"123"
127.0.0.1:6379> del name
(integer) 1
127.0.0.1:6379> get name
(nil)

INCR(递增1) INCRBY(递增一个范围) DECR(递减1) DECRBY(递减一个范围)

127.0.0.1:6379> get counter
(nil)
127.0.0.1:6379> INCR conter
(integer) 1
127.0.0.1:6379> INCR conter
(integer) 2
127.0.0.1:6379> INCR conter
(integer) 3
127.0.0.1:6379> INCR conter
(integer) 4
127.0.0.1:6379> get conter
"4"
127.0.0.1:6379> INCRBY conter 10
(integer) 14
127.0.0.1:6379> get counter
(nil)
127.0.0.1:6379> get couter
(nil)
127.0.0.1:6379> get conter
"14"
127.0.0.1:6379> DECR conter
(integer) 13
127.0.0.1:6379> DECRBY Conter 3
(integer) -3
127.0.0.1:6379> DECRBY conter 3
(integer) 10

参考:http://redis.cn/commands.html...

ps:命令不区分大小写,key区分大小写

数据结构-Lists 列表类型

双向链表,左右都可以插入和 删除数据

一个列表最多可以包含2^32-1个元素(约40亿个元素)

常用命令:lpush+lpop(栈stack)

127.0.0.1:6379> lpush mylist php
(integer) 1
127.0.0.1:6379> lpush mylist java
(integer) 2
127.0.0.1:6379> lpush mylist golang
(integer) 3
127.0.0.1:6379> LRANGE 0 10
(error) ERR wrong number of arguments for 'lrange' command
127.0.0.1:6379> LRANGE mylist 0 10
1) "golang"
2) "java"
3) "php"
127.0.0.1:6379> lpop mylist
"golang"
127.0.0.1:6379> lpop mylist
"java"
127.0.0.1:6379> lpop mylist
"php"
127.0.0.1:6379> lpop mylist
(nil)

常用命令:lpush+rpop(队列queue)

127.0.0.1:6379> lpush mylist php java python golang
(integer) 4
127.0.0.1:6379> LRANGE mylist 0 10
1) "golang"
2) "python"
3) "java"
4) "php"
127.0.0.1:6379> RPOP mylist 
"php"
127.0.0.1:6379> RPOP mylist 
"java"

参考:http://redis.cn/commands.html...

数据结构-Sets 集合类型

保存多个字符串元素。集合为无序的,不能通过索引下标访问。集合不能有重复元素。在redis中,集合可以很方便的进行交集,并集,差集等操作。

应用场景:点赞数,收藏书统计。给用户打标签(一个标签一个集合)然后可以利用集合的关系分析用户行为

集合常见命令(主要以s开头)

  • sadd(向集合中插入元素)
  • smembers(返回集合中所有成员数)
  • sismember(判断是否是集合中的成员)
  • scard(返回集合中元素的个数)
127.0.0.1:6379> sadd myset hao hao1 xiaohao hao
(integer) 3
127.0.0.1:6379> SMEMBERS myset
1) "xiaohao"
2) "hao"
3) "hao1"
# 判断hao是否是集合myset中的成员
127.0.0.1:6379> SISMEMBER myset hao
(integer) 1
127.0.0.1:6379> SISMEMBER myset hao1
(integer) 1
127.0.0.1:6379> SISMEMBER myset hao2
(integer) 0
# 返回集合中元素的个数
127.0.0.1:6379> SCARD myset
(integer) 3
# 返回不存在的元素个数则返回0
127.0.0.1:6379> SCARD myset1
(integer) 0

参考:http://redis.cn/commands.html...

数据结构-Sorted sets 有序集合类型

有序集合和集合类似,都是不包含相同字符串的合集。不同的是,有序集合中的元素都关联一个评分,通过这个评分可以对集合中的元素进行排序(元素不能重复,但是分数 可以重复),默认都是按照升序进行排序

使用有序集合,你可以非常快地(O(log(N)))完成添加删除更新元素的操作。 因为元素是在插入时就排好序的,所以很快地通过评分(score)或者 位次(position)获得一个范围的元素

应用场景:排行榜

常用命令(有序集合中的命令通常以z开头)

# 添加有序集合元素
127.0.0.1:6379> zadd scoreset 100 Amy 90 Bob
(integer) 2
127.0.0.1:6379> zadd scoreset 99 Zhangsan 91 Lisi
(integer) 2
# 获取有序集合元素
127.0.0.1:6379> zcard scoreset
(integer) 4
# 获取区间范围元素个数
127.0.0.1:6379> zcount scoreset 95 100
(integer) 2
# 获取某一个元素排名
127.0.0.1:6379> zrevrank scoreset Lisi
(integer) 2
# 获取排名区间范围
127.0.0.1:6379> zrevrange scoreset 0 10
1) "Amy"
2) "Zhangsan"
3) "Lisi"
4) "Bob"

参考:http://redis.cn/commands.html...

数据结构-Hash 哈希

Mapmap类型,指值的本身又是一种键值对类型

应用场景:用来缓存一些对象信息,入用户信息,商品信息,对象信息等=,另外就是购物车等场景中使用.

哈希命令都是以h开头

127.0.0.1:6379> HSET user name1 hao
(integer) 1                                                                                    
127.0.0.1:6379> HSET user email aaaa@qq.com
(integer) 1                                                                                    
127.0.0.1:6379> HSET user age 18
(integer) 1                                                                                    
127.0.0.1:6379> HGETALL user
1) "name1"                                                                                     
2) "hao"                                                                                       
3) "email"                                                                                     
4) "aaaa@qq.com"                                                                               
5) "age"                                                                                       
6) "18"                                                                                        
127.0.0.1:6379> HGET user age
"18"     

参考:http://redis.cn/commands.html...

查看原文

赞 0 收藏 0 评论 0

认证与成就

  • 获得 4 次点赞
  • 获得 3 枚徽章 获得 0 枚金徽章, 获得 0 枚银徽章, 获得 3 枚铜徽章

擅长技能
编辑

开源项目 & 著作
编辑

(゚∀゚ )
暂时没有

注册于 2017-04-18
个人主页被 2.3k 人浏览