6 ms·
A few hours ago when reading the article I was also intrigued by the question and journeyed down a similar path regarding the moving window and the trade-offs.
by hughlomas 13y ago
A few hours ago when reading the article I was also intrigued by the question and journeyed down a similar path regarding the moving window and the trade-offs. After toying with a couple of improper solutions I came to a very similar conclusion. The basic idea being that each time increment() is called, you store the difference since the last increment, and to count you simply add up the offsets until you reach your desired time limit. Anyway I emailed myself the basic idea to post here later. There are probably some obvious optimizations but it satisfied me as a solution. Pseudocodish javascript example below:
var second = 100000000
, minute = second * 60
, hour = minute * 60
, day = hour * 24
, current = 0
, lastIncrement = 0
, increments = [];
function increment(){
current = timer.time();
increments.push( current - lastIncrement );
lastIncrement = current;
}
function getCountInLastSecond(){
var copy = increments.slice()
, total = 0
, count = 0;
while( ( total <= second ) && ( amount = copy.pop() ) ){
total += amount;
count++;
}
return count;
}
- abalone 13y agoYour array will grow indefinitely. Not a viable solution, it seems to me. Incidentally someone else posted a round robin database solution. It's probably the way to go. That's more or less where I was headed with quantizing offsets.
- hughlomas 13y agoWell to be pedantic it will grow, at worst, to (24 * 60 * 60 * 1000000000), if you are calling increment() every individual nanosecond. Though you are right that it is ignoring realistic memory issues. I was approaching it more as a thought exercise to address the moving window.
- abalone 13y agoNo, that's just the maximum possible in a single day.
- hughlomas 13y agoIt seemed obvious to me that you would trim it if it became larger because the most it asks for is the count of a single day. However, now that I think about it increment() could called multiple times during a single nanosecond, in which case I guess it would be multiplied by whatever the maximum number of executions per nanosecond would be. My once per nanosecond comment earlier was an erroneous assumption.
- abalone 13y agoYour bigger problem is with this "trim the array" idea, which is definitely not an obvious solution. The way you've coded it you'd have to tally almost the entire days worth of deltas just to determine the trim point. And you may still exceed that single-day max memory, because you'd accumulate overruns in between trims. I'll leave you to think about that one. (Hint: google round robin database. You know, the solution that I mentioned.)
- hughlomas 13y agoMy comments, as mentioned, were ignoring real memory constraints. I don't know why you feel the need to come off as frustrated.
- bjterry 13y agoInterestingly, based on the explanation at [1] round robin databases actually don't precisely solve the question as described in the article. It sacrifices precision for larger increments, and the author was looking for an exact algorithm. 1: http://jawnsy.wordpress.com/2010/01/08/round-robin-databases/ http://jawnsy.wordpress.com/2010/01/08/round-robin-databases...