环形缓冲区在数据结构中是一种特殊的线性数据结构，具有以下特点和优势：

结构特点

  • 固定大小：环形缓冲区通常具有固定的容量，一旦创建，其大小就不能改变。这使得在内存使用方面更加可控，避免了动态分配内存带来的开销和不确定性。
  • 循环利用空间：正因为其环形的特性，当写指针到达缓冲区的末尾时，会自动回绕到开头继续写入数据；读指针在读取完数据后也会相应地移动，实现空间的循环利用。

操作方式

  • 写入操作：当向环形缓冲区写入数据时，首先检查缓冲区是否已满。如果未满，则将数据写入写指针所指的位置，然后写指针向前移动一位。如果写指针移动到缓冲区的末尾，它会回绕到开头。
  • 读取操作：从环形缓冲区读取数据时，先检查缓冲区是否为空。如果不为空，则读取读指针所指位置的数据，然后读指针向前移动一位。同样，当读指针到达缓冲区的末尾时，会回绕到开头。

应用场景

  • 实时数据处理：在需要对连续产生的实时数据进行处理的场景中，环形缓冲区可以作为数据的暂存区域。例如，音频和视频流的处理，数据采集系统等。
  • 多生产者 - 多消费者模型：环形缓冲区可以方便地在多个生产者和多个消费者之间共享数据。生产者将数据写入缓冲区，消费者从缓冲区读取数据，通过合理的同步机制，可以实现高效的数据交换。
  • 缓存数据：可以用作缓存，存储最近使用的数据，以提高数据的访问速度。例如，在数据库查询中，可以将最近查询的结果存储在环形缓冲区中，以便下次相同的查询可以直接从缓冲区中获取结果。

实现要点

  • 指针管理：准确地管理写指针和读指针是实现环形缓冲区的关键。需要确保指针的移动正确无误，并且在进行读写操作时不会出现越界的情况。
  • 同步机制：在多线程环境下使用环形缓冲区时，需要考虑同步问题。可以使用互斥锁、条件变量等同步机制来确保线程安全。
  • 空满判断：需要有可靠的方法来判断环形缓冲区是为空还是已满。常见的方法有使用计数器、位运算等。

示例：错误日志记录

描述

https://www.nowcoder.com/practice/2baa6aba39214d6ea91a2e03dff3fbeb

开发一个简单错误记录功能小模块，能够记录出错的代码所在的文件名称和行号。

处理：

  1. 记录最多8条错误记录，循环记录，最后只用输出最后出现的八条错误记录。对相同的错误记录只记录一条，但是错误计数增加。最后一个斜杠后面的带后缀名的部分（保留最后16位）和行号完全匹配的记录才做算是“相同”的错误记录。
  2. 超过16个字符的文件名称，只记录文件的最后有效16个字符；
  3. 输入的文件可能带路径，记录文件名称不能带路径。也就是说，哪怕不同路径下的文件，如果它们的名字的后16个字符相同，也被视为相同的错误记录
  4. 循环记录时，只以第一次出现的顺序为准，后面重复的不会更新它的出现时间，仍以第一次为准

数据范围：错误记录数量满足 1≤n≤100 1≤n≤100 ，每条记录长度满足 1≤len≤100 1≤len≤100

输入描述：

每组只包含一个测试用例。一个测试用例包含一行或多行字符串。每行包括带路径文件名称，行号，以空格隔开。

输出描述：

将所有的记录统计并将结果输出，格式：文件名 代码行数 数目，一个空格隔开，如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
输入：

D:\zwtymj\xccb\ljj\cqzlyaszjvlsjmkwoqijggmybr 645
E:\je\rzuwnjvnuz 633
C:\km\tgjwpb\gy\atl 637
F:\weioj\hadd\connsh\rwyfvzsopsuiqjnr 647
E:\ns\mfwj\wqkoki\eez 648
D:\cfmwafhhgeyawnool 649
E:\czt\opwip\osnll\c 637
G:\nt\f 633
F:\fop\ywzqaop 631
F:\yay\jc\ywzqaop 631
D:\zwtymj\xccb\ljj\cqzlyaszjvlsjmkwoqijggmybr 645

输出：

rzuwnjvnuz 633 1
atl 637 1
rwyfvzsopsuiqjnr 647 1
eez 648 1
fmwafhhgeyawnool 649 1
c 637 1
f 633 1
ywzqaop 631 2

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
import sys

SIZE = 8

def formatFileName(f, size = 16):
    if len(f) > size:
        return f[-16:]
    else:
        return f

class RingBuffer:
    def __init__(self, size) -> None:
        self.buffer = []
        self.legacy = []
        self.head = 0
        self.size = size
    def put(self, item):
        if item is not None:  # 跳过已经淘汰的日志
            for l in self.legacy:
                if l["file"] == item["file"] and l["line"] == item["line"]:
                    return
        if len(self.buffer) < self.size:  # 缓冲区没有满，追加即可
            self.buffer.append(item)
        else:  # 缓冲区已满，把要添加的元素放到队尾
            self.legacy.append(self.buffer[self.head])  # 记录已经淘汰的日志
            self.buffer[self.head] = item
            self.head = (self.head + 1) % self.size
    def findItem(self, file, line):
        for idx, i in enumerate(self.buffer):
            if i["file"] == file and i["line"] == line:  # 文件名和行号都相同才可以
                return idx
        return None
    def showItem(self, idx):
        if idx < len(self.buffer):
            return self.buffer[idx]
        else:
            return None
    def updateItem(self, idx, key, value):
        self.buffer[idx][key] = value
    def print(self):
        if not len(self.buffer):
            return
        headNode = self.buffer[self.head]
        print(f'{headNode.get("file")} {headNode.get("line")} {headNode.get("count")}')
        h = (self.head + 1) % len(self.buffer)
        while (h != self.head):
            node = self.buffer[h]
            print(f'{node.get("file")} {node.get("line")} {node.get("count")}')
            h = (h + 1) % len(self.buffer)

def filterLog(log):
    if not log or not isinstance(log, str):
        return None, None
    [path, line] = log.split()
    return path.split("\\")[-1], line


buffer = RingBuffer(SIZE)
for line in sys.stdin:
    f, l = filterLog(line.strip())
    if f is None or l is None:
        continue
    f = formatFileName(f)  # 题目出的很奇怪，尾十六位相同的文件竟然被当成同一个文件
    idx = buffer.findItem(f, l)
    if idx is not None:
        item = buffer.showItem(idx)
        if item:
            buffer.updateItem(idx, "count", item["count"] + 1)
    else:
        buffer.put({"file": f, "line": l, "count": 1})
buffer.print()