东风草堂博客

公众号:开发者来风

发表于 更新于

队列

循环队列，固定容器大小，实现如下。

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
#include <iostream>

using namespace std;

const int MAX_QUEUE_SIZE = 102;

template<typename T>
class Node {
public:
    T data;
    Node<T>* next;
};

template<typename T>
class CircularQueue {
public:
    CircularQueue(): front(NULL), rear(NULL), size(0) {}
    bool enqueue(T data);
    bool dequeue(T& data);
    bool isFull() { return size == MAX_QUEUE_SIZE; }
    bool isEmpty() { return size == 0; }
    int getSize() { return size; }
    void printQueue();

private:
    Node<T>* front;
    Node<T>* rear;
    int size;
};

template<typename T>
bool CircularQueue<T>::enqueue(T data) {
    if (isFull()) {
        if (front == NULL) {
            return false; // 队列为空的情况
        }
        // 队列已满，直接修改最早插入节点的值
        front->data = data;
        front = front->next; // 移动头指针
        rear = rear->next; // 移动尾指针
    } else {
        Node<T>* newNode = new Node<T>();
        newNode->data = data;
        newNode->next = front;
        if (isEmpty()) {
            front = newNode;
            rear = newNode;
        } else {
            rear->next = newNode;
            rear = newNode;
        }
        size++;
    }
    return true;
}

template<typename T>
bool CircularQueue<T>::dequeue(T& data) {
    if (isEmpty()) {
        return false;
    }
    Node<T>* temp = front;
    data = temp->data;
    front = front->next;
    delete temp;
    size--;
    return true;
}

template<typename T>
void CircularQueue<T>::printQueue() {
    if (isEmpty()) {
        cout << "Queue is empty" << endl;
    } else {
        Node<T>* temp = front;
        while (temp != rear) {
            cout << temp->data << " ";
            temp = temp->next;
        }
        cout << rear->data << " " << endl;
    }
}

int main() {
    CircularQueue<int> q;
    for (int i = 0; i < 100; i++) {
        q.enqueue(i);
    }
    q.printQueue();
    q.enqueue(100);
    q.enqueue(101);
    q.enqueue(102);
    q.enqueue(103);
    q.enqueue(104);
    q.printQueue();
    return 0;
}

在用数组实现的非循环队列中，队满的判断条件是 tail == n，队空的判断条件是 head == tail。那针对循环队列，如何判断队空和队满呢？

队列为空的判断条件仍然是 head == tail。但队列满的判断条件就稍微有点复杂了。

就像我图中画的队满的情况，tail=3，head=4，n=8，所以总结一下规律就是：(3+1)%8=4。多画几张队满的图，你就会发现，当队满时，(tail+1)%n=head。

阅读全文 »

发表于 更新于

包完整性

  1. 以特殊符号来分界，如每个包都以特定的字符来结尾（如\r\n，http的header就是），当在字节流中读取到该字符时，则表明上一个包到此为止。
  2. 固定包头+包体结构，包头一般时一个固定字节长度的结构，并且包头中会有一个特定的字段指定包体的大小。收包时，先接收固定字节数的头部，解出这个包的完整长度，按此长度接收包体。header+body 目前应用最多的一种包格式。
  3. 在序列化后的buffer前面增加一个字符流的头部，其中有一个字段存储包总长度，根据特殊字符（比如\n或者\0）判断头部的完整性。这样通常比2麻烦些，http和redis（$6\r\nfoobar\r\n）采用的这种形式，收包的时候，先判断已经收到的数据中是否包含结束符，收到结束符后解析包头，解出这个包完整长度，按此长度接收包体。

协议设计

序列号：tcp只能保证数据到达，不能保证数据是否处理。

type表示协议类型，如xml，json。

版本号尽量放在前面，读取版本号的时候可以少读一些字节，如下nginx。protobuf封装后是放在body里面的。header也是定长的，就不用序列化。body做序列化即可。

