redis源码分析1

时间:2018-08-20

redis源码分析

serverCron 都做了什么?

serverCron 是在initServer函数中,注册的时间事件aeCreateTimeEvent(server.el, 1, serverCron, NULL, NULL)设置的回调函数,每1ms执行一次该回调函数。

1. 处理看门狗调度信号[debug]
2. 更新服务器时间缓存
3. 每100ms,做一次统计量更新
4. 更新LRU时钟
5. 记录最大的内存使用,自服务器启动后
6. 记录服务器rss
7. 如果接收到SIGTERM信号, 则尝试安全退出
8. 每5秒,记录数据库的大小,使用情况,过期键
9. 执行客户端定时任务
    1. 处理超时问题
    2. 重置查询换成buffer大小
10. 执行数据库定时任务
    1. 激活过期键回收
    2. 碎片整理键
    3. 如果数据未做持久化操作,则重置大小,并重新哈希
11. 如果开启了aof重写调度,则执行aof文件重写
12. 如果有aof或者rdb在后台进行,则等待对应的退出,做相应的处理否则,立即开始rdb/aof_rewrite 
13. 冲刷aof
14. 每1秒,如果上次aof_rewrite失败,则执行
15. 异步释放客户端队列
16. 清除停止的客户端
17. 每1秒,开始定时复制
18. 每100毫秒,开始集群cluster定时
19. 每100毫秒,开始执行sentinel定时器
20. 每1秒,迁移关闭的超时socket
21. 强制bgsave
22. server.cronloops递增
23. 返回1000/server.hz

琐事

时间:2018-03-29

琐事

何为琐事

工作也快一年了,发现其实真正的工作时间,大部分是被琐事占据了。

灵魂在挣扎中煎熬。

数据结构和算法

时间:2018-02-17

数据结构

线性表

数组

1.删除数组中的指定元素

#include <iostream>
#include <vector>

using namespace std;

class Solution
{
public:
    int removeKey(vector<int> &V, int key)
    {
        int cnt = 0;
        for (int i=0; i<V.size(); i++)
        {
            if (V[i] == key)
                continue;
            V[cnt] = V[i];
            cnt++;
        }
        return cnt;
    }
};

int main()
{
    Solution s;
    vector<int> v = {1,2,1,3,2,4,5,4};

    s.removeKey(v, 3);

    for(vector<int>::iterator pos = v.begin(); pos != v.end(); pos++)
    {
        cout << *pos << endl;
    }

    return 0;
}

2.two_sum

class Solution
{
public:
    vector<int> two_sum(vector<int> &number, int target)
    {
        vector<int> ret;

        if (number.size() <= 1)
            return ret;
        map<int, int> my_map;

        for(int i=0; i<number.size(); i++)
            my_map[number[i]] = i;

        for(int i = 0; i<number.size(); i++)
        {
            int rest_val = target - number[i];
            if (my_map.find(rest_val) != my_map.end())
            {
                int index = my_map[rest_val];
                if (index == i)
                    continue;
                if (index < i)
                {
                    ret.push_back(index);
                    ret.push_back(i);
                    return ret;
                }
                else
                {
                    ret.push_back(i);
                    ret.push_back(index);
                    return ret;
                }
            }
        }
        return ret;
    }
};

链表

链表的创建

typedef struct Node
{
    int data;
    struct Node *next;
} ListNode, *LinkList;

int head_create(LinkList *L, int arr[], int cnt)
{
    *L = (LinkList)malloc(sizeof(ListNode));
    if (!*L)
        return -1;
    (*L)->next = NULL;
    int i = 0;

    while (i < cnt)
    {
        LinkList s = (LinkList)malloc(sizeof(ListNode));
        if (!s)
            return -1;
        s->data = arr[i];
        s->next = (*L)->next;
        (*L)->next = s;
        i++;
    }
    return 0;
}

int tail_create(LinkList *L, int arr[], int cnt)
{
    *L = (LinkList)malloc(sizeof(ListNode));
    if (!*L)
        return -1;
    (*L)->next = NULL;
    ListNode *s, *tmp;

    int i = 0;

    tmp = (*L);
    while (i < cnt)
    {
        s = (LinkList)malloc(sizeof(ListNode));
        if (!s)
            return -1;

        s->data = arr[i];
        tmp->next = s;
        tmp = s;
        i++;
    }
    tmp->next = NULL;

    return 0;
}

1.判断单链表中是否有环?

/*
   1. 有环
   2. 没有环
 */
int is_circle(LinkList head)
{
    if (head && head->next)
    {
        for (ListNode *slow = head, *fast = head; fast && fast->next; slow = slow->next, fast=fast->next->next)
            if (slow == fast)
                return 1;
    }
    return 0;
}

2.链表的反转

/*
返回新的链表头结点指针
 */
LinkList reverse_list(LinkList head)
{
    if (!head || !head->next)
        return NULL;

    LinkList cur, next, tmp;
    cur = head->next;
    tmp = NULL;
    / 断开连接
    head->next = NULL;

    while (cur) {
        / 记录下一个结点
        next = cur->next;
        cur->next = tmp;
        tmp = cur;
        cur = next;
    }

    head->next = tmp;
    return head;
}

