根据值从数组中选取 JSON 个对象

Question

也许我的想法是错误的，但是这里有一个问题：

我的 NSMutableArray 中全是 JSON 个对象。每个对象看起来像这样，例如这里有 2 个：

{
player = "Lorenz";
speed = "12.12";
},
 {
player = "Firmino";
speed = "15.35";
}

好的，这很好，这是我从网络服务器提要中获得的动态信息。现在我想要的是假设有 22 个这样的条目，并且速度会有所不同。

我想要一个从 1.0 秒开始到 60.0 秒的计时器，并且每秒几次我希望它抓住所有速度刚刚超过的玩家。因此，例如，如果计时器在 12.0 时关闭，然后在 12.5 时再次关闭，我希望它能够抓取速度在 12.0 和 12.5 之间的所有玩家名称，你明白吗？

显而易见的简单方法是每次计时器关闭时完全遍历数组，但我希望计时器关闭很多次，比如每秒 10 次或更多，所以这将是我认为相当浪费的算法。有更好的主意吗？我可以尝试改变数据来自网络服务器的方式，但我觉得没有必要。

Answer 1

注意：经过编辑以反映更正的理解，即 1 到 60 中的数字在该范围内连续递增，而不是该区间内的随机数。

在进入定时器循环之前，你应该做一些常见的预处理：

预先将速度从字符串转换为数值以进行快速比较，而无需每次都进行解析。这是每个项目的 O(1) 和处理所有项目的 O(n)。
将数据放在一个有序的容器中，例如排序列表或排序二叉树。这将使您可以轻松地找到目标范围内的元素。这是对所有项目进行排序的 O(n log n)。

第一次迭代：

使用二进制搜索找到起始索引。这是 O(log n)。
使用二分查找查找结束索引，使用起始索引限定查找。

在后续迭代中：

如果每次迭代增加一个可预测的量并且列表中元素之间的步长同样是一个可预测的量，那么只需维护一个指针并按照 Pete 的评论递增。这将使每次迭代的成本为 O(1)（仅向前推进固定数量）。
如果迭代之间的步骤 and/or 列表中的条目是不可预测的，那么在初始情况下进行二进制搜索。如果这些值是单调递增的（正如我现在理解要说明的问题），即使它们是不可预测的，您也可以通过维护索引将其合并到您的二进制搜索算法中，就像在其他情况下一样，而不是直接从恢复迭代在那里，如果值是不可预测的，则使用记住的索引来设置二进制搜索的下限，以便缩小搜索区域。这将使每次迭代成本为 O(log m)，其中 "m" 是要考虑的剩余元素。

总的来说，这产生了一个不比 O((N + I) log N) 差的算法，其中 "I" 是与之前的 O(I * N) 算法相比的迭代次数（并将大部分计算转移到循环外，而不是循环内）。

Answer 2

现代计算机每秒可以进行数十亿次操作。即使您的计时器每秒响起 1000 次，并且您需要处理 1000 个条目，您仍然可以采用幼稚的方法。

但要回答这个问题，最好的方法是先根据速度对数据进行排序，然后对最后一个速度超过的玩家进行索引。显然，一开始指针指向第一个玩家。然后每次你的计时器关闭时，你将需要处理从该索引开始的一些连续的玩家块。类似于（伪代码）：

global index = 0;
sort(players); // sort on speed
onTimer = function(currentSpeed) {
    while (index < players.length && players[index].speed < currentSpeed) {
        processPlayer(players[index]);
        ++ index;
    }
}

根据值从数组中选取 JSON 个对象

Picking JSON objects out of array based on their value

sorting

algorithm

json

nsarray