Circle data structures to implement sequential allocations in Julia

Hi. I need to implement a simple task, which is to choose the available (means it is currently un-used) server from a bunch of given servers based on a sequential ordering, i.e., the server which has not been used for the longest time will be chosen. I think this should be a common / general task. I was wondering, what would be a good data structure for this? What would be better? A priority queue or is there any circular data structure available in Julia for this task?

If you’re choosing servers, that implies that distributed overheads are involved which means that efficiency pretty much doesn’t matter. Keeping an index into a vector of servers and wrapping around at the vector length would work just fine.

3 Likes

While I do agree with you, @StefanKarpinski, @bsnyh has not mentioned performance at any point, it can be that @bsnyh is just looking for a data structure that does the job (has the methods for doing so with minimal implementation effort and maximum readability).

Also, if for some reason the distinction between “the server that has not received a job for the longest time (i.e., time since last task start)” and “the server that has been idle for the longest time (i.e., time since last task finish)” is relevant, and what is wanted is the second case (server idle for the longest time), then wrapping an index actually may give the wrong answer.

The DataStructures package has priority queues, heaps (that are one of the structures to implementing a priority queue) and circular buffers and deque. If you need both iteration in order as access by key, the selection of Sorted Containers may interest you.

2 Likes