3.倒数第k个结点

class Solution {
public:
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
        / 1.边界判断
        if(pListHead==NULL||k==0)
            return NULL;

        ListNode *pTail = pListHead, *pHead = pListHead;

        / 2.找到先跑的结点
        for(int i=1; i<k; ++i)
        {
            if(pHead->next!=NULL)
                pHead=pHead->next;
            else
                return NULL;
        }
        / 3.求倒数第k个结点
        while(pHead->next!=NULL)
        {
            pHead=pHead->next;
            pTail=pTail->next;
        }
        return pTail;
    }
};

4.求链表的中间的结点。

/ slow每次跑一步,fast每次跑两步

栈 和 队列

深度优先遍历DFS,宽度优先遍历BFS

  • 深度优先遍历,使用栈实现
  • 宽度优先遍历,使用堆实现

1.实现一个特殊的栈,在实现栈的基本功能的基础上,再实现返回栈中的最小元素的操作数getMin(), 设计栈可以使用现成的栈结构。

#include <iostream>
#include <stack>

using namespace std;

class Solution
{
    stack<int> data, min_val;
 public:
    void push(int x)
    {
        if ( min_val.empty() || x < min_val.top())
            min_val.push(x);
        else
            min_val.push(min_val.top());
        data.push(x);
    }

    void pop()
    {
        data.pop();
        min_val.pop();
    }

    int top()
    {
        return data.top();
    }

    int min()
    {
        return min_val.top();
    }

    int empty()
    {
        return data.empty();
    }

};

