如何构造特定于时间的数据以便可以找到最近的点? [英] How to structure time specific data so that the most recent point can be found?

问题描述

这有点难以用单行问题来表达，但我正在寻找一些建议/最佳实践，用于在 Javascript 中构建数据和编写函数.

This is kinda hard to phrase in a single line questions, but I'm looking for some advice/best practices for structuring data and writing a function in Javascript.

我有几个项目会定期更改状态.我的数据包含 itemID、时间戳和状态.我目前将它构建为一个对象数组(对于每个项目)，具有包含时间戳和状态的历史优先级.(见下文).

I have several items that change status regularly. My data contains an itemID, timestamp, and status. I am currently structuring it as an array of objects (for each item), with a history priority that contains the timestamps and status. (see below).

我正在寻找一种函数，它可以让我使用最近的过去更新轻松获取给定时间每个对象的状态.我不确定我的数据结构是否允许这样做，或者如果允许，如何编写函数.(在本例中，我将把时间戳缩短为 4 位数字)

I'm looking for a function that will allow me to easily get the status of each object at a given time using the most recent past update. I'm not sure if my data structure will allow for this, or if it does, how to write the function. (for this example I'm going to shorten my timestamps to a 4 digit number)

 var items = [
      { id: 1,
        history: {1234: 'open', 1256: 'in-use', 1289: 'reset', 1293: 'open'},
      { id: 2,
        history: {1230: 'open', 1290: 'in-use'},
      { id: 3,
        history: {1238: 'open', 1241: 'in-use', 1251: 'reset'}
 ]

我希望能够拥有这样的功能:

I'd like to be able to have a function like this:

 getStatus(1260);

然后回来

 {1: 'in-use', 2: 'open', 3: 'reset'}

每个id，根据查询时间之前的最近历史记录传入时的状态.

Each id, with the status it was in at the time passed in based on the most recent history record prior to the queried time.

我完全不喜欢这个数据结构.我还尝试让历史记录包含时间和状态的对象数组，但这意味着我每次都必须遍历整个数组.我最大的问题是我的头脑正在推动我使用 SQL 方法来执行此操作，但我被困在客户端 Javascript 中...

I am not at all attached to this data structure. I also tried having the history an array of objects containing the time and the status, but that means I have to loop through the entire array every time. My biggest problem is that my head is pushing me to an SQL method for doing this, but I'm stuck in client-side Javascript...

我的问题:最好的数据结构是什么?以及我将如何编写我的 getStatus() 函数?

My questions: What is the best data structure for this? and How would I go about writing my getStatus() function?

谢谢！

推荐答案

我还尝试让历史记录包含时间和状态的对象数组，但这意味着我每次都必须遍历整个数组.

I also tried having the history an array of objects containing the time and the status, but that means I have to loop through the entire array every time.

如果您对数组进行了排序，则不会，因为您可以直接访问最近的日期.您也可以使用二进制搜索来获取特定时间戳的状态.对于您当前拥有的对象，您总是必须枚举所有属性以找到最匹配的.

Not if you had the array sorted, as you then can access the most recent date directly. Also you can use binary search for getting the state at a specific timestamp. With the object you currently have, you always have to enumerate all properties to find the best-matching.

var items = [
  { id: 1,
    history: [
      { timestamp: 1234, status: 'open'},
      { timestamp: 1256, status: 'in-use'},
      { timestamp: 1289, status: 'reset'},
      { timestamp: 1293, status: 'open'}
    ]
  },
  …
];
function index(arr, compare) { // binary search, with custom compare function
    var l = 0,
        r = arr.length - 1;
    while (l <= r) {
        var m = l + ((r - l) >> 1);
        var comp = compare(arr[m]);
        if (comp < 0) // arr[m] comes before the element
            l = m + 1;
        else if (comp > 0) // arr[m] comes after the element
            r = m - 1;
        else // this[m] equals the element
            return m;
    }
    return l-1; // return the index of the next left item
                // usually you would just return -1 in case nothing is found
}
// example:
function insertItem(history, timestamp, status) {
    var i = index(history, function(item) {
        return item.timestamp - timestamp;
    });
    history.splice(i+1, 0, {timestamp: timestamp, status: status});
}

function getStatus(time) {
    var result = {};
    function comparefn (item) {
        return item.timestamp - time;
    }
    for (var i=0; i<items.length; i++) {
        var pos = index(items[i].history, comparefn);
        result[items[i].id] = pos == -1
          ? undefined
          : items[i].history[pos].status;
    }
    return result;
}

这篇关于如何构造特定于时间的数据以便可以找到最近的点?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！