algorithm - 在数组末尾添加新数据点不是一个坏主意吗？(Is adding the new data point not at the end of array a bad idea?)

Question

This involves a design decision.

(这涉及设计决策。)

An interviewer asked me to write something to plot the data assuming there are 100 data points, and new data point comes in (and given to the program) every 0.1, 0.3 or 0.5 or 1 second.

(一位访调员要求我假设有100个数据点，并且每隔0.1、0.3或0.5或1秒钟就会有新数据点出现（并提供给程序），以写出一些数据图表。)

(it can change in the future, and I think the smallest granularity on a common web browser is 0.03 seconds).

(（将来可能会改变，我认为普通网络浏览器的最小粒度为0.03秒）。)

I proceeded to think about adding the new data point to the Nth position in the array.

(我开始考虑将新数据点添加到数组中的第N个位置。)

For example, adding the data at array entry 36, and plot the data from 37th to 99th, and then from 0th to 36th.

(例如，在数组条目36处添加数据，然后将数据从第37绘制到第99，然后从0绘制到第36。)

Next time, add the data at array entry 37, and plot the data from 38th to 99th, and then from 0th to 37th.

(下次，将数据添加到数组条目37中，并将数据从38号绘制到99号，然后从0号绘制到37号。)

This way, we don't need to "unshift" (shift out) the data at entry 0 and therefore needing to shift entry 1 to 99 one place forward, and then add the new data point at entry 99, and then plot data entry 0 to 99.

(这样，我们不需要“取消移位”（移出）条目0处的数据，因此无需将条目1向前移至99位，然后在条目99处添加新数据点，然后绘制数据条目0至99。)

For some reason, the interviewer gave a big frown, and said, "why would we do that? It is not heavy to shift 99 data over."

(出于某种原因，面试官大为皱眉，说道：“我们为什么要这么做？将99个数据转移过来并不繁重。”)

I said what if there are 500 or 1000 data point we'd like to plot in the future, we might want to avoid shifting data about 500 times or 1000 time each time when a new data point comes in.

(我说过，如果将来要绘制500或1000个数据点，我们可能希望避免每次输入新数据点时将数据移位500或1000次。)

He mentioned "let's say we just shift them anyway".

(他提到“让我们无论如何都要转移它们”。)

Is shifting the data actually not an issue or concern?

(转移数据实际上不是问题或担忧吗？)

What if on the screen we have 10 or 15 of such widgets, apps, or webpages, to monitor 15 types of data, we might want to avoid shifting 15,000 data entries constantly.

(如果在屏幕上有10或15个这样的小部件，应用程序或网页怎么办，以监视15种数据类型，我们可能要避免不断移动15,000个数据条目。)

  ask by nopole translate from so

Answer 1

I naively tried to load n canvas to the page, and compared the time needed to plot against the time taken shifting array.

(我天真地尝试将n个画布加载到页面，并将绘制所需的时间与移动数组所花费的时间进行了比较。)

tldr: Whichever method is used to shift the points, the method is negligible against the time needed to plot the points.

(tldr：无论使用哪种方法移动点，该方法与绘制点所需的时间都可以忽略不计。)

(~ 3%)

(（?3％）)

---

I only run the code in ff70 with casual js.

(我只在带有休闲js的ff70中运行代码。)

(For instance I am stocking an array of objects even though optimization may be available if I stock only floats)

(（例如，即使我仅存储浮动对象，即使可以进行优化，我也要存储一组对象）)

There are two kind of measures: push and refresh.

(有两种措施：推送和刷新。)

• push measures the time needed to shift a point and add a new one

  (推式测量移动一个点并添加一个新点所需的时间)

• refresh measures the time needed to replot the canvas

  (刷新度量重新绘制画布所需的时间)