int main(void)
{
    Solution st;

    st.push(5);
    st.push(4);
    st.push(2);
    st.push(3);
    st.push(1);
    st.push(3);

    while (!st.empty()) {
        cout << st.top() << "|" << st.min()  << endl;
        st.pop();
    }

    return 0;

2.实现一个栈的逆序,但是只能用递归函数和这个栈本身的操作来实现,而自己不能申请另外的数据结构。

#include <iostream>
#include <stack>

class Solution
{
public:
    / 翻转一个栈
    void revStack(stack<int> &A)
    {
        if(A.empty())
            return;
        int res1=Get(A);
        revStack(A);
        A.push(res1);
    }

    / 获取元素
    / 递归本质就是一个栈
    / 这其实是一个双栈的问题
    int Get(stack<int> &A)
    {
        if(A.empty())
            exit(-1);

        / 拿到栈顶的元素
        int res1 = A.top();
        A.pop();

        if(A.empty())
            return res1;
        else
        {
            int res2=Get(A);
            A.push(res1);
            return res2;
        }
    }
};
  1. 二叉树的指定结点的路径

    bool specialPath(Node *pRoot,Node *pNode,vector<int> &v)
    {
    / 默认的终止条件
    if (pRoot == NULL)
        return false;
    
    / 
    v.push_back(pRoot->val);
    bool found = false;
    
    / 终止条件
    if (pRoot == pNode) {
        for (int i=0; i<v.size(); i++)
            cout << v[i] << " ";
        cout << endl;
        return true;
    }
    
    if (!found && pRoot->left)
    {
        found = specialPath(pRoot->left, pNode, v);
    }
    
    if (!found && pRoot->right)
    {
        found = specialPath(pRoot->right, pNode, v);
    }
    
    if (!found)
        v.pop_back();
    
    return found;
    }

字符串

1.KMP算法

2.最长回文子字符串(Manachers算法)

回文串:是一个正读和反读都一样的字符串,比如“level”或者“noon”等等就是回文串

3.判断两个字符串是否互为旋转词

#include <iostream>
#include <string>

class Rotation
{
public:
  bool isRotate(string A, string B)
  {
    string sum = A + A;
    string::size_type n = sum.find(B);

    / string::npos 代表-1
    if (n != string::npos)
      return true;
    else
      return false; 
  }
}

4.字符串单词翻转,例如:给定一个字符串"i love you",反转为"you love i"?

#include <stdio.h>
#include <string.h>

void str_rev(char s[], int from, int to);
void str_world_rev(char s[]);

int main(int argc, char const *argv[])
{
    char s[] = "hello world test i love picture wow";

    printf("%s\n",s);
    str_world_rev(s);
    printf("%s\n",s);

    return 0;
}

void str_rev(char s[], int from, int to)
{
    while (from < to) {
        char t = s[from];
        s[from++] = s[to];
        s[to--] = t;
    }
}

void str_world_rev(char s[])
{
    int len = strlen(s);
    str_rev(s, 0, len-1);
    int pos = 0;
    for (int i=0; i<=len; i++)
    {
        if (s[i] == ' ' || i==len) {
            str_rev(s, pos, i-1);
            pos = i+1;
        }
    }
}

5.给定一个字符串str, 和一个整数i, i代表str中的位置,将str[0..i]移动到右侧,str[i+1..N-1]移动到左侧 要求时间复杂度O(n),空间复杂度是O(1)

/* 三步反转法 */
#include <stdio.h>
#include <string.h>

void str_rev(char s[], int from, int to)
{
    while (from < to)
    {
        char t = s[from];
        s[from++] = s[to];
        s[to--] = t;
    }
}

void left_to_tail(char s[], int m)
{
    int len = strlen(s);

    m %= len;

    str_rev(s, 0, m-1);
    str_rev(s, m, len-1);
    str_rev(s, 0, len-1);
}

int main(int argc, char const *argv[])
{
    char s[] = "hello-world.";

    printf("%s\n", s);
    left_to_tail(s, 4);
    printf("%s\n", s);
    return 0;
}

6.给定一个字符串数组,请找到一种拼接顺序,使得将所有字符串拼接起来组成的大字符串是所有可能性中字典顺序最小的字符串

#include <iostream>
#include <vector>
#include <string>

using namespace std;

static bool cmp(const string &str1, const string &str2)
{
    return str1 + str2 < str2 + str1 ? true : false;
}

/**
 * 返回字符串数组中的字典序最小的拼接字符串
 * s 该字符串数组
 * n 数组元素的个数
 */
string find_smallest(vector<string> &multi_str, int n)
{
    string res = "";

    sort(multi_str.begin(), multi_str.end(), cmp);
    for(int i=0; i<n; i++) {
        res += multi_str[i];
    }
    return res;
}

int main(void)
{

    vector<string> str_arr;

    str_arr.push_back("test");
    str_arr.push_back("ce");
    str_arr.push_back("abc");
    str_arr.push_back("ba");
    str_arr.push_back("a");

    cout << "res: " << find_smallest(str_arr, 5) << endl;
    return 0;
}

字符串重点

1.合法括号序列判断题

/*
给定一个字符串,判断其是合法的括号序列
'(())()' 合法
')(())'  不合法
')))(((' 不合法
'((a))'  不合法
*/
#include <iostream>
#include <string>

using namespace std;

bool checkValidParentheses(string s)
{
    int num = 0;
    for (int i = 0; i < s.size(); ++i)
    {
        if (s[i] == '(')
            num++;
        else if (s[i] == ')')
            num--;
        else
            return false;

        if (num < 0)
            return false;
    }
    if(num==0)
        return true;
    else
        return false;
}

int main(void)
{
    string s = "()(())";

    bool res = checkValidParentheses(s);

    cout << "res " << res << endl;
    return 0;
}

2.是否互为变形词

/*
判断两个词,是否互为变形词
 */
#include <iostream>
#include <string>

using namespace std;

class Transform
{
public:
    bool is_transform(string a, string b)
    {
        if (a.size() != b.size())
            return false;

        int hs1[256] = {0}, hs2[256] = {0}, i;

        for(i=0; i<a.size(); i++)
        {
            hs1[a[i]]++;
            hs2[b[i]]++;
        }

        i = 0;

        while (i<256 && hs1[i] == hs2[i])
            i++;

        if (i>=256)
            return true;
        else
            return false;
    }
};

int main(void)
{
    string a = "helloo";
    string b = "eloloh";
    string c = "elolhh";
    string d = "hi";

    Transform ts;
    bool res1 = ts.is_transform(a,b);
    bool res2 = ts.is_transform(a,c);
    bool res3 = ts.is_transform(a,d);

    cout << "res1: " << res1 << " | res2: " << res2 << " | res3: " << res3 << endl;
}

3.一棵二叉树是否为另一棵树的拓扑子结构

#include <iostream>
#include <vector>
#include <string>

using namespace std;

struct TreeNode
{
    int data;
    struct TreeNode *left;
    struct TreeNode *right;

    TreeNode(int x) : data(x), left(NULL), right(NULL)
    {}
}

class IdenticalTree
{
public:
    bool is_identical(TreeNode * A, TreeNode * B)
    {
        string a,b;
        serialize(A, a);
        serialize(B, b);

        if (a.find(b) != string::npos)
            return true;
        else
            return false;
    }

    void serialize(TreeNode * A, string &str)
    {
        if (!A)
        {
            str += "#!";
            return;
        }
        str += intToStr(A->data);
        serialize(A->left);
        serialize(A->right);
    }

    string intToStr(int n)
    {
        if (!n)
            return "0!";
        string res;
        vector<int> tmp;

        while (n) {
            tmp.push_back(n % 10);
            n /= 10;
        }

        for (vector<int>::reverse_iterator ri = tmp.rbegin(); ri != tmp.rend(); ri++) {
            res.push_back(*ri + 48);
        }

        res.push_back('!');
        retur res;
    }
}

树

1.二叉树

遍历

  • 先序[递归和非递归<使用栈>的方法]
  • 中序
  • 后序
  • 层序[使用一个队列的方法]:本质是一个图的宽度优先遍历的一个应用。
/* 二叉树的层序遍历 */

#include <iostream>
#include <cstdlib>
#include <queue>
#include <vector>

/ 定义结点
struct TreeNode
{
  int data;
  struct TreeNode *left;
  struct TreeNode *right;

  TreeNode(int val) : data(val), left(NULL), right(NULL)
  {}
};

class Solution
{
public:
  vector< vector<int> > layerScan(TreeNode *root)
  {
    vector<vector<int>> res;
    vector<int> tmp;
    queue<TreeNode*> que;

    que.push(root);
    TreeNode *last = root, *nlast = NULL, *now = NULL;

    / 作宽度优先遍历
    while(!que.empty()) {

      now = que.front();

      cout << now->data << " ";
      tmp.push_back(now->data);

      if (now->left) {
        que.push(now->left);
        nlast = now->left;
      }
      if (now->right) {
        que.push(now->right);
        nlast = now->right;
      }
      if (now == last) {
        res.push_back(tmp);
        tmp.clear();
        cout << endl;

        last = nlast; 
      }

      que.pop();

    }
    return res; 
  }
}

二叉树的序列化和反序列化

/* cpp代码 */
#include <iostream>
#include <vector>
#include <cstdlib>
#include <queue>

using namespace std;

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;

    TreeNode(int x) : val(x), left(NULL), right(NULL)
    {}
};

