Timeline for How to classify simple priority queue algorithm
Current License: CC BY-SA 3.0
21 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| S Jan 21, 2017 at 10:34 | history | bounty ended | CommunityBot | ||
| S Jan 21, 2017 at 10:34 | history | notice removed | CommunityBot | ||
| Jan 20, 2017 at 11:11 | comment | added | D.W.♦ | What do you mean by "classifying" this algorithm? It's hard for me to tell what you are asking or what kind of answer you are looking for. Let me ask another way: What will do you with the answer? How do you plan to evaluate proposed answers? Incidentally, this is a good example why we recommend you ask only one question per post; you asked multiple questions (how to prove it is correct, whether starvation is possible, how to classify it), and received answers to some but not all of those. P.S. I suggest you flag any comments that are no longer relevant, and edit to address the remainder. | |
| Jan 20, 2017 at 9:20 | history | edited | Alexander Mills | CC BY-SA 3.0 |
added 20 characters in body
|
| Jan 15, 2017 at 9:47 | vote | accept | Alexander Mills | ||
| Jan 15, 2017 at 2:42 | vote | accept | Alexander Mills | ||
| Jan 15, 2017 at 9:47 | |||||
| Jan 13, 2017 at 22:48 | answer | added | D.W.♦ | timeline score: 2 | |
| Jan 13, 2017 at 22:16 | comment | added | D.W.♦ | Can you clarify some aspects of your proposed algorithm? 1. Step 5: "sort...by priority level" -- do you mean by increasing priority level (priority 1 items first, then priority 2 items, then priority 3), or by decreasing priority level? 2. "Sort... first by priority level, then by age" -- do you mean to sort by priority, but resolving ties using age? Or do you mean (a) sort the first 20 items by priority; then, (b) sort the first 20 items by age, using a stable sorting algorithm. The latter doesn't seem to make sense, as it seems like it is equivalent to not doing any sorting at all. | |
| S Jan 13, 2017 at 19:37 | history | suggested | Harshdeep Sokhey | CC BY-SA 3.0 |
Removed irrelevant content in the question
|
| Jan 13, 2017 at 17:16 | answer | added | D.W.♦ | timeline score: 3 | |
| Jan 13, 2017 at 15:34 | review | Suggested edits | |||
| S Jan 13, 2017 at 19:37 | |||||
| S Jan 13, 2017 at 9:27 | history | bounty started | Alexander Mills | ||
| S Jan 13, 2017 at 9:27 | history | notice added | Alexander Mills | Authoritative reference needed | |
| Jan 11, 2017 at 9:05 | comment | added | Alexander Mills | AFAICT you can't have it both ways, you have to choose one sorting dimension over another dimension. and like I was saying, I think it's more important to eliminate starvation (liveness?), and less important to get high priority items off the queue quickly. | |
| Jan 11, 2017 at 9:02 | comment | added | Alexander Mills | well, re: the question of the sort, please see: stackoverflow.com/questions/41586024/… | |
| Jan 11, 2017 at 8:56 | comment | added | quicksort | I believe you should clarify what you are trying to achieve. From what you wrote, I gather you imply some form of liveness property, but I'm not exactly sure what it is and what the exact constraints are. Regarding the sorting, I don't see why you wouldn't be able to. You can certainly sort according to any order relation of your choice, that's what sorting algorithms do. | |
| Jan 11, 2017 at 8:36 | comment | added | Alexander Mills | The only problem/achilles heel I see for this algorithm is the sorting part - I have to make sure that the sorting which happens on two dimensions (priority and age of an item in the queue) does not consistently relegate certain items to the back of the subset of 20. So perhaps it's much better to put more weight on age and less weight on priority. | |
| Jan 11, 2017 at 8:23 | history | edited | Alexander Mills | CC BY-SA 3.0 |
added 12 characters in body
|
| Jan 11, 2017 at 0:07 | comment | added | Alexander Mills | The biggest question in my mind is actually if we can truly sort things in two dimensions - first sort by priority level, then sort by age. Not even sure if that's possible or how to do it! | |
| Jan 10, 2017 at 23:00 | review | First posts | |||
| Jan 11, 2017 at 7:45 | |||||
| Jan 10, 2017 at 22:58 | history | asked | Alexander Mills | CC BY-SA 3.0 |