Dyalog APL中的堆队列

Question

我正在学习Dyalog APL。我实现了一个二进制堆，它似乎可以工作。我如何使它看起来更像APL (而不是Python)？

⎕io←0
heappush←{(⍺,⍵)siftdown 0(≢⍺)}

heappop←{
 heap←⍵
 last←⊃¯1↑heap ⋄ rest←¯1↓heap
 0=≢rest:rest last
 r←heap[0]
 (((last@0)rest)siftup 0)r
}

siftdown←{
 heap←⍺
 start pos←⍵
 item←pos⌷heap
 newpos←{
  ⍵≤start:⍵
  parentpos←⌊(⍵-1)÷2
  parent←parentpos⌷heap
  item

Answer 1

我如何使它看起来更像APL (而不是Python)？

假设你的意思是“以一种功能更强、命令更少的方式”，

--我不认为你能很大程度上做到这一点，这是有原因的。基本上，基于数组的堆(以及您在算法教科书上看到的其他常见算法)是为命令式语言设计的。将其翻译成一种语言，其主要优势不是命令式的，这会使代码感到尴尬和不合适。它还可能导致代码，其时间复杂度实际上比设计的还要糟糕。看看用Haskell编写类似算法时的样子. APL不是100%的功能，但肯定比命令式更有功能(特别是当您主要使用dfns时)。如果需要，搜索“函数算法”并尝试实现这些算法。在堆的情况下，左倾树并不太复杂，与命令式二进制堆相比，它支持更多的O(\log n)操作(堆合并)。您也可以查看插图不错。

，但您仍然可以改进代码的某些部分.

在

算法中的改进

• 使用⎕IO←1代替。

默认情况下，基于数组的堆使用基于0的索引，因此父-子关系稍微有些尴尬：

\begin{align} \text{left child}&=1+2\times\text{parent} \\ \text{right child}&=2+2\times\text{parent} \\ \text{parent}&=\Bigl\lfloor \frac{\text{child} - 1}2 \Bigr\rfloor \end{align}

如果您使用基于1的索引，它会变得稍微干净一些：

\begin{align} \text{left child}&=2\times\text{parent} \\ \text{right child}&=1+2\times\text{parent} \\ \text{parent}&=\Bigl\lfloor \frac{\text{child}}2 \Bigr\rfloor \end{align}

我没有其他更好的想法来利用APL的优势，因为底层的算法纯粹是命令式的。

编写APL代码

的一般技巧

• 将并进函数的正确参数设为主参数(即堆)。
• 如果您看到一个比较的否定(例如~heap[chp])，请使用单个等效函数(例如，heap[chp]≥heap[rpos])。
• 当你连接两个标量时，更喜欢串联(例如0,≢⍺)而不是搁浅(例如0(≢⍺))。
• 在实现算法时，不要修改现有变量的内容(例如，避免引用chp←((rpos<≢heap)∧~heap[chp]，然后修改它)。试着选择一个单独而有意义的名字。
• 平行尺寸的搁浅作业(例如(start pos)←⍵而不是start pos←⍵)。
• 考虑使用命名约定，以及一些描述性更强的名称。(例如，我很难看出chp代表什么。)
• 考虑在每个函数中添加注释，简要描述输入(S)和输出。