Below three approaches for pushing: either push (Array.prototype.(shift|push), tail to a queue (and move the head), or nopole's approach

(以下三种推入方法：推入（Array.prototype。（shift | push），拖尾到队列（并移动头部）或nopole的方法)

Every 10ms I plot the time spent in the push method.

(我每隔10ms绘制一次push方法中的时间。)

On top of the picture, the cumulative time spent.

(在图片顶部，花费了累计时间。)

I stop once a run has reached 100 points and reload the page for another run.

(一旦运行达到100点，我就会停止，然后重新加载页面以进行另一次运行。)

The y axis is the same accross all runs

(y轴在所有行程中都相同)

1. Push

   (推)

push avg: (838+886+864)/3 = 862ms

(推平均：（838 + 886 + 864）/ 3 = 862ms)

2. Queue

   (队列)

push avg: (625+760+825)/3 = 736ms

(推平均（625 + 760 + 825）/ 3 = 736ms)

refresh avg: (40554+39934+40915+39194+39264+30480)/6 = 38390ms

(刷新平均：（40554 + 39934 + 40915 + 39194 + 39264 + 30480）/ 6 = 38390ms)

3. Nopole

   (诺波尔)

push avg: (792+861+871)/3 = 841ms

(推平均：（792 + 861 + 871）/ 3 = 841ms)

Notice that for one sample: (625/30480) we seem to have benefited from some cpu willing to work.

(请注意，对于一个示例：（625/30480），我们似乎已经从一些愿意工作的CPU中受益。)

So the shifting method feels even more irrelevant.

(因此，移位方法变得更加无关紧要。)

It is hard to tell which approach is better, because of the few samples drought for each kind of methods and it is likely more an issue of cpu's overall workload rather than the page itself

(很难确定哪种方法更好，因为每种方法的样本干旱少，这很可能是cpu整体工作量的问题，而不是页面本身的问题)

To reproduce

(重现)

 let timerPush = 0 let timerRefresh = 0 class Canvas { constructor (f, el, period) { this.w = 300 this.h = 300 this.points = [] const canvas = document.createElement('canvas') canvas.style.cssText = 'background:#eeeeee; margin:10px;' canvas.width = this.w canvas.height = this.h this.ctx = canvas.getContext('2d') this.ctx.transform(1, 0, 0, -1, 0, this.h / 2) this.ctx.lineWidth = 1 this.dw = this.w / this.MAX_POINTS this.dh = this.h / 2 el.appendChild(canvas) let x = 0 this.timer = setInterval(_ => { x += period this.push({ x, y: f(x) }) this.refresh() }, period * 1000) } refresh () { const now = performance.now() this.ctx.clearRect(0, -this.h / 2, this.w, this.h) this.ctx.beginPath() this._plot() this.ctx.stroke() this.ctx.closePath() timerRefresh += performance.now() - now } push (p) { const now = performance.now() this._push(p) timerPush += performance.now() - now } _plot () { if (!this.points.length) { return } this.ctx.moveTo(0 * this.dw, this.points[0].y * this.dh) for (let i = 1; i < this.points.length; ++i) { const p = this.points[i] this.ctx.lineTo(i * this.dw, py * this.dh) } } _push (p) { if (this.points.length == this.MAX_POINTS) { this.points.shift() } this.points.push(p) } MAX_POINTS = 100 } class CanvasQueue extends Canvas { constructor () { super(...arguments) this.tail = {} this.head = this.tail this.n = 0 } _plot () { if (!this.head.next.p) return let node = this.head.next this.ctx.moveTo(0 * this.dw, node.py * this.dh) let i = 1 node = node.next while (node) { this.ctx.lineTo(i * this.dw, node.py * this.dh) ++i node = node.next } } _push (p) { if (this.n === this.MAX_POINTS) { this.head = this.head.next } else { this.n++ } const node = { p } this.tail.next = node this.tail = node } } class CanvasNopole extends Canvas { constructor () { super(...arguments) this.start = 0 } _plot () { if (!this.points.length) { return } const s = this.start let z = 1 let startBack = 0 if (this.points[s]){ this.ctx.moveTo(0 * this.dw, this.points[s].y * this.dh) for (let i = s+1; i < this.points.length; ++i) { const p = this.points[i] this.ctx.lineTo(z++ * this.dw, py * this.dh) } }else{ this.ctx.moveTo(0 * this.dw, this.points[0].y * this.dh) startBack = 1 } for (let i = startBack; i < s; ++i) { const p = this.points[i] this.ctx.lineTo(z++ * this.dw, py * this.dh) } } _push (p) { this.points[this.start] = p this.start = (this.start + 1) % this.MAX_POINTS } } class CanvasSummary extends Canvas { constructor () { super(...arguments) this.ctx.resetTransform() this.ctx.transform(1, 0, 0, -1, 0, this.h) // we know beforehand that timer should not grow bigger const deltaTimer = 50 this.dh = this.h / deltaTimer this.old = timerPush } refresh () { this.ctx.clearRect(0, 0, this.w, this.h) this.ctx.beginPath() this.ctx.resetTransform() this.ctx.fillText(`push: ${timerPush} plot: ${timerRefresh}`, 5, 20) this.ctx.transform(1, 0, 0, -1, 0, this.h) this._plot() this.ctx.stroke() this.ctx.closePath() } push (p) { this._push(p) } } function run () { const $summary = document.querySelector('.summary') const $bench = document.querySelector('.bench') const cs = new CanvasSummary(x => { if (cs.points.length === cs.MAX_POINTS) { clearInterval(cs.timer) } const y = timerPush - cs.old cs.old = timerPush return y }, $summary, 1) //const canvas = Array(30).fill(0).map(x => new Canvas(Math.sin, $bench, 0.01)) //const canvas = Array(30).fill(0).map(x => new CanvasQueue(Math.sin, $bench, 0.01)) const canvas = Array(30).fill(0).map(x => new CanvasNopole(Math.sin, $bench, 0.01)) } run() 

 <section class="summary"></section> <hr/> <div class="bench"></div>