http请求头为文本，但是body如果传的是jpeg就是二进制。

xml、json序列化后都是文本，protobuf序列化后就是二进制，这里指的是将对象序列化，对象里面一些变长的字段不进行序列化不方便传输。

阅读全文 »

发表于 更新于


采用proto buffer作为idl语言。
采用http2进行通信，body采用protobuf序列化后的二进制传输，将字段名去掉，以数字代替。

四种模式：一个端口可以对应多个service

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
syntax = "proto3";
package helloworld; // 命名空间
option go_package = "grpc/helloworld/proto";
import "google/protobuf/timestamp.proto";
import "google/protobuf/any.proto"; // go 里面的interface类型

service Greeter {
// simple rpc
rpc GetFeature(Point) returns (Feature) {}

// server-to-client streaming rpc，下载文件
rpc ListFeatures(Rectangle) returns (stream Feature) {}

// client-to-server streaming rpc，上传文件
rpc RecoredRoute(stream Point) returns (RouteSummary) {}

// Bidirectional streaming rpc，开多线程读写实现，问答场景
rpc RouteChat(stream RouteNote) returns (stream RouteNote) {}
}

// 结构体以message开头
message Feature {
    // 1-15 占一个字节
    string name = 1;
    Point location = 2;
    google.protobuf.Timestamp birthday = 9;
    Address address = 10; // 自定义类型
    repeated string hobys = 11; // 多个兴趣
    map<string, google.protobuf.Any> data = 12;
    reserved 3, 4 to 8; // 保留字段
    reserved "phone", "email";
}

enum Gender {
    FEMALE = 0; // 必须0开始
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// ListFeatures
std::unique_ptr<ClientReader<Feature>> reader(stub_->ListFeatures(&context, rect)); // 通过stub_
while (reader->Read(&feature)) { // 重复接收
    std::cout << "Found feature called " << feature.name() << " at " << feature.location().latitude() / kCoordFactor_ << ", " << feature.location().longitude() / kCoordFactor_ << << std::endl;
}
Status status = reader->Finish();
if (status.ok()) {
    std::cout << "ListFeatures rpc success." << std::endl;
} else {
    std::cout << "ListFeatures rpc failed." << std::endl;
}

// 主线程读
RouteNote server_note;
while (stream->Read(&server_note)) {
    std::cout << "Got message " << server_note.message() << " at " << server_note.location().latitude() << ", " << server_note.location().longitude() << std::endl;
}
writer.join(); // 等待写线程完成

grpc用于微服务所面临的问题：

  1. 用户鉴权问题，鉴权方案的具体实现还包括了多种场景下的解决方案，例如：基于 JWT 或 OAuth 认证、基于多种细粒度授权方案进行授权、支持 OIDC 等。开发者需要根据具体的业务需求和安全要求，选择合适的鉴权方案。
阅读全文 »

发表于 更新于

docker

1
2
3
docker run -itd --name redis -p 6379:6379 --restart unless-stopped redis
docker exec -ti redis bash
redis-cli

redis

内存数据库、kv数据库、数据结构数据库
对象类型有哪些？底层使用了哪些数据结构

  • string
    • int，字符串长度小于等于20且能转成整数，set teacher 1000000，type teacher，object encoding teacher
    • raw，字符串长度大于44
    • embstr，字符串长度小于等于44，cpu缓存中基本单位为cacheline 64字节，sdshdr头为9字节，加上’\0’，buf的最大长度为44，set teacher 1000000a，object encoding teacher
  • list
    • quicklist，双向循环链表
    • ziplist，压缩链表
  • hash，hmset role:1001 age 30 name mark sex 1, hgetall role:1001, hget role:1001 age，散列表：指针数组+数组长度+hash函数
    • dict/hashtable,节点数量大于512，或字符串长度大于64
    • ziplist，压缩列表，节点数量小于等于512（hash-max-ziplist-entries），且字符串长度小于等于64(hash-max-ziplist-value)
  • set，sadd set 1 2 3 4 5,object encoding set,sadd set mark,object encoding set
    • intset，整数数组，元素都为整数，且节点数量小于等于512(set-max-intset-entries)
    • dict/hashtable，字典，元素有一个不为整数或者数量大于512
  • zset，有序的结构
    • skiplist，跳表，数量大于128或者有一个字符串长度大于64
    • ziplist，压缩列表，节点数量小于等于128（zset-max-ziplist-entries）且字符串长度小于等于64(zset-max-ziplist-value)
阅读全文 »

发表于 更新于

单调栈分为单调递增栈和单调递减栈

