The need (context).
Several times a day, we need to migrate a set of digital assets from one system to another. The process uses memory (the assets are held in memory for a short time) and we need to do our best to keep the memory capacity down. Fortunately, we have some flexibility (there is no hard ceiling) but there is a noticeable performance improvement if we keep our migration to about 50Mb of assets at a time.
Each migration consists of about 15,000 digital assets, ranging from a hundred bytes or so, up to well over 50Mb (but very rarely). A typical (std) distribution of our assets has a mean (μ) of 213777.0 and a standard deviation (σ) of 1591525.0 - this isn't very accurate - (there's a slight pull towards the low end and then a few very big assets), but it's good enough.
Each asset has a unique id and, along with some other metadata, we have its size available to us. Although we could use an 'asset' struct, for flexibility sake (and because I am unused to templates), I chose to use a pair<size_t,size_t> to represent each asset - the first being the id, the second being the actual size of the asset. (size_t is suitable for both the id and the asset size). I know structs would be more suitable, and will make the change as suggested below.
Therefore, it seemed reasonable (still does) to use a bin-packing solution (a 1-D knapsack-problem).
The criteria of assessment.
The calculation speed of the bin-packing solution is not very important (we are looking at only 15k assets), and neither is a terribly optimal solution. The primary criterion was ease of understanding, and ease of use. Some of our juniors have never heard of bin-packing, and finding a reasonably easy to read method with few lines is more important than a very generalised, maximally optimal, super-fast solution.
Wikipedia, StackOverflow, and Google are always the first places to look, of course; and bin-packing is a very well-addressed area.
From these, I found the code by Bastian Rieck on his bin-packing GitHub repo, specifically the max_rest_pq function that uses a priority queue.
While it worked fine, I am not familiar with std::priority_queue, and likewise, it seemed only to store the size of each bin, not the contents of each bin. I chose to use pair size_t/size_t for asset-id/weight - I'm not so good at templates, but structs will probably be used in the deployed solution.
Instead, I chose to replace Bastian's use of a std::priority_queue with a std::multimap, by exploiting its lower_bound() method (The map's key here represents space available, not size of current fill). Likewise, using extract()/insert() instead of pop()/push() found in std::priority_queue.
Why I asked this question.
While I may be an experienced programmer, I am not a good programmer. I'm looking to improve on the solution I wrote.
It seems to work well against than many other (more complex, lengthy)
algorithms solutions, but maybe it's no good.