vector<char>::size_type n;

class Serialize
{
public:
    void serialize(TreeNode *head, vector<char> &B)
    {
        if (!head) {
            B.push_back('#');
            B.push_back('!');
            return;
        }

        int value = head->val;

        if (!value) {
            B.push_back('0');
            B.push_back('!');
            serialize(head->left, B);
            serialize(head->right, B);
            return;
        }

        / 数字转字符表示
        int a;
        vector<int> A;
        while (value) { / 存在数字值
            a = value % 10;  / 这里是个位数先进去啊
            A.push_back(a);
            value /= 10;
        }

        while (!A.empty()) { / 数字vector不为空
            a = A.back();
            A.pop_back();
            B.push_back('0' + a);
        }
        B.push_back('!');
        serialize(head->left, B);
        serialize(head->right, B);

        return;
    }
};

class Deserialize
{
public:
    void deserialize(vector<char> A, TreeNode * &head)
    {
        vector<char>::size_type i,j;
        int value = 0;

        if (n > A.size() - 1 || A[n] == '#')
            return;

        i = j = n;

        while (A[j] != '!')
            j++;

        while (j > i) {
            value = (A[i] - '0') + value * 10;
            i++;
        }

        head = (TreeNode *) malloc(sizeof(TreeNode));
        head->val = value;

        head->right = head->left = NULL;

        n = i + 1;

        /
        deserialize(A, head->left);
        deserialize(A, head->right);
    }
};

class TreePrinter
{
public:
    vector<vector<int> > tree_print(TreeNode *root)
    {
        vector<vector<int> > res;
        vector<int> tmp;
        queue<TreeNode *> que;

        if (root == NULL)
            return vector<vector<int> >(0);

        que.push(root);
        TreeNode *last = root, *nlast = NULL, *now = NULL;

        / 如果这个队列不是空
        while (!que.empty()) {
            now = que.front();
            cout << now->val << " ";

            tmp.push_back(now->val);

            if (now->left) {

                que.push(now->left);
                nlast = now->left;
            }

            if (now->right) {
                que.push(now->right);
                nlast = now->right;
            }

            if (now == last) {

                res.push_back(tmp);
                tmp.clear();
                cout << endl;
                last = nlast;
            }
            que.pop();
        }

        return res;
    }
};

int main()
{
    int i = 0;
    char a[11] = {'1','2','!','3','!','#','!','#','!','#','!'};
    vector<char> sor(a, a + 11);

    Deserialize de;
    TreeNode *T = NULL;
    de.deserialize(sor, T);

    Serialize se;
    vector<char> res;
    se.serialize(T, res);

    for(int i=0; i!=res.size(); i++)
        cout << res[i] << " ";
    cout << endl;

    vector<vector<int> > res1;
    TreePrinter tree_ptr;
    res1 = tree_ptr.tree_print(T);

    for (vector<vector<int> >::iterator itr1 = res1.begin(); itr1 != res1.end(); ++itr1)
    {
        for (vector<int>::iterator itr2 = (*itr1).begin(); itr2 != (*itr1).end(); ++itr2)
        {
            cout << "[" << ++i << "] "<< *itr2 << " ";
        }
        cout << endl;
    }
    return 0;
}

二叉数的高度

#include <stdio.h>
#include <stdlib.h>

#define max(a,b) a>b ? a : b

typedef struct _TreeNode
{
  int data;
  struct _TreeNode *left;
  struct _TreeNode *right;
} TreeNode, *Tree;

int tree_high(Tree t)
{
  if (t == NULL)
    return 0;
  return 1 + max(tree_high(t->left), tree_high(t->right)); 
}

二叉树的宽度

翻转二叉树

2.自平衡二叉树

3.二叉查找树

4.红黑树