  1. 单调递增栈即栈内元素保持单调递增的栈
  2. 同理单调递减栈即栈内元素保持单调递减的栈
    操作规则（下面都以单调递增栈为例）
  3. 如果新的元素比栈顶元素大，就入栈
  4. 如果新的元素较小，那就一直把栈内元素弹出来，直到栈顶比新元素小

柱状图中最大的矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。

1
2
3
4
5
6
7
8
9
stack<int> st;
for(int i = 0; i < nums.size(); i++)
{
	while(!st.empty() && st.top() > nums[i])
	{
		st.pop();
	}
	st.push(nums[i]);
}
阅读全文 »

发表于 更新于

什么是递归

周末你带着女朋友去电影院看电影，女朋友问你，咱们现在坐在第几排啊？电影院里面太黑了，看不清，没法数，现在你怎么办？

别忘了你是程序员，这个可难不倒你，递归就开始排上用场了。于是你就问前面一排的人他是第几排，你想只要在他的数字上加一，就知道自己在哪一排了。但是，前面的人也看不清啊，所以他也问他前面的人。就这样一排一排往前问，直到问到第一排的人，说我在第一排，然后再这样一排一排再把数字传回来。直到你前面的人告诉你他在哪一排，于是你就知道答案了。

这就是一个非常标准的递归求解问题的分解过程，去的过程叫“递”，回来的过程叫“归”。基本上，所有的递归问题都可以用递推公式来表示。刚刚这个生活中的例子，我们用递推公式将它表示出来就是这样的：

1
f(n)=f(n-1)+1 其中，f(1)=1
阅读全文 »

发表于 更新于

因为这些排序算法的时间复杂度是线性的，所以我们把这类排序算法叫作线性排序（Linear sort）。之所以能做到线性的时间复杂度，主要原因是，这三个算法是非基于比较的排序算法，都不涉及元素之间的比较操作。

桶排序（Bucket sort）

核心思想是将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。

如果要排序的数据有 n 个，我们把它们均匀地划分到 m 个桶内，每个桶里就有 k=n/m 个元素。每个桶内部使用快速排序，时间复杂度为 O(k * logk)。m 个桶排序的时间复杂度就是 O(m * k * logk)，因为 k=n/m，所以整个桶排序的时间复杂度就是 O(n*log(n/m))。当桶的个数 m 接近数据个数 n 时，log(n/m) 就是一个非常小的常量，这个时候桶排序的时间复杂度接近 O(n)。

桶排序对要排序数据的要求是非常苛刻的。要排序的数据需要很容易就能划分成 m 个桶，并且，桶与桶之间有着天然的大小顺序。这样每个桶内的数据都排序完之后，桶与桶之间的数据不需要再进行排序。

阅读全文 »

发表于 更新于

深入解析网络测速的核心逻辑与实现方案，涵盖chunked数据传输格式、HTTP POST请求机制、基于epoll的高并发网络编程技术，详解客户端与服务端协同测速原理，提供完整的C++代码实现示例。

阅读全文 »

发表于 更新于

详细解析读写锁的功能与实现原理，包括读写锁的基本概念、加锁与解锁机制、读写锁的优化策略、读写锁的性能分析等。提供完整的C++代码示例，帮助开发者理解并在实际项目中应用读写锁。

阅读全文 »
0%