Redis 中快排算法详解(pqsort.c) | klion26
Redis 中的快排中的思想是一篇叫做"Engineering a Sort Function"里面的思想。做到比标准库里面的快排更快，更稳定，（在自己电脑上做测试的时候，基本一样的时间），按照论文来说主要用到下面的优化：
- 元素交换的时候更省时间
- 在某些情况下使用了冒泡排序，以及插入排序
- 选择一个接近中位数的数做 pivot
下面从上面三个方面入手分析代码
对于元素交换方面，代码里面的做法首先会查看待排序的数组是否按机器字节对齐，以及每个元素所占的字节长度是否等于机器字节长度，代码如下
Read full article from Redis 中快排算法详解(pqsort.c) | klion26
No comments:
Post a Comment