5.堆

6.B-,B+树

图

1.广度优先遍历

2.深度优先遍历

3.最小生成树

4.最短路径

查找

1.折半查找

int binarySearch(int arr[], int cnt, int key)
{
  int left = 0;
  int right = cnt -1;

  while (left <= right) {
    mid = (right-left)/2 + left;
    if (arr[mid] == key)
      return mid;
    else if (arr[mid] > key)
      right = mid - 1;
    else
      left = mid + 1;
  }

  return -1;
}

2.哈希表

/ 使用开放寻址法,实现一个hash表

排序

时间复杂度为O(n^2)的排序算法

1.冒泡排序

/ O(n^2)
#include <stdio.h>
#include <stdlib.h>

void bubbleSort(int arr[], int cnt)
{
  for (int i=1; i<cnt; i++)
  {
    for (int j=0; j<cnt-i; j++)
    {
      if (arr[j] > arr[j+1])
      {
        int tmp = arr[j];
        arr[j+1] = arr[j];
        arr[j] = tmp;
      }
    }
  }  
}

/*
排序算法还可以进行优化,设置一个标志域flag,如果某一趟排序发生了变换,那么flag为true。
如果某一趟排序没有发生交换,则说明序列已经有序了,不必再进行继续的比较操作,此时flag为false
 */
void bubbleSort2(int arr[], int cnt)
{
  int flag = 1;

  for (int i=1; i<cnt && flag; i++)
  {
    flag = 0;
    for (int j=0; j<cnt-1; j++)
    {
      if (arr[j] > arr[j+1])
      {
        flag = 1;
        int tmp = arr[j+1];
        arr[j+1] = arr[j];
        arr[j] = tmp;
      }
    }
  }
}

int main(void)
{
  int a[] = {5,2,1,4,3};

  for(int i = 0; i<5; i++)
    printf("%d ", a[i]);
  printf("\n");

  bubbleSort(a, 5);

  for(int i = 0; i<5; i++)
    printf("%d ", a[i]);
  printf("\n");

}

2.选择排序

/*
每次找到最小元素的位置,放入到指定的位置上,形成排序的序列
*/
void selectSort(int arr[], int cnt)
{
  for (int i=0; i<cnt; i++)
  {
    int min = i;
    for (int j=i+1; j<cnt; j++)
    {
      if (arr[j] < arr[min])
      {
        min = j;
      }
    }
    if (min != i)
    {
        int tmp = arr[i];
        arr[i] = arr[min];
        arr[min] = tmp;
    }
  }
}

3.插入排序

/* 
1. 从索引1的位置上开始遍历,并记录当前位置上的值
2. 该位置之前的为已经排好序的序列
3. 该位置上的值依次和排好序的序列中的值进行比较,找到应该插入的位置
4. 如果索引变量,说明要进行插入
*/

void insertSort(int arr[], int cnt)
{
  for (int i=1; i<cnt; i++)
  {
    int key = arr[i];

    int index = i - 1;

    while (index >=0 && arr[index] > key)
    {
      arr[index+1] = arr[index];
      index--;
    }

    if (index != i - 1)
    {
      arr[index+1] = key;
    }
  }
}

时间复杂度是O(n * logn)的排序算法

4.归并排序

/*
归并排序:
1. 先将数组分割为1的长度区间,排序
2. 将数组分割为长度为2的长度区间,排序
3. 将数组分割为长度为4的区间,排序
4. 相邻有序区间合并,知道成为原数组

*/
#include <stdio.h>
#include <stdlib.h>

/ 合并函数
void merge(int arr[], int left, int mid, int right);
/ 归并排序
void merger_sort(int arr[], int left, int right);

int main(int argc, char const *argv[])
{
    int arr[10] = {5,2,3,1,2, 55,23,7,8,9};
    for (int i = 0; i < 10; ++i)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");

    merger_sort(arr, 0, 9);

    for (int i = 0; i < 10; ++i)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
    return 0;
}

void merger_sort(int arr[], int left, int right)
{
    int mid = (right - left)/2 + left;

    if (left < right) {
        merger_sort(arr, left, mid);
        merger_sort(arr, mid+1, right);
        merge(arr, left, mid, right);
    }
}

void merge(int arr[], int left, int mid, int right)
{
    / 左边部分的长度
    int len1 = mid - left + 1;
    / 右边部分的长度
    int len2 = right - mid;

    int arr_l[len1];
    int arr_r[len2];
    / 构建两个小数组
    for (int i=0; i<len1; i++)
    {
        arr_l[i] = arr[left+i];
    }

    for (int j=0; j<len2; j++)
    {
        arr_r[j] = arr[mid+j+1];
    }

    / 合并操作
    int i = 0, j = 0;
    int k = left;

    while (i < len1 && j < len2) {
        if (arr_l[i] <= arr_r[j]) {
            arr[k] = arr_l[i];
            i++;

        } else {
            arr[k] = arr_r[j];
            j++;
        }
        k++;
    }

    / 剩下的元素依次放入
    while (i<len1) {
        arr[k] = arr_l[i];
        i++;
        k++;
    }
    while (j<len2) {
        arr[k] = arr_r[j];
        j++;
        k++;
    }
}

