javascript - 如何有效地跟踪频繁更新的滑动数组中的滚动最小值/最大值

Question

考虑以下 javascript 数据结构:

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...
}

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

最初你可以很容易地设置一个最小/最大值，每次添加一个对象时检查它是大于还是小于当前的最大值

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

数组的大小是有限的——在本例中我们将其长度设置为 8。

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

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

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

您是否看到另一种跟踪数组的最小/最大值的方法，这种数组每秒都在变化？

Answer 1

数据结构:

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

• 最小/最大堆跟踪最小/最大项目。

• 用于跟踪每个项目频率的 HashMap 。

当你有数据到来时，更新新项的频率，如果不在堆中，添加它。

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

堆头是解决方案。

伪代码:

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>