Pseudo Code optimization

Question

Summary:

I am struggling with the Pseudo code for an that algorithm assigns "least filled slot first" to a tasks on multi-core chip.

Detail

So far I have written following:

What I do not like here is:

1. In while loop I am removing one by one elements of $R$ (which is a row vector with $m$ elements). This means the complexity of $m^2$, however I could have sorted $R$ outside the loop and then just removed the head every time that would reduce the complexity to $m\log m + m$ for this part. But in that case the index $j$ will get jumbled up and not usable in the rest of the part. Is there an elegant Pseudo-code way of saying "store the indices before sorting for later use"?
2. Any other stylistic suggestions that make it easier to read while still reducing the "implementation complexity" ?

In general, I know its a trade-off between readability vs complexity. Generally, the main purpose of presenting an algorithm is to make it readable and leave the implementation details to the implementer. But just to be pedantic ..

Thanks.

Answer 1

Good questions.

On algorithm

• "Is there an elegant Pseudo-code way of saying 'store the indices before sorting for later use'?"

  Yes. you can write "let $Q$ be the array that includes $(r_{j}, j)$ for all $1\le j\le m$ sorted by their first entries". Note that $Q$ keeps track of the indices in the second entries of its elements.

  What you will code actually is to create an array that has all elements like $(r_j,j)$ and sort it, where $(a, b)\prec (c, d)$ if $a < c$. In term of Java, your sort the array of those ordered pairs with a customized comparator. In Python, it is automatic as you can try a = [(5,1),(7,2),(4,3)]; a.sort(); print(a).

• You cannot pull out $t$ from the array $S$ since each element in $S$ is $d_t$, a primitive value.

  What you want is to store the key-value pair $(t, d_t)$ in $S$. That is, $S$ should be an associative array, which is a dict in Python or a Map in Java or std::map in terms of C++.

• "For all $d_t\in S$, set $d_t= d_t+r_j$".

  Since $d_t$ appears in $S$, "set $d_t$" could be probably understood as "set the $d_t$ in $S$" by anyone who has not understood the algorithm before seeing the pseudocode. What you want is to update, I believe the $d_t$ in $D$ instead of $d_t$ in $S$.

On variables

• The name of variables does not make much sense. It is prefered to use the first letter of one related word.
• There is no need to introduce both $R$ and $[r_{j}]_{1\times m}$. Only one or two labels/variables are used in actual programming code, such as double[] r = new double r[m]; in Java or double[m] r; in C/C++.
• Why considering $[r_j]$ as a $1\times m$ matrix? It is a simple array.

For example, you could write the following naming choices.

• Per Core peak power consumption: $p=[p_1,\cdots, p_m]$
• Per Core Utilizations: $u=[u_1, \cdots, u_m]$
• Total time slots in a period: $s$

How to write pseudocode?

It occurs to me that the pseudocode in the question might be even harder to understand than the actual code had it been implemented in most programming languages that I use.

Whenever you are writing pseudocode, imagine that you are telling the target audience how the algorithm works. Have you made it easier for them to understand the algorithm fully and correctly?

Answer 2

I think it would be perfectly reasonable and normal to present the pseudocode as is, and to mention in the accompanying text that if you sort $R$ in advance, you can implement this algorithm in $O(m \log m)$ time. I think it's pretty clear how to implement the selection step, and you don't need to write out all the indices to explain.