5.快速排序

/*
快速排序:
1.随机的选择一个数,小于它的放左边,大于它的放右边
2.对左右两个部分,递归的调用快速排序的过程
*/
void quick_sort(int arr[], int left, int right)
{
    int i = left;
    int j = right;

    / 设置回调结束条件
    if (i >= j)
        return;

    / 设置参考值[参考值是最小值]
    int key = arr[left];

    / 开始放置
    while (i < j) {
        while (i < j && arr[j] >= key) {
            j--;
        }
        if (i < j) {
            / 这里i上的值已经保存到key中了
            arr[i] = arr[j];
        }
        while (i < j && arr[i] <= key) {
            i++;
        }
        if (i < j) {
            arr[j] = arr[i];
        }
    }

       / 此时i就是中间位置,因为有外层的while, 一会做下分区优化
    arr[i] = key;

    quick_sort(arr, left, i-1);
    quick_sort(arr, i+1, right);
}

6.堆排序

/*
堆排序:堆是层序遍历的方式在数组中分布
1. 将数组中的各个元素,构建一个大根堆
2. 堆顶元素和最后一个元素交换
3. 剩下元素重新构建大根堆,重复以上过程,知道堆中没有元素

堆是一种树形数据结构
    parent (i)
        return [i/2]
    left (i)
        return 2i
    right (i)
        return 2i + 1
*/
#include <iostream>

using namespace std;

class HeapSort
{
public:
    / arr 数组指针
    / n 元素个数
    HeapSort(int *arr, int n)
    {
        int i, tmp;
        / 1. 构建堆
        for(int i=n/2 - 1; i>=0; i--)
        {
            / i 当前位置
            / n-1 结束位置
            HeapAdjust(arr, i, n-1);
        }

        / 2. 交换位置
        for (int i=n-1; i>=0; i--)
        {
            / 堆顶元素和最后一个元素交换
            tmp = arr[0];
            arr[0] = arr[i];
            arr[i] = tmp;

            / 调整剩下的元素
            HeapAdjust(arr, 0, i-1);
        }
    }

    / 从一个结点开始,依次向下进行堆调整
    void HeapAdjust(int *arr, int start, int end)
    {
        int j, cur, tmp;

        / 获取当前元素
        cur = start;

        tmp = arr[cur];
        / 左孩子开始
        for (j = 2*start + 1; j<=end; cur = j, j=2*j+1)
        {
            / 选择左孩子,还是选择右孩子?
            if (j < end && arr[j] < arr[j+1])
                j++;

            if (tmp >= arr[j])
            {
                break;
            }
            else
            {
                arr[cur] = arr[j];
                arr[j] = tmp;
            }
        }
    }

};

int main(void)
{
    int a[] = {51,12,3,2,23,99,8,10,2,1};

       / 这里使用了构造函数
    HeapSort *hp = new HeapSort(a, 10);

    for (int i = 0; i < 10; ++i)
    {
        cout << a[i] << " ";
    }
    cout << endl;

    delete(hp);

    return 0;
}

7.希尔排序

/*
希尔排序是插入排序的改良版
在插入排序中,比较的步长是1,而希尔排序的比较步长是逐渐调整的(从大到小)
*/
#include<iostream>

using namespace std;

void shell(int * arr, int len)
{
    if (len<=1||arr==NULL)
        return;

    /*
     1. gap 是步长增量,逐步减小
     */
    for(int gap=len/2; gap>0; gap=gap/2)
    {
        / 对gap个组进行操作
        for (int i = gap; i<len; ++i)
        {
            / 每个步长不断进行调整
            for (int j=i-gap; j>=0 && arr[j + gap] < arr[j]; j -= gap)
            {
                int tmp = arr[j];
                arr[j] = arr[j+gap];
                arr[j+gap] = tmp;
            }
        }
    }
}

int main(void)
{
    int a[] = {5,3,8,9, 1,4,2,7,6};

    shell(a, 9);

    for (int i = 0; i < 9; ++i)
    {
        cout << a[i] << " ";
    }
    cout << endl;

    return 0;
}

时间复杂度是O(n)的排序算法

这种类型的排序算法都是基于(桶排序)而来的。 记住,桶排序只是一种思想,并不是具体的排序算法。 常见的实现有计数排序,基数排序。

8.计数排序

/*
计数排序:
1. 建立数组数字范围内个桶
2. 每个元素放入到一个桶中
3. 将桶内元素依次倒出,就是一个有序的数组
*/
#include <iostream>
#include <cstdlib>

using namespace std;

