Algorithm...
กก
#include <vector>
#include <set>
#include <stdio.h>
#include <stdlib.h>
// the mutable definition is because we want to modify the set iterator directly
// I don't want to remove and insert as the position in sorted seq is not changed.
struct FrameIndexRenderMinute
{
int index;
mutable int minute;
};
struct FrameIndexRenderMinuteCompByMinute
{
bool operator()(const FrameIndexRenderMinute& left, const FrameIndexRenderMinute& right) const
{
return left.minute < right.minute;
}
};
struct FrameIndexRenderMinuteCompByIndex
{
bool operator()(const FrameIndexRenderMinute& left, const FrameIndexRenderMinute& right) const
{
return left.index < right.index;
}
};
// this set sorted by render minute
typedef std::set<FrameIndexRenderMinute, FrameIndexRenderMinuteCompByMinute> RenderJobSet;
// this set sorted by frame index
typedef std::set<FrameIndexRenderMinute, FrameIndexRenderMinuteCompByIndex> RenderJobSequenceSet;
typedef std::vector<FrameIndexRenderMinute> RenderJobVector;
typedef std::vector<RenderJobVector> RenderJobVectorVector; // the slot represents hourly jobs assignment
class RenderJobDispatch
{
private:
void applyFinishedJobSet(RenderJobSet& renderJobSet, RenderJobVector& finishedJobVector)
{
// to do, remove finished job set from renderJobSet
// also adjust job's render minute by the distance relative to finished job frame index
int i;
RenderJobSequenceSet dstSeqSet;
RenderJobSequenceSet srcSeqSet;
// we create two set sorted by frame index
for (i = 0; i < finishedJobVector.size(); i ++)
{
srcSeqSet.insert(finishedJobVector[i]);
}
for (RenderJobSet::iterator jobit = renderJobSet.begin(); jobit != renderJobSet.end(); jobit ++)
{
dstSeqSet.insert(*jobit);
}
// now we remove the finished jobs
for (i = 0; i < finishedJobVector.size(); i ++)
{
srcSeqSet.insert(finishedJobVector[i]);
dstSeqSet.erase(finishedJobVector[i]);
}
// we now need to adjust remain jobs' estimated render minute according to finished render minute
// this is done by the average according to its frame index
for (RenderJobSequenceSet::iterator it = dstSeqSet.begin(); it != dstSeqSet.end(); it ++)
{
RenderJobSequenceSet::iterator loIt, upIt;
loIt = srcSeqSet.lower_bound(*it);
upIt = srcSeqSet.upper_bound(*it);
// get average render time relative to how close it is to up/lo bound
int loDistance, upDistance;
if (loIt == srcSeqSet.end())
{
loDistance = 0;
}
else
{
loDistance = it->index - loIt->index;
}
if (upIt == srcSeqSet.end())
{
upDistance = 0;
}
else
{
upDistance = upIt->index - it->index;
}
int totalDistance = loDistance + upDistance;
if (totalDistance != 0)
{
int newMinute = (loIt->minute*loDistance + upIt->minute*upDistance)/totalDistance;
it->minute = newMinute;
//renderJobSet.begin()->minute = 0;
}
}
// now, we need to write back the parameter
renderJobSet.clear();
RenderJobSequenceSet::iterator setIt;
for (setIt = dstSeqSet.begin(); setIt != dstSeqSet.end(); setIt ++)
{
renderJobSet.insert(*setIt);
}
finishedJobVector.clear();
for (setIt = srcSeqSet.begin(); setIt != srcSeqSet.end(); setIt ++)
{
finishedJobVector.push_back(*setIt);
}
}
int findMaxFitSlot(RenderJobSet jobSubSet, int nLeftMinute, RenderJobVector& renderJobVector)
{
if (jobSubSet.empty())
{
// no need to update renderJobSlot
return nLeftMinute;
}
int nMinLeftMinute;
nMinLeftMinute = nLeftMinute;
// and we know it is not empty
RenderJobSet::iterator theFirst = jobSubSet.begin();
// initialize the parameter
int nNextLeftMinute = nLeftMinute - theFirst->minute;
if (nNextLeftMinute < 0)
{
return nLeftMinute;
}
renderJobVector.push_back(*theFirst);
RenderJobVector tempJobVector, minJobVector;
// copy the original result and add our first job at back
minJobVector.assign(renderJobVector.begin(), renderJobVector.end());
//tempJobVector.push_back(*theFirst);
RenderJobSet nextRenderJobSet;
// we can do this because jobSubSet is not empty
theFirst ++;
RenderJobSet::iterator it;
for (it = theFirst; it != jobSubSet.end(); ++ it)
{
nextRenderJobSet.insert(*it);
}
// next we iterate and try to find the minLeftMinute recursively
for (it = theFirst; it != jobSubSet.end(); it ++)
{
// push stack
tempJobVector.assign(renderJobVector.begin(), renderJobVector.end());
int nTempLeftMinute = findMaxFitSlot(nextRenderJobSet, nNextLeftMinute, tempJobVector);
if (nTempLeftMinute >= 0 && nTempLeftMinute < nMinLeftMinute)
{
nMinLeftMinute = nTempLeftMinute;
minJobVector.assign(tempJobVector.begin(), tempJobVector.end());
}
// remove stack
//renderJobVector.pop_back();
}
// this is what we find, or possible nothing changed
renderJobVector.assign(minJobVector.begin(), minJobVector.end());
return nMinLeftMinute;
}
public:
RenderJobVectorVector Dispatch(RenderJobSet renderJobSet, RenderJobVector& finishedJobVector, int nMaxMinute)
{
applyFinishedJobSet(renderJobSet, finishedJobVector);
RenderJobVectorVector result;
int nLeftMinute = nMaxMinute;
RenderJobVector renderJobVector;
do
{
nLeftMinute = findMaxFitSlot(renderJobSet, nMaxMinute, renderJobVector);
if (renderJobVector.empty())
{
// cannot find any more fit job slot assignment, just quit
break;
}
result.push_back(renderJobVector);
for (int i = 0; i < renderJobVector.size(); i ++)
{
renderJobSet.erase(renderJobVector[i]);
}
renderJobVector.clear();
}
while (true);
return result;
}
};
int main()
{
const int MaxJobNumber = 30;
RenderJobDispatch dispatch;
RenderJobSet renderJobSet;
RenderJobVector finishedJobVector;
RenderJobVectorVector result;
for (int i = 0; i < MaxJobNumber; i ++)
{
FrameIndexRenderMinute node;
node.index = i;
node.minute = rand()%30 + 20;
renderJobSet.insert(node);
printf("job:index=%d, minute=%d\n", node.index,node.minute);
}
do
{
result = dispatch.Dispatch(renderJobSet, finishedJobVector, 120);
if (result.size() == 0)
{
break;
}
// got a new job slot and
// do rendering, assume we just finish one slot of job every time
// rendering...
// finished one slot and insert into the finished job slot
printf("\n...rendering...\n");
printf("finished job is...\n");
for (int i = 0; i < result[0].size(); i ++)
{
printf("index=%d,minute=%d\n", result[0][i].index, result[0][i].minute);
finishedJobVector.push_back(result[0][i]);
}
}
while (true);
return 0;
}
////////////////////////////////////////////////////////////////////////////////
// second version fix some bugs and add greedy algorithm as recursion is useless when job queue is bigger than 50 or something.
#include <vector>
#include <set>
#include <stdio.h>
#include <stdlib.h>
// the mutable definition is because we want to modify the set iterator directly
// I don't want to remove and insert as the position in sorted seq is not changed.
struct FrameIndexRenderMinute
{
int index;
mutable int minute;
};
struct FrameIndexRenderMinuteCompByMinute
{
bool operator()(const FrameIndexRenderMinute& left, const FrameIndexRenderMinute& right) const
{
if (left.minute != right.minute)
{
return left.minute < right.minute;
}
else
{
return left.index < right.index;
}
}
};
struct FrameIndexRenderMinuteCompByIndex
{
bool operator()(const FrameIndexRenderMinute& left, const FrameIndexRenderMinute& right) const
{
return left.index < right.index;
}
};
// this set sorted by render minute
typedef std::set<FrameIndexRenderMinute, FrameIndexRenderMinuteCompByMinute> RenderJobSet;
// this set sorted by frame index
typedef std::set<FrameIndexRenderMinute, FrameIndexRenderMinuteCompByIndex> RenderJobSequenceSet;
typedef std::vector<FrameIndexRenderMinute> RenderJobVector;
typedef std::vector<RenderJobVector> RenderJobVectorVector; // the slot represents hourly jobs assignment
class RenderJobDispatch
{
public:
void applyFinishedJobSet(RenderJobSet& renderJobSet, RenderJobVector& finishedJobVector)
{
// to do, remove finished job set from renderJobSet
// also adjust job's render minute by the distance relative to finished job frame index
int i;
RenderJobSequenceSet renderSeqSet;
RenderJobSequenceSet finishedSeqSet;
// we create two set sorted by frame index
for (i = 0; i < finishedJobVector.size(); i ++)
{
finishedSeqSet.insert(finishedJobVector[i]);
}
for (RenderJobSet::iterator jobit = renderJobSet.begin(); jobit != renderJobSet.end(); jobit ++)
{
renderSeqSet.insert(*jobit);
}
// now we remove the finished jobs
for (i = 0; i < finishedJobVector.size(); i ++)
{
//srcSeqSet.insert(finishedJobVector[i]);
renderSeqSet.erase(finishedJobVector[i]);
}
// clear it now, so we insert new updated jobs
renderJobSet.clear();
// we now need to adjust remain jobs' estimated render minute according to finished render minute
// this is done by the average according to its frame index
for (RenderJobSequenceSet::iterator it = renderSeqSet.begin(); it != renderSeqSet.end(); it ++)
{
RenderJobSequenceSet::iterator loIt, upIt;
loIt = finishedSeqSet.lower_bound(*it);
upIt = finishedSeqSet.upper_bound(*it);
// get average render time relative to how close it is to up/lo bound
int loDistance, upDistance;
if (loIt == finishedSeqSet.end())
{
loDistance = 0;
}
else
{
loDistance = it->index - loIt->index;
}
if (upIt == finishedSeqSet.end())
{
upDistance = 0;
}
else
{
upDistance = upIt->index - it->index;
}
FrameIndexRenderMinute node;
int totalDistance = loDistance + upDistance;
int newMinute;
if (totalDistance != 0)
{
newMinute = (loIt->minute*loDistance + upIt->minute*upDistance)/totalDistance;
//it->minute = newMinute;
//renderJobSet.begin()->minute = 0;
}
else
{
newMinute = it->minute;
}
node.minute = newMinute;
node.index = it->index;
renderJobSet.insert(node);
}
}
private:
int findMaxFitSlot(RenderJobSet jobSubSet, int nLeftMinute, RenderJobVector& renderJobVector)
{
return findMaxFitslotByGreedy(jobSubSet, nLeftMinute, renderJobVector);
}
int findMaxFitslotByGreedy(RenderJobSet jobSubSet, int nLeftMinute, RenderJobVector& renderJobVector)
{
if (jobSubSet.empty())
{
// no need to update renderJobSlot
return nLeftMinute;
}
int nNextLeftMinute = nLeftMinute;
// and we know it is not empty
RenderJobSet::iterator theFirst;
for (theFirst = jobSubSet.begin(); theFirst != jobSubSet.end(); theFirst ++)
{
// initialize the parameter
int nTempNextLeftMin = nNextLeftMinute - theFirst->minute;
if (nTempNextLeftMin == 0)
{
// we cannot expect anything better
renderJobVector.push_back(*theFirst);
return 0;
}
else
{
if (nTempNextLeftMin >= theFirst->minute)
{
//still possible for more
renderJobVector.push_back(*theFirst);
nNextLeftMinute = nTempNextLeftMin;
}
else
{
//it is time for us to search backward;
break;
}
}
}
if (theFirst == jobSubSet.end())
{
return nNextLeftMinute;
}
//
if (nNextLeftMinute < theFirst->minute)
{
if (!renderJobVector.empty())
{
nNextLeftMinute += renderJobVector[renderJobVector.size() - 1].minute;
renderJobVector.pop_back();
}
else
{
return nNextLeftMinute;
}
}
FrameIndexRenderMinute node = *theFirst;
int nMinLeftMinute = nNextLeftMinute;
for (RenderJobSet::reverse_iterator it = jobSubSet.rbegin(); it != jobSubSet.rend(); it ++)
{
if (nNextLeftMinute >= it->minute)
{
renderJobVector.push_back(*it);
return nNextLeftMinute - it->minute;
}
}
return nMinLeftMinute;
}
int findMaxFitSlotByRecursion(RenderJobSet jobSubSet, int nLeftMinute, RenderJobVector& renderJobVector)
{
if (jobSubSet.empty())
{
// no need to update renderJobSlot
return nLeftMinute;
}
int nMinLeftMinute;
nMinLeftMinute = nLeftMinute;
RenderJobVector minJobVector;
minJobVector.assign(renderJobVector.begin(), renderJobVector.end());
// and we know it is not empty
for (RenderJobSet::iterator theFirst = jobSubSet.begin(); theFirst != jobSubSet.end(); theFirst ++)
{
// initialize the parameter
int nNextLeftMinute = nLeftMinute - theFirst->minute;
if (nNextLeftMinute < 0)
{
//we deliberately want to return negative to indicate there is no need to continue as our
// job queue is sorted.
return nNextLeftMinute;
}
RenderJobSet nextRenderJobSet;
RenderJobSet::iterator it = theFirst;
// we can do this because jobSubSet is not empty
for (it ++ ; it != jobSubSet.end(); ++ it)
{
nextRenderJobSet.insert(*it);
}
RenderJobVector tempJobVector;
// copy the original result and add our first job at back
tempJobVector.assign(renderJobVector.begin(), renderJobVector.end());
tempJobVector.push_back(*theFirst);
int nTempLeftMinute = findMaxFitSlot(nextRenderJobSet, nNextLeftMinute, tempJobVector);
if (nTempLeftMinute >= 0 && nTempLeftMinute < nMinLeftMinute)
{
nMinLeftMinute = nTempLeftMinute;
minJobVector.assign(tempJobVector.begin(), tempJobVector.end());
}
if (nTempLeftMinute < 0)
{
// we know there is no chance for any try further
//nMinLeftMinute = nTempLeftMinute;
break;
}
// remove stack
//renderJobVector.pop_back();
}
// this is what we find, or possible nothing changed
renderJobVector.assign(minJobVector.begin(), minJobVector.end());
return nMinLeftMinute;
}
public:
void printRenderJobSet(RenderJobSet& jobSet)
{
for (RenderJobSet::iterator it = jobSet.begin(); it != jobSet.end(); it ++)
{
printf("job: frameIndex=%d,renderMinute=%d\n", it->index, it->minute);
}
}
RenderJobVectorVector Dispatch(RenderJobSet renderJobSet, RenderJobVector& finishedJobVector, int nMaxMinute)
{
applyFinishedJobSet(renderJobSet, finishedJobVector);
RenderJobVectorVector result;
int nLeftMinute = nMaxMinute;
RenderJobVector renderJobVector;
do
{
nLeftMinute = findMaxFitSlot(renderJobSet, nMaxMinute, renderJobVector);
if (renderJobVector.empty())
{
// cannot find any more fit job slot assignment, just quit
break;
}
result.push_back(renderJobVector);
for (int i = 0; i < renderJobVector.size(); i ++)
{
renderJobSet.erase(renderJobVector[i]);
}
renderJobVector.clear();
}
while (true);
// let's print the unsolved jobs
printf("the rest unassigned jobs are:\n");
printRenderJobSet(renderJobSet);
return result;
}
};
int main()
{
const int MaxJobNumber = 3000;
const int MaxAllowedMinute = 240;
RenderJobDispatch dispatch;
RenderJobSet renderJobSet;
RenderJobVector finishedJobVector;
RenderJobVectorVector result;
for (int i = 0; i < MaxJobNumber; i ++)
{
FrameIndexRenderMinute node;
node.index = i;
node.minute = rand()%30 + 20;
renderJobSet.insert(node);
printf("job:index=%d, minute=%d\n", node.index,node.minute);
}
int counter = 0;
printf("before starting:\n//////////////////////////////////////\n");
dispatch.printRenderJobSet(renderJobSet);
printf("\n\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\n");
do
{
dispatch.applyFinishedJobSet(renderJobSet, finishedJobVector);
/*
printf("before pass %d, the job set is:\n//////////////////////////////////////\n", counter++);
dispatch.printRenderJobSet(renderJobSet);
printf("\n\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\n");
*/
result = dispatch.Dispatch(renderJobSet, finishedJobVector, MaxAllowedMinute);
if (result.size() == 0)
{
break;
}
// got a new job slot and
// do rendering, assume we just finish one slot of job every time
// rendering...
// finished one slot and insert into the finished job slot
printf("\n...rendering...\n");
printf("finished job is...\n");
int total = 0;
for (int i = 0; i < result[0].size(); i ++)
{
total += result[0][i].minute;
printf("index=%d,minute=%d\n", result[0][i].index, result[0][i].minute);
finishedJobVector.push_back(result[0][i]);
}
printf("this job slot has %d minute left based on maximum minute %d allowed\n", MaxAllowedMinute - total, MaxAllowedMinute);
}
while (true);
return 0;
}
กก
กก