如何在频繁更新的滑动数组中有效地跟踪滚动最小值/最大值 [英] How to efficiently track rolling min / max values in a frequently updated sliding array

查看：20
本文介绍了如何在频繁更新的滑动数组中有效地跟踪滚动最小值/最大值的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

考虑以下 javascript 数据结构:

让传感器 = {传感器 1:{分钟:1.00，最大:9.00，数据: [{时间戳:1517760374400，价值:1.00},{时间戳:1517760374500，价值:2.00},{时间戳:1517760374600，价值:9.00},{时间戳:1517760374700，价值:1.00},{时间戳:1517760374800，价值:3.00},{时间戳:1517760374900，价值:1.00},{时间戳:1517760375000，价值:9.00},{时间戳:1517760375100，价值:8.00},]},//传感器 2、传感器 3 等...}

想象一下，每个传感器可能有数千个带时间戳的数据.

最初您可以轻松设置最小值/最大值，每次添加对象时，通过检查它是否大于或小于当前最大值

但棘手的部分和我的问题是:

数组的大小是有限的 - 在这种情况下，我们将其设置为长度为 8.

每当添加第 8 项之后的新项(达到限制)时，将删除第 1 项，并将第 n 项推入数组末尾.

问题是可以有更多具有相同值的项目，即使没有，我们也无法知道下一个最小值/最大值是什么，而无需再次迭代整个数组

这应该可以扩展到数千个数组项目，并且理想情况下大约每秒运行一次 - 尽可能低的 CPU 利用率 - 我真的不认为每秒循环数千个项目会足够有效.

您是否看到了其他跟踪数组最小值/最大值的其他方法，该数组每秒都在变化?

解决方案

数据结构:

  • 存储 N 项的队列大小为 N.

  • 最小/最大堆以跟踪最小/最大项目.

  • 用于跟踪每个项目频率的哈希映射.

当你有数据时，更新新项目的频率，如果堆中没有，则添加.

当你需要弹出一个item时，降低频率，而head的频率==0，则从堆中移除.

堆的头是解决方案.

伪代码:

const swap = (data, i, j) =>{让 temp = 数据 [i];数据[i] = 数据[j];数据[j] = 温度；}类堆{构造函数(){this.data = [];this.inHeap = {};this.size = 0;}头() {返回 this.data[0];}//添加项目 O(logN);加号码) {如果 (!this.inHeap[number]) {this.data[this.size++] = number;让当前 = this.size - 1;而(当前> 0){如果 (this.data[current >> 1] < this.data[current]) {交换(this.data，当前>> 1，当前)；当前＞＞＝1；} 别的 {休息;}}this.inHeap[number] = true;}}//移除头部 O(logN);消除() {this.size--;删除 this.inHeap[this.data[0]];this.data[0] = this.data[this.size];让电流 = 0;而(当前 * 2 + 1 < this.size){让下一个 = 当前 * 2 + 1;if (current * 2 + 2 < this.size && this.data[current * 2 + 2] > this.data[current * 2 + 1]) {下一个 = 当前 * 2 + 2;}如果 (this.data[current] < this.data[next]) {交换(this.data，当前，下一个)；当前 = 下一个；} 别的 {休息;}}}}类队列{构造函数(最大尺寸){this.maxSize = maxSize;this.size = 0;this.data = [];this.head = -1;}//添加一个数字并返回删除的项目(如果有)加号码) {让下一个 = (this.head + 1) % this.maxSize;让removedItem = this.data[next];this.data[next] = 数字；this.head = 下一个；if (removedItem === undefined) {this.size++;}返回已删除的项目；}得到(我){返回 this.data[(this.head - this.size + 1 + i + this.maxSize ) % this.maxSize];}}类解决方案{构造函数(n){this.n = n;this.queue = new Queue(this.n);this.heap = new Heap();this.频率 = {};}加号码) {让removedItem = this.queue.add(number);如果 (!this.frequency[number]) {this.frequency[数字] = 1;this.heap.add(number);} 别的 {this.frequency[number]++;}if (removedItem !== undefined) {this.frequency[removedItem]--;如果 (!this.frequency[removedItem]) {删除 this.frequency[removedItem];}//如果频率为零，则移除头部while (!this.frequency[this.heap.head()]) {this.heap.remove();}}}尺寸() {返回 this.queue.size;}得到(我){返回 this.queue.get(i);}最大限度() {返回 this.heap.head();}}/*** 在这里使用解决方案！！**/让解决方案=新解决方案(3)；让 numberInput = document.getElementById("number");让 data = document.getElementById("data");让 maxResult = document.getElementById("max");让 heapData = document.getElementById("heap");让 queueData = document.getElementById("queue");let frequencyData = document.getElementById("频率");函数 addNumber() {让值 = parseInt(numberInput.value);如果(isNaN(值)){alert("请输入数字！");} 别的 {解决方案.添加(值)；}maxResult.innerHTML = "Max:" + solution.max();//收集资料让 dataString = "";for (let i = 0; i 

.input {显示:弹性；}.input 输入 {宽度:200px；填充:5px 10px；大纲:无；}.输入按钮{填充:5px 10px；边框:1px纯浅灰色；}div {填充:5px 10px；}

<input type="text" id="number"/><button onClick="addNumber()">添加</button>
<div class="result"><div class="data" id="data">数据:

麦克斯:未定义！

<div class="debug"><div><code class="data" id="heap">堆:

<div><code class="max" id="queue">队列:

<div><code class="max" id="频率">频率:

Consider the following javascript data structure:

let sensors = { 
  sensor1: {
    min: 1.00,
    max: 9.00,
    data: [
      {
        timestamp: 1517760374400,
        value: 1.00
      },
      {
        timestamp: 1517760374500,
        value: 2.00
      },
      {
        timestamp: 1517760374600,
        value: 9.00
      },
      {
        timestamp: 1517760374700,
        value: 1.00
      },
      {
        timestamp: 1517760374800,
        value: 3.00
      },
      {
        timestamp: 1517760374900,
        value: 1.00
      },
      {
        timestamp: 1517760375000,
        value: 9.00
      },
      {
        timestamp: 1517760375100,
        value: 8.00
      },
    ]
  },
  // sensor2, sensor3, etc...
}

Imagine there could be thousands of timestamped data for each sensor.

Initially you can easily set a min / max value, every time an object is added by checking if it is bigger or smaller than the current max

But the tricky part and my question is this:

What is the size of the array is limited - in this case we would set it to a length of 8.

Whenever a new item after item 8 is added (the limit is reached), the 1st item will be removed, and the nth item will be pushed into the end of the array.

The problem is that there can be more items with the same value, and even if there isn't we have no way of knowing which min / max is next without iterating the entire array once again

This is supposed to be scalable to thousands of array items, and is to be run roughly every second with ideally - as low cpu utilization as possible - I don't really think looping over thousands of items every second will be effecient enough.

Do you see another other ways of keeping track of min / max values of an array which is changing like this ever second?

解决方案

Data structure:

When you there is a coming data, update the frequency of the new item, if not there in the heap, add it.

When you need to pop an item, decrease the frequency, while frequency of head == 0, remove from the heap.

Head of the heap is the solution.

Pseudo code: 

const swap = (data, i, j) => {
  let temp = data[i];
  data[i] = data[j];
  data[j] = temp;
}

class Heap {
  constructor() {
    this.data = [];
    this.inHeap = {};
    this.size = 0;
  }
  
  head() {
    return this.data[0];
  }
  // add item O(logN);
  add(number) {
  
    if (!this.inHeap[number]) {
      this.data[this.size++] = number;
      let current = this.size - 1;

      while (current > 0) {
        if (this.data[current >> 1] < this.data[current]) {
          swap(this.data, current >> 1, current);
          current >>= 1;
        } else {
          break;
        }
      }
      this.inHeap[number] = true;
    }
    
  }
  // remove head O(logN);
  remove() {
    this.size--;
    delete this.inHeap[this.data[0]];
    this.data[0] = this.data[this.size];

    let current = 0;
    while (current * 2 + 1 < this.size) {
      let next = current * 2 + 1;
      if (current * 2 + 2 < this.size && this.data[current * 2 + 2] > this.data[current * 2 + 1]) {
        next = current * 2 + 2;
      } 
      
      if (this.data[current] < this.data[next]) {
        swap(this.data, current, next);
        current = next;
      } else {
        break;
      }
    }
    
  }
}

class Queue {
  constructor(maxSize) {
    this.maxSize = maxSize;
    this.size = 0;
    this.data = [];
    this.head = -1;
  }
  
  // add a number and return the removed item if any
  add(number) {
    let next = (this.head + 1) % this.maxSize;
    let removedItem = this.data[next];
    this.data[next] = number;
    this.head = next;
    
    if (removedItem === undefined) {
      this.size++;
    }
    
    return removedItem;
  }
  
  get(i) {
    return this.data[(this.head - this.size + 1 + i + this.maxSize ) % this.maxSize];
  }
}

class Solution {
  constructor(n) {
    this.n = n;
    this.queue = new Queue(this.n);
    this.heap = new Heap();
    this.frequency = {};
  }
  add(number) {
    let removedItem = this.queue.add(number);
    
    if (!this.frequency[number]) {
      this.frequency[number] = 1;
      this.heap.add(number);
    } else {
      this.frequency[number]++;
    }
    
    if (removedItem !== undefined) {
      this.frequency[removedItem]--;
      
      if (!this.frequency[removedItem]) {
        delete this.frequency[removedItem];
      }
      
      // remove head if frequency is zero
      while (!this.frequency[this.heap.head()]) {
        this.heap.remove();
      }
    }
  }
  
  size() {
    return this.queue.size;
  }
  
  get(i) {
    return this.queue.get(i);
  }
  
  max() {
    return this.heap.head();
  }
}

/*** use of solution here!! **/
let solution = new Solution(3);
let numberInput = document.getElementById("number");
let data = document.getElementById("data");
let maxResult = document.getElementById("max");
let heapData = document.getElementById("heap");
let queueData = document.getElementById("queue");
let frequencyData = document.getElementById("frequency");

function addNumber() {
  let value = parseInt(numberInput.value);
  
  if (isNaN(value)) {
    alert("Please input a number!");
  } else {
    solution.add(value);
  }
  
  maxResult.innerHTML = "Max: " + solution.max();
  
  // gather data
  let dataString = "";
  for (let i = 0; i < solution.size(); i++) {
    dataString += " " + solution.get(i);
  }
  
  data.innerHTML = "Data: " + dataString;
  heapData.innerHTML = "Heap: " + JSON.stringify(solution.heap.data.slice(0, solution.heap.size));
  queueData.innerHTML = "Queue: " + JSON.stringify(solution.queue);
  frequencyData.innerHTML = "Frequency: " + JSON.stringify(solution.frequency);
  
  numberInput.value = parseInt(Math.random() * 1000);
}

.input {
  display: flex;
}

.input input {
  width: 200px;
  padding: 5px 10px;
  outline: none;
}

.input button {
  padding: 5px 10px;
  border: 1px solid light gray;
}

div {
  padding: 5px 10px;
}

<div class="input">
  <input type="text" id="number" />
  <button onClick="addNumber()">Add</button>
</div>
<div class="result">
  <div class="data" id="data">
    Data: 
  </div>
  <div class="max" id="max">
    Max: undefined!
  </div>
</div>
<div class="debug">
  <div>
    <code class="data" id="heap">
      Heap:
    </code>
  </div>
  <div>
    <code class="max" id="queue">
    Queue:
    </code>
  </div>
  <div>
    <code class="max" id="frequency">
      Frequency:
    </code>
  </div>
</div>

这篇关于如何在频繁更新的滑动数组中有效地跟踪滚动最小值/最大值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！

查看全文
相关文章
前端开发最新文章
热门教程
热门工具
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