class CountSort
{
public:
    /**
     * arr 数组
     * n   元素个数
     */
    void counting_sort(int *arr, int n)
    {
        int max, min;
        min = max = arr[0];

        / 1. 找到最大值和最小值
        for (int i=1; i<n; i++)
        {
            if (arr[i]<min)
                min = arr[i];
            if (arr[i]>max)
                max = arr[i];
        }

        / 2. 分配这么多的槽
        int *counts = (int *) calloc(max-min+1, sizeof(int));
        if (!counts)
            exit(-1);

        / 3. 标识一个数的个数
        for (int j=0; j<n; j++)
        {
            counts[arr[j] - min]++;
        }

        / 4. 原数组填充
        for (int i=0,j=0; i<max-min+1; i++)
        {
            while (counts[i]) {
                arr[j] = i+min;
                counts[i]--;
                j++;
            }
        }
    }
};

int main(int argc, char const *argv[])
{
    int a[] = {8,2,5,3, 1,7,4,6};

    CountSort cs;

    cs.counting_sort(a, 8);

    for (int i = 0; i < 8; ++i)
    {
        cout << a[i] << " ";
    }

    cout << endl;

    return 0;
}

9.基数排序

/*
基数排序:
1. 准备0~9十个数字桶
2. 首先按照待排序元素的个位数,依次入桶,然后依次倒出
3. 再按照十位数,依次入桶,依次倒出
4. 百位...
5. 最高位...
*/
#include <iostream>

/*
求一个数的最大位数,双层循环
*/
int max_bit(int *arr, int cnt)
{
    int bit = 1;
    int tmp = 10;

    for (int i=0; i<cnt; i++)
    {
        while (arr[i] >= tmp)
        {
            tmp *= 10;
            bit++;
        }
    }

    return bit;
}

/*
基数排序
 */
void radix_sort(int *arr, int cnt)
{
    int bit = max_bit(arr, cnt);
    int counts[10];
    int tmp[cnt];
    int radix = 1;

    / 循环次数
    for (int i=0; i<bit; i++)
    {
        / 1. 计数器置为空
        for (int i=0; i<10; i++)
            counts[i] = 0;

        / 2. 求每一个位上的个数
        for (int i=0; i<cnt; i++)
        {
            int k = (arr[i] / radix) % 10;
            counts[k]++;
        }

        / 获取每个元素,应该入桶的编号
        for (int i=1; i<10; i++)
            counts[i] = counts[i-1] + counts[i];

        / 元素根据编号入桶
        for (int i=cnt-1; i>=0; i--)
        {
            int k = (arr[i] / radix) % 10;
            tmp[counts[k] - 1] = arr[i];
            counts[k] --;
        }

        / 倒出桶内元素
        for (int i = 0; i < cnt; ++i)
        {
            arr[i] = tmp[i];
        }

        / 为下次,做准备
        radix *= 10;
    }
}

int main(int argc, char const *argv[])
{
    int a[] = {88, 12, 78, 21, 43, 90, 51, 22, 66, 54};

    radix_sort(a, 10);

    for (int i = 0; i < 10; ++i)
    {
        std::cout << a[i] << " ";
    }

    std::cout << std::endl;
    return 0;
}

排序算法的稳定性

不稳定的排序算法:快速排序,堆排序,选择排序,希尔排序;其他的都是稳定的排序算法

算法实例

1.荷兰3色国旗问题

/*
一个只包含0,1,2三种数的数组,获取一个0放在前,1中间,2后边的数组?
*/
#include <iostream>
#include <vector>

using namespace std;

class ThreeColor
{
public:
    vector<int> sortThreeColor(vector<int> &arr, int n)
    {
        int f,r,i,temp;
        for(i=f=0, r=n-1; i<=r; i++)
        {
          if (arr[i] == 0)
          {
            temp = arr[f];
            arr[f]=arr[i];
            arr[i]=temp;
            f++;
          }
          if (arr[i] == 2)
          {
            temp = arr[r];
            arr[r] = arr[i];
            arr[i] = temp;
            r--;
            i--;
          }
        }
        return arr;
    }
};

int main()
{
  int a[6]={1,2,0,2};
  vector<int> b(a,a+4);
  ThreeColor c;
  c.sortThreeColor(b,4);
  for(int i=0;i<4;i++)
  cout<<b[i]<<" ";
  cout<<endl;
  return 0;
}

查找

1.二分查找

#include <stdio.h>
#include <stdlib.h>

int binarySearch(int arr[], int cnt, int key)
{
  int left = 0;
  int right = cnt - 1;

  / 这里的等号相当重要
  while (left <= right)
  {
    int mid = (right - left)/2 + left;

    if (arr[mid] = key)
      return mid;
    else if (arr[mid] > key)
      right = mid - 1;
    else
      left = mid + 1;
  }

  return -1;
}

int main(void)
{
    int a[] = {1,3,5,6,7,8,10,13};

    int res = binarySearch(a, 8, 7);

    printf("res: %d\n, res");
    return 0;
}

算法

1.分治法

应用:快速排序

2.动态规划

应用:上台阶问题

/ 1. 有一个10个台阶的阶梯,每次只能跨越1个台阶或者2个台阶,上到台阶顶有多少种走法。

