8
$\begingroup$

What is a good, common way to express dictionaries (= maps) in pseudocode? I.e. datastructures that basically allow to store values for keys, iterate over all key/value pairs, test for inclusion of a given key, etc. I have something like the following (in this case senseless) Python code in mind:

D = {}
D[1] = 2
for key, value in D.items():
    # do something with key and value
if key in D:
    # do something

And I want to express it as pseudocode in a publication. Thinking mathematically, dictionaries are functions are relations are sets of pairs, so writing something like

D ← ∅
D[1] ← 2
for all (k, v) ∈ D

would actually make sense. But is it understandable? And for the test, I'd use

if k ∈ keys(D)

Or is it saver to be more literal, e.g.

D ← empty dictionary
for all key-value pairs (k, v) in D

Is there existing good practice / any reference on how to write commonly understandable pseudocode?

$\endgroup$
  • $\begingroup$ I think this should be moved to Stackoverflow. $\endgroup$ – David Ketcheson Feb 26 '12 at 7:29
  • $\begingroup$ Thought about Stack Overflow as well, but was in doubt because it's not about actual programming but only about how to present it, which is certainly related to computational science. However, if you feel like it should be moved, can somebody do that for me? (I myself cannot, can I?) $\endgroup$ – Jan Pöschko Feb 26 '12 at 10:29
  • $\begingroup$ I just started a discussion on meta at meta.scicomp.stackexchange.com/questions/205/… $\endgroup$ – Jan Pöschko Feb 26 '12 at 10:40
  • $\begingroup$ @DavidKetcheson: In the future, if you feel the question should be migrated, please flag it for migration. In this case, Jan is right; it's not about actual programming, so it's not on-topic for Stack Overflow. However, it may be on topic for Programmers or cstheory. I'd have to talk to the cstheory mods about the edits they want, since one of their mods mentioned that the question would need to be tweaked for their site. $\endgroup$ – Geoff Oxberry Feb 27 '12 at 14:46
  • $\begingroup$ In the mean time, this link to a question on cstheory in the meta thread (courtesy of cstheory mod Kaveh) may be of interest to people who are interested in this question. $\endgroup$ – Geoff Oxberry Feb 27 '12 at 14:51
7
$\begingroup$

It looks like you're already using some of the concepts from Corwin, Leiserson, Rivest, and Stein, which I've always seen as the "default" introductory text for algorithms, in writing your pseudocode. I don't think there's any more standard reference for pseudocode.

However, I would argue that what makes a good pseudocode is to break the problem down into its representative mathematical and logical functions. What conditions have to be true to execute the code? What branches exist? What data is really essential in determining the behavior?

Beyond that, the goal of good pseudocode is to tell the programmer what needs to be done—and not necessarily how to implement it. You might want, for instance, to flatten something like nested loops into a single statement:

For all elements x in 2-D array A
    x ← max(0, x)

would probably be better than saying

For all i in 1:m
   For all j in 1:n
       A(i,j) ← max(0, A(i,j)

as the latter already starts to make some assumptions about the language that is being used (row-major versus column-major, etc.).

$\endgroup$
4
$\begingroup$

I think it depends on the context of the publication, the intended audience, and how "common" you need "commonly understandable" to be. I do think your last option is probably safest, i.e. be as literal/explicit and as close to "plain English" as possible. But if your intended audience has familiarity with set theory, or Python, or Java, or C#, or JavaScript, etc., then a notation similar to one of those might be better.

I make this suggestion as someone who conducts job interviews where the candidate is expected to write code or pseudocode. Most candidates (both good and bad) tend to drift toward the language they're most familiar with in order to make their pseudocode as understandable as possible to themselves and to me. People familiar with Java write Map<K,V>. People familiar with Python write tuples or a dictionary as you did in your first code snippet. People familiar with C write arrays. People with less of a programming background tend to write pseudocode that looks more like plain English -- but that often ends up looking like Python anyway. :-)

I unfortunately can't answer your last question -- I'm not familiar with any reference or common recommendations for writing pseudocode.

$\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.