聊一聊快排算法
曾经有一个人让我写下快排算法，我给他写出来了，然后就被Diss了，怎么申请这么多临时变量。来，各位看官一起看看本菜🐔的作业。各位看官也可以动手写一写。
快速排序的逻辑 — 来自百度百科
快速排序算法通过多次比较和交换来实现排序，其排序流程如下:
(1)首先设定一个分界值，通过该分界值将数组分成左右两部分。
(2)将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。
(3)然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
(4)重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。
<?php
$input = [100, 23, 452, 234, 56223, 6234, 134, 51, 234];
$ret = quickSort($input);
printf("%s\n", json_encode($ret));
function quickSort($input)
{
$len = count($input);
if ($len <= 1) {
return $input;
}
$temp = $input[0];
$left = $right = [];
for ($i = 1; $i < $len; $i++) {
if ($temp >= $input[$i]) {
$left[] = $input[$i];
} else {
$right[] = $input[$i];
}
}
$left = quickSort($left);
$right = quickSort($right);
return array_merge($left, [$temp], $right);
}
基本上也是符合快速排序的标准，不过确实$left和$right这两个属于数组copy，会需要大量的内存空间的。但是既然说到利用了中间变量来存放数组，那么是否有别的方式呢？
答案肯定是有的了，既然不能用中间变量存数组，那么我可以使用交换的方式，因为反正都是比大小，我们通过一个临时变量将原数组的数据挖一个出来，然后再去比较，可以看下面的示例。
[100, 23, 452, 234, 56223, 6234, 134, 51, 234]
第一趟，我先取100出来，然后从右向左扫描，比他小的（51<100）放入他的坑，那么结果如下：
[---, 23, 452, 234, 56223, 6234, 134, 51, 234]
从左扫发现51，填入左边的坑。
[51, 23, 452, 234, 56223, 6234, 134, ---, 234]
然后从51的下个值往右扫，发现452>100，那么把452填入上面挖的坑
[51, 23, ---, 234, 56223, 6234, 134, 452, 234]
然后从452往左扫描，发现没有小于100的。那么100 就只能去填坑了。自此我们做了一个循环。
[51, 23, 100 234, 56223, 6234, 134, 452, 234]
那么下一个循环我们怎么开始呢？因为100的右边肯定是大于它的，100的左边肯定是小于它的。PS.这不是废话吗？上面的快排就是这样要求的。
我们就从51，到100 这三个元素之间继续排序。
[51,23,100]
[--,23,100]
[23,--,100]
[23,50,100]
最左边的完成了，那么我们来看看最右边的
[234,56223,6234, 134, 452, 234]
.... 各位看官自己实现下看看？
好了直接上代码
<?php
function quickSort(&$input, $low, $high)
{
if ($high <= $low) return;
$i = $low;
$j = $high;
$key = $input[$low];
while ($i < $j) {
while ($i < $j && $input[$j] >= $key) {
$j--;
}
if ($i < $j) {
$input[$i] = $input[$j];
$i++;
}
while ($i < $j && $input[$i] < $key) {
$i++;
}
if ($i < $j) {
$input[$j] = $input[$i];
$j--;
}
// printf("find i(%d),j(%d)\n", $i, $j);
}
$input[$i] = $key;
quickSort($input, $low, $i - 1);
quickSort($input, $i + 1, $high);
// return $input;
}
为了节省递归参数赋值，我们传了引用进去，更加节省内存空间。那么具体效果如何呢，我们来看看跟内置函数sort的对比结果。
排序个数：100000
内置排序耗时：27.215004 ms
手写排序耗时：104.742050 ms
结果抽查 1
排序个数：200000
内置排序耗时：61.784983 ms
手写排序耗时：241.871119 ms
结果抽查 1
排序个数：300000
内置排序耗时：87.085009 ms
手写排序耗时：448.505878 ms
结果抽查 1
排序个数：400000
内置排序耗时：120.175838 ms
手写排序耗时：618.201971 ms
结果抽查 1
排序个数：500000
内置排序耗时：149.783850 ms
手写排序耗时：796.765804 ms
结果抽查 1
排序个数：600000
内置排序耗时：182.029963 ms
手写排序耗时：1063.417196 ms
结果抽查 1
排序个数：700000
内置排序耗时：209.767103 ms
手写排序耗时：1333.762884 ms
结果抽查 1
排序个数：800000
内置排序耗时：241.870165 ms
手写排序耗时：1633.098841 ms
结果抽查 1
排序个数：900000
内置排序耗时：272.398949 ms
手写排序耗时：1975.782871 ms
结果抽查 1
排序个数：1000000
内置排序耗时：299.492121 ms
手写排序耗时：2303.519964 ms
结果抽查 1
可以看出虽然我们采用了传引用的方法，在大量的数据排序的时候，自己写的还是没有内置的厉害。基本上内置的算法只需要自己写的1/5的时间。
那么是否别的语言也是这样的呢？我们来看看golang吧。
排序个数： 100000
内置排序耗时： 16.072056ms
手写排序耗时： 6.95578ms
结果抽查: true
排序个数： 200000
内置排序耗时： 31.831613ms
手写排序耗时： 14.822814ms
结果抽查: true
排序个数： 300000
内置排序耗时： 46.872946ms
手写排序耗时： 24.190585ms
结果抽查: true
排序个数： 400000
内置排序耗时： 66.008501ms
手写排序耗时： 33.844555ms
结果抽查: true
排序个数： 500000
内置排序耗时： 77.824994ms
手写排序耗时： 43.05986ms
结果抽查: true
排序个数： 600000
内置排序耗时： 106.42095ms
手写排序耗时： 53.728681ms
结果抽查: true
排序个数： 700000
内置排序耗时： 117.377987ms
手写排序耗时： 65.855924ms
结果抽查: true
排序个数： 800000
内置排序耗时： 125.352682ms
手写排序耗时： 80.507389ms
结果抽查: true
排序个数： 900000
内置排序耗时： 140.563745ms
手写排序耗时： 92.550294ms
结果抽查: true
排序个数： 1000000
内置排序耗时： 162.15016ms
手写排序耗时： 100.330999ms
结果抽查: true
可以看到golang手写的居然比内置的快。100万个int排序，golang内置需要162ms，手写的居然只要100ms，php内置需要299ms，而手写居然需要2300多ms。
看来php的执行效率确实低，不过惊讶的是php内置函数排序居然只比golang慢一倍。
电脑配置
CPU：2.8 GHz 双核Intel Core i5
MEM：8 GB 1600 MHz DDR3
PHP version：7.4.2
Golang version ：go1.13.7
最后贴上golang代码
package main
import (
"fmt"
"math/rand"
"sort"
"time"
)
func quickSortCustom(nums *[]int, start int, end int) {
// 起点和终点重合的时候，退出
if start >= end {
return
}
i, j := start, end
//左节点的坑挖出来，备用
mid := (*nums)[start]
for {
// 左节点位移到跟右节点重合时退出for循环
if i >= j {
break
}
// 右节点开始向左查找，直到比基准值小
for {
if j > i && (*nums)[j] >= mid {
j--
} else {
break
}
}
// 把右节点的坑，填入左节点。现在右节点j空出来了
if i < j {
(*nums)[i] = (*nums)[j]
i++
}
// 左节点开始向右寻找，直到找到比基准值大的
for {
if j > i && (*nums)[i] < mid {
i++
} else {
break
}
}
//把左节点的值填入右节点的坑，（上面的右节点j是空的没有变过）。此时左节点i空出来了
if i < j {
(*nums)[j] = (*nums)[i]
j--
}
}
// 把最开始挖出来的坑放到新坑里面
(*nums)[i] = mid
quickSortCustom(nums, start, i-1)
quickSortCustom(nums, i+1, end)
}
type IntSlice []int
func (s IntSlice) Less(i, j int) bool { return s[i] < s[j] }
func (s IntSlice) Len() int { return len(s) }
func (s IntSlice) Swap(i, j int) { s[i], s[j] = s[j], s[i] }
func main() {
startTime := time.Now()
for i := 100000; i <= 1000000; i += 100000 {
numsIn := make(IntSlice, 0)
numsMy := make([]int, 0)
for n := 0; n < i; n++ {
//rand.Seed(int64(n))
x := rand.Intn(10000)
numsIn = append(numsIn, x)
numsMy = append(numsMy, x)
}
l := len(numsMy)
//fmt.Println("原始:", numsMy, "排序个数：", l)
fmt.Println("排序个数：", l)
// ---------------- 内置排序 开始----------------
startTime = time.Now()
sort.Ints(numsIn)
cost := time.Since(startTime)
fmt.Println("内置排序耗时：", cost)
// ---------------- 内置排序 结束----------------
// ---------------- 手写排序 开始----------------
startTime = time.Now()
quickSortCustom(&numsMy, 0, l-1)
cost = time.Since(startTime)
fmt.Println("手写排序耗时：", cost)
// ---------------- 手写排序 结束----------------
fmt.Println("结果抽查:", numsMy[l/2] == numsIn[l/2])
//fmt.Println("内置:", numsIn)
//fmt.Println("手写:", numsMy)
fmt.Println(" ")
}
//nums := []int{8081, 7887, 1847, 4059, 2081, 1318, 4425, 2540, 456, 3300}
//fmt.Println("原始的数据:", nums)
//quickSortCustom(&nums, 0, len(nums)-1)
//fmt.Println("自己排序后:", nums)
//
//nums2 := IntSlice{8081, 7887, 1847, 4059, 2081, 1318, 4425, 2540, 456, 3300}
////fmt.Println("排序前:",nums2)
//sort.Stable(nums2)
//fmt.Println("内置排序后:", nums2)
}
B站代码解读 — LRUCache
0x01. 说明
- 本文源码来源于互联网，本人保证公开部分不涉及任何公司的敏感信息，本人保证不传播任何敏感信息。
- 本文仅用于学术交流，请勿在商业用途中使用此源码，此源码并未执行任何开源授权。
0x02. 介绍
LRU全称为Least Recently Used，为内存管理算法的一种。通过淘汰最近最少使用的KEY来实现内存置换。
LRU的规则是最近调用的key排在列表的最前面。例如：set 3,set 4,set 5, 内存中key的排列应该是 543。然后get 4，内存刷新为453，再set 1，内存刷新为145。【注，排列顺序为阅读顺序，最左边为顶部】
从描述中可以看出，最近读取，最近更新的key，会排到队列的最顶部，该key之前的首尾会连接起来保持顺序。那么实现这种数据结构成为双向链表。
对于双向链表，了解数据结构的同学肯定不陌生，本着解读的目的，我们来介绍下什么是双向链表。
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。
每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。
有一点需要注意的是，队列的顶部和底部并不是相连的（LRU不是循环双向链表），所以我们需要有一个head指针，和tail指针来保存头尾信息。
对于双向链表的实现不是本文讨论的重点，在这里略过。我们重点是解读LRU的实现。
0x03. LRU Cache实现
从上面的示意图中，我们需要定义一个结构体，包含四个元素，next指针，prev指针，key和value字段。在golang中可以使用interface{}作为泛型支持。
实现如下：
type Element struct {
prev, next *Element
Key interface{}
Value interface{}
}
整个LRUCache的结构如下，head为头指针，tail为尾指针，capacity为队列长度，【为什么要指定长度，因为是内存置换，属于虚拟内存，所以肯定是要限制长度来使用的】。
cache 为字典结构存储Element元素（以我的理解其中Element.key 为冗余设计，应该是可以省略Element.key字段）。
type LRUCache struct {
cache map[interface{}]*Element
head *Element
tail *Element
capacity int
}
那么剩下的就是实现几个方法，『内存开辟』，『设置值』，『更新队列』，『删除元素』。具体实现可以看下面的源代码
package lrucache
// Element - node to store cache item
type Element struct {
prev, next *Element
Key interface{}
Value interface{}
}
// Next - fetch older element
func (e *Element) Next() *Element {
return e.next
}
// Prev - fetch newer element
func (e *Element) Prev() *Element {
return e.prev
}
// LRUCache - a data structure that is efficient to insert/fetch/delete cache items [both O(1) time complexity]
type LRUCache struct {
cache map[interface{}]*Element
head *Element
tail *Element
capacity int
}
// New - create a new lru cache object
func New(capacity int) *LRUCache {
return &LRUCache{make(map[interface{}]*Element), nil, nil, capacity}
}
// Put - put a cache item into lru cache
func (lc *LRUCache) Put(key interface{}, value interface{}) {
if e, ok := lc.cache[key]; ok {
e.Value = value
lc.refresh(e)
return
}
if lc.capacity == 0 {
return
} else if len(lc.cache) >= lc.capacity {
// evict the oldest item
delete(lc.cache, lc.tail.Key)
lc.remove(lc.tail)
}
e := &Element{nil, lc.head, key, value}
lc.cache[key] = e
if len(lc.cache) != 1 {
lc.head.prev = e
} else {
lc.tail = e
}
lc.head = e
}
// Get - get value of key from lru cache with result
func (lc *LRUCache) Get(key interface{}) (interface{}, bool) {
if e, ok := lc.cache[key]; ok {
lc.refresh(e)
return e.Value, ok
}
return nil, false
}
// Delete - delete item by key from lru cache
func (lc *LRUCache) Delete(key interface{}) {
if e, ok := lc.cache[key]; ok {
delete(lc.cache, key)
lc.remove(e)
}
}
// Range - calls f sequentially for each key and value present in the lru cache
func (lc *LRUCache) Range(f func(key, value interface{}) bool) {
for i := lc.head; i != nil; i = i.Next() {
if !f(i.Key, i.Value) {
break
}
}
}
// Update - inplace update
func (lc *LRUCache) Update(key interface{}, f func(value *interface{})) {
if e, ok := lc.cache[key]; ok {
f(&e.Value)
lc.refresh(e)
}
}
// Front - get front element of lru cache
func (lc *LRUCache) Front() *Element {
return lc.head
}
// Back - get back element of lru cache
func (lc *LRUCache) Back() *Element {
return lc.tail
}
// Len - length of lru cache
func (lc *LRUCache) Len() int {
return len(lc.cache)
}
// Capacity - capacity of lru cache
func (lc *LRUCache) Capacity() int {
return lc.capacity
}
func (lc *LRUCache) refresh(e *Element) {
if e.prev != nil {
e.prev.next = e.next
if e.next == nil {
lc.tail = e.prev
} else {
e.next.prev = e.prev
}
e.prev = nil
e.next = lc.head
lc.head.prev = e
lc.head = e
}
}
func (lc *LRUCache) remove(e *Element) {
if e.prev == nil {
lc.head = e.next
} else {
e.prev.next = e.next
}
if e.next == nil {
lc.tail = e.prev
} else {
e.next.prev = e.prev
}
}