伪代码中的字典

计算科学 算法 出版物
2021-12-15 07:46:39

用伪代码表达字典(=地图)的好方法是什么?即基本上允许存储键值、遍历所有键/值对、测试是否包含给定键等的数据结构。我脑子里有类似以下(在这种情况下毫无意义)的 Python 代码:

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

我想在出版物中将其表示为伪代码。从数学上思考,字典是函数,关系是成对的集合,所以写类似

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

实际上是有道理的。但这可以理解吗?对于测试,我会使用

if k ∈ keys(D)

还是更字面意义上的节省,例如

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

是否有关于如何编写通常可以理解的伪代码的良好实践/任何参考?

2个回答

在编写伪代码时,您似乎已经在使用Corwin、Leiserson、Rivest 和 Stein中的一些概念,我一直将其视为算法的“默认”介绍性文本。我认为伪代码没有更多的标准参考。

然而,我认为一个好的伪代码是将问题分解成具有代表性的数学和逻辑函数。执行代码必须满足哪些条件?存在哪些分支?哪些数据对于确定行为真正重要?

除此之外,好的伪代码的目标是告诉程序员需要做什么——而不一定是如何实现它。例如,您可能希望将嵌套循环之类的内容扁平化为单个语句:

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

可能会比说更好

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

因为后者已经开始对正在使用的语言做出一些假设(行优先与列优先等)。

我认为这取决于出版物的背景、目标受众以及您需要“普遍理解”的程度。我确实认为您的最后一个选择可能是最安全的,即尽可能文字/明确并尽可能接近“普通英语”。但是,如果您的目标受众熟悉集合论、Python、Java、C# 或 JavaScript 等,那么类似于其中之一的符号可能会更好。

我提出这个建议是作为一个进行求职面试的人,希望候选人编写代码或伪代码。大多数候选人(无论好坏)都倾向于使用他们最熟悉的语言,以使他们的伪代码对他们自己和我来说尽可能容易理解。熟悉 Java 的人编写Map<K,V>. 熟悉 Python 的人会编写元组或字典,就像您在第一个代码片段中所做的那样。熟悉 C 的人会写数组。编程背景较少的人倾向于编写看起来更像普通英语的伪代码——但最终往往看起来像 Python。:-)

很遗憾,我无法回答您的最后一个问题——我不熟悉编写伪代码的任何参考或常见建议。