json - 根据值从数组中挑选 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

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

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

1. 预先将速度从字符串转换为数值以进行快速比较，而无需每次都进行解析。这是每个项目的 O(1) 和处理所有项目的 O(n)。

2. 将数据放入有序容器中，例如排序列表或排序二叉树。这将使您可以轻松地找到目标范围内的元素。这是对所有项目进行排序的 O(n log n)。

在第一次迭代时:

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

在后续迭代中:

• 如果每次迭代增加一个可预测的量并且列表中元素之间的步长同样是一个可预测的量，那么只需维护一个指针并按照 Pete 的评论递增。这将使每次迭代的成本为 O(1)(仅向前推进固定数量)。

• 如果迭代之间的步骤和/或列表中的条目不可预测，则按照初始情况进行二分搜索。如果这些值是单调递增的(正如我现在理解要说明的问题)，即使它们是不可预测的，您也可以通过维护索引将其合并到您的二进制搜索算法中，就像在其他情况下一样，而不是直接从恢复迭代在那里，如果值是不可预测的，则使用记住的索引来设置二进制搜索的下限，以便缩小搜索区域。这将使每次迭代的成本为 O(log m)，其中“m”是要考虑的剩余元素。

总的来说，这产生了一个不比 O((N + I) log N) 差的算法，其中“I”是与之前的 O(I * N) 算法相比的迭代次数(并且移动最多循环外的计算，而不是循环内的计算)。