From 8d4ea0bb9cdda4021c54ed564382b89ddec8c800 Mon Sep 17 00:00:00 2001 From: Holden Rohrer Date: Thu, 16 Jan 2020 23:21:15 -0500 Subject: added explanation for schedule architecture --- architecture | 21 +++++++++++++++++++++ 1 file changed, 21 insertions(+) create mode 100644 architecture diff --git a/architecture b/architecture new file mode 100644 index 0000000..c161699 --- /dev/null +++ b/architecture @@ -0,0 +1,21 @@ +Say you have several queues A, B, ... +Each queue has a length K_n. +Each queue has a weight K_w. K_w adjusted such that \sumK_w=1 +If k items are requested, a set of items from the tops of each relevant queue will be returned. +K_c <= K_n items were chosen from queue K. +Minimize \sum|kK_w-K_c|. << Jesus Christ that's it. How could I be so stupid. + +main(queueList, num) -> while (not have num) getNumOrAll(queueList[top], remaining) + +getNumOrAll(queue, num): + Step 1: Make array of num*job.weight + Step 2: "Remove" all num%1 from array, and count + Step 3: "Sort" array by num. + Step 4: Continue counting. Subtract one from each array member until at num. +^^ Not perfect + Step 1: (Pre-)sort by job.data.length/job.weight. + Step 2: Start at lowest, and pop all until job.data.length>job.normweight*num (decreasing num as popping and recalc job.normweight). + Step 2.5: If empty, remove prio && jobs[prio]; return. + Step 3: Then, pop job.normweight*num//1 elems from remaining, without num decrease or normweight recalc. But keep job.wacc = job.normweight*num%1 + Step 4: Shallow copy job array, and sort by job.wacc. + Step 5: Iterate through array (high->low), and subtract 1 until the length of output is num. -- cgit