文档章节

[Algorithm] Circular buffer

o
 osc_n6euf5h6
发布于 2019/03/20 02:24
字数 305
阅读 11
收藏 0

精选30+云产品,助力企业轻松上云!>>>

You run an e-commerce website and want to record the last N order ids in a log. Implement a data structure to accomplish this, with the following API:

  • record(order_id): adds the order_id to the log
  • get_last(i): gets the ith last element from the log. i is guaranteed to be smaller than or equal to N.

You should be as efficient with time and space as possible.

It seems like an array would be the perfect fit for this problem. We can just initialize the array to have size N, and index it in constant time. Then, when we record any orders, we can pop off the first order and append it to the end. Getting the ith last order would then just be indexing the array at length - i.

This is one issue with this solution, however: when we have to pop off an element when the array is full, we have to move every other element down by 1. That means record takes O(N) time. How can we improve this?

What we can do to avoid having to moving every element down by 1 is to keep a current index and move it up each time we record something. For get_last, we can simply take current - i to get the appropriate element. Now, both record and get_last should take constant time.

This is actually called Circular buffer:

 

function CB_log (total) {
  let current = 0;
  let n = total;
  let logs = [];
  return {
    record (id) {
      logs[current] = id;
      current = (current + 1) % n;
    },
    get_last(i) {
      if (i > n || !i) {
          return null;
      }
      let idx = current - i;
      if (idx >= 0) {
        return logs[idx]
      } else {
        return logs[n - Math.abs(idx)]
      }
    }
  }
}



const log = new CB_log(5);

log.record(41);
log.record(17);
log.record(12);
log.record(78);
log.record(100);//3
log.record(1);//2
log.record(0);//1

console.log(
  log.get_last(4) // 78
)

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
Advent of Code Days 17 and 18: Spinlocks and Interpreters

Days 17 and 18 both defeated me. Star 1 was easy, Star 2 was not. Both were pretty quick to solve for the first star, though, so let's look at that. Day 17 - Spinlock For Advent......

Swizec Teller
2017/12/25
0
0
Configuring InnoDB Buffer Pool Flushing

翻译自5.7官方文档 performs certain tasks in the background, including flushing of dirty pages (those pages that have been changed but are not yet written to the database files)......

Amnesiasun
2017/06/27
0
0
Configuring InnoDB Buffer Pool Flushing

翻译自5.7官方文档 performs certain tasks in the background, including flushing of dirty pages (those pages that have been changed but are not yet written to the database files)......

Amnesiasun
2017/06/27
0
0
622. Design Circular Queue

Design Circular Queue https://leetcode.com/problems/design-circular-queue/discuss/149420/Concise-Java-using-array/167623https://www.youtube.com/watch?v=Ig34WPrgofI dequeue doesn......

osc_j7avs3gb
2018/08/28
1
0
备忘录:数据结构-数据

了解每种数组的用途,性能,最好能实现一遍 [Bit array ][1] [Circular buffer][2] [Dynamic array ][3] [Hash table ][4] [Hashed array tree][5] [Sparse array ][6] [List of data struct......

Bluven
2013/10/24
4
0

没有更多内容

加载失败,请刷新页面

加载更多

为什么从HBase的0.96版本开始,舍弃了-ROOT-文件?

HBase结构的读写流程 (1). HBase0.96版本之前: (2). HBase0.96开始: a. 当客户端获取到.meta文件的位置之后,会缓存.meta.文件的位置 b. 客户端还会缓存HRegion的位置 -ROOT-存在的意义: ...

其乐m
51分钟前
18
0
volatile关键字对 - What is the volatile keyword useful for

问题: At work today, I came across the volatile keyword in Java. 今天的工作中,我遇到了Java中的volatile关键字。 Not being very familiar with it, I found this explanation: 不太熟......

技术盛宴
56分钟前
25
0
golang 封装 mysql 和 redis 连接

Mysql封装 package dbimport ("fmt"_ "github.com/go-sql-driver/mysql""github.com/jmoiron/sqlx")var DB *sqlx.DBfunc init(){database, err := sqlx.Op......

开源中国最牛的人
56分钟前
21
0
pdfbox 读取文件报错 java.io.IOException: Page tree root must be a dictionary

pdfbox java.io.IOException: Page tree root must be a dictionary 示例代码 public static void main(String[] args) { try (InputStream sampleInputs = new ClassPathResource("s......

lemos
今天
28
0
整理 Linux下列出目录内容的命令

在 Linux 中,有非常多的命令可以让我们用来执行各种各样的任务。当我们想要像使用文件浏览器一样列出一个目录下的内容时,大家第一时间想到的是 ls 命令。但只有 ls 命令能实现这个目的吗?...

良许Linux
今天
17
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部