I'm trying to order some data in real-time (in an API call) where my item count is on the order of a few million.
I'm using Go, so my pseudo code may resemble that. My input items look like this:
type Item struct {
// SetID is the set this item belongs to. This may be in the
// 100,000s in unique sets.
SetID int
// SetOrder is the position in the set relative to
// other items with the same SetID. There will be
// about 10s of items in the same set.
SetOrder int
// BucketID is the bucket this item belongs to.
// There are 10,000s of buckets.
BucketID int
}
I'm starting with an unordered list of Items. I'm trying to group the items into buckets with the same BucketID forming as few buckets as possible. It's fine if multiple buckets with the same ID exist if required to meet ordering restrictions. Buckets have an order, but that order is driven entirely by the item ordering restrictions.
Items with the SetID must follow the SetOrder within their set. So if an Item in SetID 1 with SetOrder 2 wants to be put in a bucket at the beginning of the bucket list, since there may already be a bucket with the right ID it could belong to, but there's already a bucket later in the list that has an Item in SetID 1 with SetOrder 1, that would cause the Items in the same set to be out of order relative to each other.
If it matters, items in the same set will never have a bucket in common.
I'll try to give a trivial example. I'll give the buckets letters for readability.
Starting with the items (1,1,A) (1,2,B) (2,1,B) (2,2,A)
I end up with an ordered list of buckets.
* A: (1,1)
* B: (1,2) (2,1)
* A: (2,2)
The last item in the list which is in set 2 wants to go in the existing A bucket at the beginning of the bucket list, but it can't, because there's already an item in set 2 that's ordered in front of it in bucket B.
Ultimately, I'm using this to generate a rule list for a 3rd party application that processes everything in a flat configuration to optimize configuration size and processing performance. It's more performant if I can group rules (SetID) with the same condition (Bucket) together, but without violating the ordering of conditions within the same rule.
