根据它们的值挑选JSON对象阵列

也许我认为这个错误，但是这里有一个问题：根据它们的值挑选JSON对象阵列

我有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次或更多次的速度完成，这样会很公平我认为浪费的算法。任何更好的想法？我可以尝试改变数据来自Web服务器的方式，但不认为这是必要的。

来源

2015-07-10 Cocorico

注意：编辑以反映正确认识到1至60中的数字在该范围内连续增加，而不是该间隔中的随机数。

在你进入计时圈，你应该做一些共同预处理：

从字符串到前期的快速比较的数值转换速度，而不必每次进行解析。这是每个项目的O（1）和O（n）来处理所有项目。
将数据放入有序容器中，如排序列表或排序后的二叉树。这将使您可以轻松找到目标范围内的元素。这是O（n日志n）排序所有项目。

在第一次迭代：

使用二进制搜索来查找开始索引。这是O（log n）。
使用二进制搜索来查找结束索引，使用开始索引来限制搜索。

在随后的迭代中：

如果通过可预测的量，并且在列表中的元素之间的步骤每次迭代增加同样是可预测的量，那么就维持一个指针和增量按Pete的评论。这将使每次迭代的成本为O（1）（只是按照固定的数量前进）。
如果迭代之间的步骤和/或列表中的条目不可预测，那么按照初始情况进行二分搜索。如果值单调增加（因为我现在明白要说明的问题），即使它们是不可预知的，也可以通过在另一种情况下维护索引来将其合并到二进制搜索算法中，而不是直接从在那里，如果这些值是不可预知的，则应使用记忆索引来设置二分搜索的下限，以缩小搜索区域的范围。这将使每次迭代花费O（log m），其中“m”是要考虑的其余元素。

总之，这产生了一种算法，不大于O（（N + I）日志N），其中“I”是相比以前算法，这是O（I * N）的迭代次数更糟（并且将大部分计算转移到循环之外，而不是在循环内部）。

来源

2015-07-10 04:42:28

如果保留指数保持在你的排序列表，那么你就知道下一个项目时，下一个限制是通过其中找到的指数，所以没有二进制搜索是必需的。 –

谢谢，皮特。我稍微误解了这个问题。该方法假设元素和输入数字以可预测的方式递增，但是 - 如果不是 - 在最坏的情况下不会是O（n）（如果必须一直增加到最后假设你不知道前进的固定金额？）。我已经更新了答案，以纳入您的建议，但稍作修改。 –

如果你按照OP的例子抓住12到12.5之间的所有球员，他们只是从你的索引增加到不少于12的球员，直到你找到一个不低于12.5的球员;如果OP想要范围内的所有玩家而不是范围内的第一个和最后一个玩家，那么无论如何你都必须迭代它们。 –

一台现代计算机每秒可以完成数十亿次操作。即使您的计时器每秒钟停止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; 
    } 
}

来源

2015-07-10 05:46:10 Ishamael

根据它们的值挑选JSON对象阵列

回答

相关问题