Embargo algorithm

Anonymous Monk has asked for the wisdom of the Perl Monks concerning the following question:

I have a list of items from which I want to continously return a random item, but I need to embargo any returned item until the next top of the hour. This requirement is because I'm dealing with a webservice that resets it's rate limit at the top of the hour. And to deal with different server times, I also need to embargo any item returned before 5 minutes of the top of the hour until the top of the 2nd hour (ex. if the item was used at 14:55:01, it should be embargoed until 16:00).

Is there any existing datastructure or module that would make this easy to implement? I want to make this efficient as well, so I don't want to have to loop through all the items to find the next available one.

This is my first thought of how to implement this:

package List::ResetOnTheHour;

sub new {
    my $class = shift;
    my $self  = {
        list           => [@_],
        embargo_1_hour => [],
        embargo_2_hour => [],
        last_check     => 0,
    };
    return bless $self, $class;
}

sub next {
    my $self = shift;

    my $list = $self->{list};

    # compare last_check against time and push embargo_1_hour back
    # onto list if the top of the hour has passed. push embargo_2_hour
    # onto embargo_1_hour or list depending upon how much time has
    # passed.

    my $next = splice @$list, -1 + int rand @$list, 1;

    # if within 5 minutes of next top of hour, push onto
    #     embargo_2_hour,
    # else push onto embargo_1_hour

    return $next;
}

# This would be used instead of the constructor to add items when a
# last used time is already known, like when reading from a
# serialized state file on startup.
sub add {
    my ($self, $elem, $time) = @_;
    # add to list or embargo_X_hour depending on value of time.
}
[download]

Comment on Embargo algorithm Download Code

Replies are listed 'Best First'.
Re: Embargo algorithm by BrowserUk (Patriarch) on Oct 29, 2013 at 17:47 UTC
Use shuffle to randomise your list of things into an array (say @items); pop (or shift) the next item off @items each time you need one. When an item is used, it is also pushed onto a `@used` array Each time the clock reaches 5 minutes before the hour; shuffle the @used array with the remainder of the @items array into a temporary array; say @defered. And empty the @used array. Once the hour roles over; overwrite the current @items with @defered, and continue. With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday' Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error. "Science is about questioning the status quo. Questioning authority". In the absence of evidence, opinion is indistinguishable from prejudice.	[reply] [d/l]
Re: Embargo algorithm by atcroft (Abbot) on Oct 29, 2013 at 17:35 UTC
This may be a simplistic way of looking at it, but when I read your post, my first thought was to keep track of last "hour" the item was "returned", although in this case "hour" would be calculated as int( ( time + 300 ) / 3600 ) % 24. This would mean that anything from 3100 to 3599 (:55 to :59:59) as well as anything from 0 to 3099 (:00:00 to :54:59) will evaluate to the same hour. I had considered a while() loop, getting a random index and checking if the return "hour" and the current hour (UTC) matched. As I typed the paragraph above, however, I realized there was possibly a simpler way: maintain a pointer or index of the number of un-returned items this hour, pick your next item at random between 0 and this index, then swap the one picked and the value of the index, and decrement the index. So, for example, you have 10 items (0..9). Pick one at random (8), return it, then swap it and item 9, and decrement your max to 9. Pick another at random from 0..8, and so forth. I have no illusions that the two ideas above are the best, but they are ideas, and I hope they prove helpful.	[reply]
Re: Embargo algorithm by Not_a_Number (Prior) on Oct 29, 2013 at 21:15 UTC
This is how I'd do it (albeit without using OO Perl): `use List::Util 'shuffle'; my @bag = shuffle qw( A B C D E ); my @embargoed = pop @bag; while ( 1 ) { my $time = ( localtime )[ 0 ]; # seconds sleep 1; if ( $time >= 55 ) { push @embargoed, pop @bag; push @bag, shift @embargoed if @embargoed > 2; @bag = shuffle @bag; sleep 5; } print "$time @embargoed\n"; }` [download] NB: For testing porpoises, I've substituted seconds for minutes and minutes for hours. Adjusting this (including `sleep` times) is left as an excercise... Update: Simplified code (and explanation). Minutes don't matter!	[reply] [d/l] [select]