8

环形（循环）缓冲区和队列有什么区别？两者都支持 FIFO，所以在什么情况下我应该在队列上使用环形缓冲区，为什么？

与 Hadoop 的相关性

map 阶段使用环形缓冲区来存储中间键值对。选择队列的原因是什么？

4

4 回答 4

8

RingBuffer 是一个数组，用作队列

它将分别维护读取和写入位置。当它到达 Array 的末尾时，它将从 Array 的开头继续。

RingBuffer 在队列上的使用。

  1. 环形缓冲区很快。
  2. 当您很难确定要存储多少数据时，RingBuffer 很有用。

有关更多详细信息，请查看 Jakob Jenkov 的这篇文章。

看看相关的 SE 问题：

Java - 环形缓冲区

于 2016-02-02T04:41:46.813 回答
6

队列是支持入队和出队操作的抽象数据类型。环形缓冲区是队列的一种可能实现，尽管它不是唯一的（例如，您可以使用链表实现队列）。换句话说，队列是可以支持 FIFO 插入的数据结构的通用术语，而环形缓冲区是您可以用来实现队列的一种可能的数据结构。

希望这可以帮助！

于 2014-06-09T17:14:56.163 回答
2

两者在实现上非常相似，但它们在使用上的细微差别会使它们看起来完全不同。这是简短的答案：

Ring：可以读取缓冲区中的中间值，例如“最近的历史缓冲区”

Fifo：只能读取最旧的（并且经常在读取时删除）

长答案

环形缓冲区有一个指针，当它到达末尾时会前进和回绕。这允许数据在自然过时时被覆盖。如果您需要为某事保留最后 N 个样本，这很有用。示例用法：

  • FIR 实现，您将在其中使用最近的 N 个样本。随着新数据点的出现，FIR 将对最近的 N 个数据点进行操作。
  • 如果发生特定事件，则捕获最后 N 个数据点（如行车记录仪，如果检测到事件，则会自动保存最后 5 秒的视频）

一个 FIFO 或 Queue（两者是同一个），通常被实现为一个环形缓冲区（templatetypedef 的答案是正确的，它可能是一个链表）。与环形缓冲区相比，会有2个指针；一个用于读取，另一个用于写入。就像环形缓冲区指针一样，任何一个指针都会在递增时回绕到物理缓冲区的开头；给人一种连续缓冲的错觉。请注意，写指针赶上读指针被认为是错误的。示例用法：

  • 一个实体正在生产数据，另一个实体正在处理它，但处理不能及时或与数据生产者同时发生。就像邮局的排队一样。
  • 消息从一个系统发送到另一个系统。秩序很重要，任何一个都不应丢失。
于 2019-01-31T18:41:32.147 回答
1

我宁愿说队列是一种策略，它规定了物品的放置位置以及它们从何处移除。在队列（也称为 FIFO）中，客户被放置在后面，然后从前面移除，让第一个来的人成为第一个得到服务的人。

另一方面，缓冲区是一个更通用的名称，并没有提及其策略，尽管大多数时候人们认为缓冲区是一个 FIFO。缓冲区通常是一个更“物理”的结构，因此通常与一些容量限制相关联（比如说 8 个项目）。

在您的情况下，循环缓冲区实现了一个 FIFO，该 FIFO 对未完成客户的数量具有上限，如果您超过此最大值，它将丢弃最旧的客户并替换为新客户。

于 2016-02-01T18:46:52.597 回答