1

Perhaps I think about this wrong, but here is a problem:

I have NSMutableArray all full of JSON objects. Each object look like this, here are 2 of them for example:

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

Okay so this is fine, this is dynamic info I get from webserver feed. Now what I want though is lets pretend there are 22 such entries, and the speeds vary.

I want to have a timer going that starts at 1.0 seconds and goes to 60.0 seconds, and a few times a second I want it to grab all the players whose speed has just been passed. So for instance if the timer goes off at 12.0 , and then goes off again at 12.5, I want it to grab out all the player names who are between 12.0 and 12.5 in speed, you see?

The obvious easy way would be to iterate over the array completely every time that the timer goes off, but I would like the timer to go off a LOT, like 10 times a second or more, so that would be a fairly wasteful algorithm I think. Any better ideas? I could attempt to alter the way data comes from the webserver but don't feel that should be necessary.

Improve this question

2 Answers 2

Reset to default
2

NOTE: edited to reflect a corrected understanding that the number in 1 to 60 is incremented continously across that range rather than being a random number in that interval.

Before you enter the timer loop, you should do some common preprocessing:

  1. Convert the speeds from strings to numeric values upfront for fast comparison without having to parse each time. This is O(1) for each item and O(n) to process all the items.

  2. Put the data in an ordered container such as a sorted list or sorted binary tree. This will allow you to easily find elements in the target range. This is O(n log n) to sort all the items.

On the first iteration:

  • Use binary search to find the start index. This is O(log n).
  • Use binary search to find the end index, using the start index to bound the search.

On subsequent iterations:

  • If each iteration increases by a predictable amount and the step between elements in the list is likewise a predictable amount, then just maintain a pointer and increment as per Pete's comment. This would make each iteration cost O(1) (just stepping ahead by a fixed amount).

  • If the steps between iterations and/or the entries in the list are not predictable, then do a binary search as in the initial case. If the values are monotonically increasing (as I now understand the problem to be stating), even if they are unpredictable, you can incorporate this into your binary search algorithm by maintaining an index as in the other case, but instead of resuming iteration directly from there, if the values are unpredictable, instead use the remembered index to set a lower bound on the binary search so that you narrow the region being searched. This would make each iteration cost O(log m), where "m" are the remaining elements to be considered.

Overall, this produces an algorithm that is no worse than O((N + I) log N) where "I" is the number of iterations compared to the previous algorithm that was O(I * N) (and shifts most of the computation outside of the loop, rather than inside the loop).

Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

If you keep hold of the index in your sorted list, then you know the index of the next item which to find when the next limit is passed, so no binary search is required.
Thanks, Pete. I slightly misunderstood the question. That approach works assuming that the elements and input number are incrementing in a predictable fashion, but -- if not -- wouldn't that still be O(n) in the worst case (if you had to increment all the way to the end? given that you don't know the fixed amount by which to jump ahead?). I've updated the answer to incorporate your suggestion, though, with slight modification.
If you're grabbing all the players between 12 and 12.5 as the OP example gives, they you just increment from your index which was at the player not less than 12 until you find a player not less than 12.5; if the OP wants all the players in the range rather the first and last in the range, you have to iterate over them anyway.
What if 20 of the 22 entries are between 12 and 12.5? Using binary search bounds the time to find the upper end of that interval. For a larger instance of the problem, you could spend O(n) time with direct iteration. You're right that printing out all of the entries in that range would be O(n), anyway, but returning a subview that simply references the array and includes the start_index and end_index would be a superior option, especially if the OP later used it for a computation that doesn't require iterating over all entries (like finding the median time in that subrange).
Yes, in the case that the OP wants the first and last in the range rather than iterating all in the range then binary search would be better.
2

A modern computer can do billions of operations per second. Even if your timer goes off 1000 times per second, and your need to process 1000 entries, you will still be fine with a naive approach.

But to answer the question, the best approach would be to sort the data first based on speed, and then have an index of the last player whose speed was already passed. At the beginning the pointer, obviously, points at the first player. Then every time your timer goes off, you will need to process some continuous chunk of players starting at that index. Something along the lines of (in pseudocode):

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

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.