0
$\begingroup$

I'm reading the The Algorithm Design Manual book on Data Structures and it says the following about FIFO and LIFO containers:

Support retrieval in first in, first out (FIFO) order. This is surely the fairest way to control waiting times for services. You want the container holding jobs to be processed in FIFO order to minimize the maximum time spent waiting. Note that the average waiting time will be the same regardless of whether FIFO or LIFO is used. Many computing applications involve data items with infinite patience, which renders the question of maximum waiting time moot.

Can someone please explain what is meant by minimizing maximum time spent waiting and why the waiting time is same for FIFO and LIFO?

Thanks

$\endgroup$
2
$\begingroup$

Maybe an example will help, consider lets say for 3 minutes we add 2 tasks each minute, and we process 1 task a minute. With a FIFO queue the timeline will be:

  • t(0): 'a' and 'b' added: [a, b] - 'a' processed after waiting $0$ - [b]
  • t(1): 'c' and 'd' added: [b, c, d] - 'b' processed after waiting $1$ - [c, d]
  • t(2): 'e' and 'f' added: [c, d, e, f] - 'c' processed after waiting $1$ - [d, e, f]
  • t(3): [d, e, f] - 'd' processed after waiting $2$ - [e, f]
  • t(4): [e, f] - 'e' processed after waiting $2$ - [f]
  • t(5): [f] - 'f' processed after waiting $3$ - []

Average wait time: $(0 + 1 + 1 + 2 + 2 + 3) / 6 = 1.5$, longest wait time: $3$

Then consider a LIFO stack:

  • t(0): 'a' and 'b' added: [a, b] - 'b' processed after waiting $0$ - [a]
  • t(1): 'c' and 'd' added: [a, c, d] - 'd' processed after waiting $0$ - [a, c]
  • t(2): 'e' and 'f' added: [a, c, e, f] - 'f' processed after waiting $0$ - [a, c, e]
  • t(3): [a, c, e] - 'e' processed after waiting $1$ - [a, c]
  • t(4): [a, c] - 'c' processed after waiting $3$ - [a]
  • t(5): [a] - 'a' processed after waiting $5$ - []

Average wait time: $(0 + 0 + 0 + 1 + 3 + 5) / 6 = 1.5$, longest wait time: $5$

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

The example by @MattD is great inspiration to see what happens. Note how there is a difference between maximal and average waiting time. The maximal waiting time can be optimized.

The average waiting time equals the total waiting time divided by the number of tasks. So you can prove that the average waiting time is the same under all executions by looking at the total waiting time. This can be done as follows. Look at any two tasks and swap them. This will not change the total waiting time: one will be $x$ units faster, the other $x$ units later. (This even holds when swapping a task to a time before it was added, but that is a mathematical curiosity...) This reasoning only holds when all tasks are of the same length.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.