python - 将伪代码翻译成Python？

Question

我需要一些帮助来翻译此内容pseudocode到 python ，我在代码中提出了一些问题，真的很希望得到一些帮助:)我确实理解代码背后的想法，即二进制乘法的分而治之技术。

你们会如何用 python 编写这个？

def mult(A,B):

        n = len(A)
        if (n <= 1):
            return (A[0]*B[0])

        p = A[0:n/2]
        q = A[n/2:n]
        r = B[0:n/2]
        s = B[n/2:n]

        pr = mult(p,r)
        ps = mult(p,s)
        rq = mult(r,q)
        qs = mult(q,s)

        sum = ps + rq # no problem adding like this I guess

？

好吧，我不知道伪代码中的“in”和“end”是做什么的。 我认为转变只是使用“<<”运算符。或者在本例中可能不是，因为它是一个列表，但为此创建一个帮助函数很简单。

Answer 1

首先，我认为这根本不是伪代码，而是用真实语言编写的代码，可能是从 (S)ML 派生的语言。如果您知道它是什么语言，那么解释它就会容易得多 - 您可以在该语言的文档中查找它，而不是试图猜测 shift 之类的内容。

<小时/>

话虽如此，您显然翻译了很多错误的内容。

<小时/>

首先，你把它变成了:

if |A| ≤ 1

…进入这个:

n = len(A)
if (n == 1):

除了添加无意义的额外括号之外，您还破坏了 A 为空的递归基本情况。

<小时/>

接下来，par可能只是意味着“如果你愿意的话，你可以并行地执行这些操作”，所以忽略它可能是可以的。另一方面，考虑到您是从并行算法和数据结构类(class)的讲义中获取这一点的，您忽略的内容可能就是整个要点。显然，在 Python 中，您需要将其映射到不同的东西 - 例如，创建一个 concurrent.futures.ProcessPoolExecutor，提交四个递归调用，然后等待所有四个 future？ (尽管这有可能是一种尽可能晚的绑定(bind)语言，在这种情况下，您不想在这里等待 future ，而是更改使用这些值之一的每个表达式，以便它等待它需要的 future ，并将这些表达式也提交给执行者。)

<小时/>

无论如何，您已经将对正在定义的函数的递归调用转换为对某个不同函数的调用。所有这些:

    pr = binary_mult(p,r)
    ps = binary_mult(p,s)
    rq = binary_mult(r,q)
    qs = binary_mult(q,s)

…需要调用mult。

<小时/>

let ... in ... end 实际上是说第一个 ... 是第二个 ... 的一堆局部变量。您可以通过例如在每个变量上用del替换end来翻译它，但我认为忽略它是可以的，因为你有.

但是你遗漏了最重要的部分，这一点:

shift(pr, n) + shift(sum, n/2) + qs

我不确定最后一个 + 是 +。它可能是不同的符号，或者是光标在 + 上移动时截取的屏幕截图，或者是 + 上有灰尘的打印输出的扫描件，或者其他一些很好的例子说明了当您需要文本中的代码帮助时为什么应该发布文本而不是文本图片......

无论如何，你需要做任何正在做的事情(并返回结果)。这是该函数的关键部分；所有 let … in 内容都只是为此表达式设置的。

<小时/>

按照你对函数含义的猜测，以及我对几乎 SML 语法的猜测，忽略并行位，像你写的东西接近直接翻译:

def shift(A, n):
    # Taking a wild guess
    return A + [0 for _ in range(n)]

def mult(A, B):
    n = len(A)
    if n <= 1:
        return [A[0] * B[0]]
    else:
        p, q = A[:n//2], A[n//2:]
        r, s = B[:n//2], B[n//2:]
        pr, ps, rq, qs = mult(p, r), mult(p, s), mult(r, q), mult(q, s)
        sum = ps + rq
        return pr << n + sum << n//2 + qs

我敢打赌我们至少猜错了一件事。例如，也许 + 应该是按元素相加而不是列表串联。找出答案的唯一方法是用一些数字运行它并检查输出。唯一的问题是，我什至不知道输入应该是什么。也许是二进制数字的大端位值列表？在这种情况下，+ 必须是带有进位的元素加法。

事实上，这些东西应该可以同时用作数字和大尾数位列表。没有内置的 Python 类型可以这样工作，但构建一个……或在 PyPI 上找到一个并不太难。 bitarray 和 bitstring 看起来像是合理的候选者。