int up_stairs(int n)
{
  if (n == 1)
    return 1;
  if (n == 2)
    return 2;

  for (int i=3; i<n; i++)
  {
    / 后一种方法是前两种方法的和
    return up_stairs(n-1) + up_stairs(n-2);
  }
}

最长公共子序列

function lcs($str1, $str2)
{
    / 存储生成的二维矩阵
    $dp = array();
    / 最大子串长度
    $max = 0;

    for ($i = 0; $i < strlen($str1); $i++) { 
        for ($j = 0; $j < strlen($str2); $j++) { 
            if ($str1[$i] == $str2[$j]) {
                $dp[$i][$j] = isset($dp[$i-1][$j-1]) ? $dp[$i-1][$j-1] + 1 : 1;
            } else {
                $dp[$i-1][$j] = isset($dp[$i-1][$j]) ? $dp[$i-1][$j] : 0;
                $dp[$i][$j-1] = isset($dp[$i][$j-1]) ? $dp[$i][$j-1] : 0;

                $dp[$i][$j] = $dp[$i-1][$j] > $dp[$i][$j-1] ? $dp[$i-1][$j] : $dp[$i][$j-1];
            }

            $max = $dp[$i][$j] > $max ? $dp[$i][$j] : $max;
        }
    }

    for ($i = 0; $i < strlen($str1); $i++) { 
        for ($j = 0; $j < strlen($str2); $j++) { 
            echo $dp[$i][$j] . " ";
        }
        echo "<br />";
    }

    var_dump($max);
}

lcs("abcbdab", "bdcaba");

字符串去重

时间:2018-02-16

字符串去重就是把一个字符串中的重复字符串去除。那么使用php如何实现这个功能呢?下面是我实现的字符串去重函数。

/**
 * 去除重复字符串
 */
function removeSameStr(String $s)
{
    $str_arr = str_split($s);
    $len = count($str_arr);

    if ($len < 2)
        return $s;

    $res = '';
    for ($i=0; $i<$len; $i++) {
        $tmp = $str_arr[$i];

        if ($tmp) {
            for ($j=$i+1; $j<$len; $j++) {
                if ($tmp == $str_arr[$j]) {
                    $str_arr[$j] = '';
                }
            }
            $res .= $tmp;
        }
    }
    return $res;
}

$str = "fdsafewfwefdss29fdsfe";

echo removeSameStr($str);

swoole内核剖析5 -- swString字符串

时间:2017-12-18

1.1 字符串

swoole实现了自己的字符串swString,达到了空间的预分配和快速销毁,同时也是swoole_buffer的底层实现。

基本数据结构

typedef struct _swString
{
    size_t length;   / 长度
    size_t size;     / 大小
    off_t offset;    / 偏移
    char *str;       / 字符串指针
} swString;

在结构体swString中,length是字符串的真实长度(不包含最后的'\0'字符),str是存储真实字符串的指针。

逻辑图

swString逻辑图

基本函数

/ 新建字符出去
swString *swString_new(size_t size);
/ 复制指定长度的字符串
swString *swString_dup(const char *src_str, int length);
/ 复制字符串
swString *swString_dup2(swString *src);

/ 打印字符串
void swString_print(swString *str);
/ 销毁字符串
void swString_free(swString *str);
/ 字符串追加
int swString_append(swString *str, swString *append_str);
int swString_append_ptr(swString *str, char *append_str, int length);
/ 字符串写入
int swString_write(swString *str, off_t offset, swString *write_str);
int swString_write_ptr(swString *str, off_t offset, char *write_str, int length);
/ 字符串空间扩展
int swString_extend(swString *str, size_t new_size);
/ 字符串空间申请
char* swString_alloc(swString *str, size_t __size);

核心知识点

  • swString *swString_new(size_t size);

新建字符串,就是单纯的在堆上申请一块swString结构体的内存,初始化并将每个字段初始化为0;然后将swString->size设置为函数参数的size;接着在堆上再申请一块size大小的内存块,返回的指针赋值给swString->str字段;之后返回swString的头地址。

  • int swString_extend(swString *str, size_t new_size);

字符串扩展底层调用的就是realloc, 很简单,就是基本的库函数调用,而new_size的值却有很大的学问。是通过swoole_size_align(new_length * 2, sysconf(_SC_PAGESIZE))进行分配的,这样分配有啥好处呢?我们看看函数内部:

static sw_inline size_t swoole_size_align(size_t size, int pagesize)
{
    / 字节内存对齐
    return size + (pagesize - (size % pagesize));
}

通过使用size % pagesize求的一个缺省的内存数内存页大小,通常是4096,在加上size,这样保证了size永远是内存字节对齐的。至于为什么要进行内存对齐,网上搜索一下,大家就会明白。

  • int swString_append(swString *str, swString *append_str);

追加字符串,就是将追加字符串拼接到字符串的后边。swoole首先判断两个字符串的总长度,是否大于源字符串的size属性,如果大于,就进行字符串扩展swString_extend, 然后将字符串append_str->str拼接到str->str后边。

过程: