Dyalog APL循环性能问题及向量化实现咨询

问题描述 #

我尝试用循环处理Binance API获取的数据，但循环运行极慢，这是Dyalog的bug吗？相关测试代码如下：

res←getBinanceSymbols

res←⍬
baseToken←'USDT'

tmpSymbols←(⎕JSON(HttpCommand.Get'api.binance.com/api/v3/exchangeInfo').Data).symbols

:For sym1 :In tmpSymbols
    ⎕←sym1.symbol
:EndFor

我的完整任务是生成XXXYYY、XXXZZZ、ZZZYYY形式的交易对，尝试用嵌套循环实现但耗时极长，代码如下：

res←getBinanceSymbols

res←⍬
baseToken←'USDT'

tmpSymbols←(⎕JSON(HttpCommand.Get'api.binance.com/api/v3/exchangeInfo').Data).symbols

:For sym1 :In tmpSymbols
    Sym1_Token1←sym1.baseAsset
    Sym1_Token2←sym1.quoteAsset

    :If Sym1_Token1≡baseToken
        :For sym2 :In tmpSymbols
            Sym2_Token1←sym2.baseAsset
            Sym2_Token2←sym2.quoteAsset

            :If Sym1_Token1≡Sym2_Token2
                :For sym3 :In tmpSymbols
                    Sym3_Token1←sym3.baseAsset
                    Sym3_Token2←sym3.quoteAsset

                    :If Sym2_Token1≡Sym3_Token1
                    :AndIf Sym3_Token2≡Sym1_Token2
                    :AndIf Sym1_Token1≢Sym1_Token2
                    :AndIf Sym2_Token1≢Sym1_Token1
                    :AndIf Sym2_Token1≢Sym1_Token2

                        res,←⊂((Sym1_Token1⍪Sym1_Token2)(Sym2_Token1⍪Sym1_Token2)(Sym2_Token1⍪Sym1_Token2))

                    :EndIf
                :EndFor
            :EndIf
        :EndFor
    :EndIf
:EndFor

核心问题 #

1. 为何循环如此缓慢？我用的是Intel Core i5 11代+40GB DDR4的电脑，这个速度完全无法接受！
2. 如何不使用嵌套循环，用更符合APL风格的方式解决这个问题？

解答 #

问题1：循环缓慢的原因 #

这不是Dyalog的bug，核心原因有三点：

• 时间复杂度过高：三重嵌套循环的时间复杂度是O(n³)，Binance的交易对数量达数千个，n³对应数十亿级别的运算量，高性能CPU也会卡顿。
• APL的设计特性：APL是为数组式运算优化的，:For这类显式循环属于解释执行，开销远高于原生数组操作。
• 内存操作低效：代码中res,←⊂...每次循环都扩展数组，会不断触发内存重新分配，进一步拖慢速度。

问题2：APL风格的实现方案 #

APL的核心是用数组操作替代循环，以下是优化后的实现：

步骤1：提取结构化数据

先把交易对的基础资产和报价资产提取为数组，方便后续向量运算：

baseAssets ← tmpSymbols.baseAsset
quoteAssets ← tmpSymbols.quoteAsset

步骤2：筛选符合条件的交易对

我们需要的三元组满足：

• 交易对1：USDT⍪Y（USDT为基础资产，Y为报价资产）
• 交易对2：Z⍪USDT（Z为基础资产，USDT为报价资产）
• 交易对3：Z⍪Y（Z为基础资产，Y为报价资产）
• 额外约束：USDT≠Y、Z≠USDT、Z≠Y

用数组操作一次性完成筛选：

baseToken ← 'USDT'
; 筛选以USDT为基础资产的交易对，提取对应的Y
usdtBaseMask ← baseAssets ≡ baseToken
Y ← quoteAssets[usdtBaseMask]
; 筛选以USDT为报价资产的交易对，提取对应的Z
usdtQuoteMask ← quoteAssets ≡ baseToken
Z ← baseAssets[usdtQuoteMask]
; 将所有交易对转为"Z/Y"格式，存入命名空间实现哈希集合（快速查找）
allPairs ← baseAssets,⍨'/'∘,⊢ quoteAssets
pairSet ← ⎕NS⍬
pairSet.(⍎¨allPairs)←⊂1
; 筛选符合所有约束条件的Z-Y组合
valid ← ((Z≠baseToken)∧(Y≠baseToken)∧(Z≠Y)) ∧ (∊pairSet.⍎¨Z,⍨'/'∘,⊢Y)
; 生成最终的三元组结果
validZ ← Z[valid]
validY ← Y[valid]
res ← ⊂¨ (baseToken,⍨'/'∘,⊢ validY) , (validZ,⍨'/'∘,⊢ baseToken) , (validZ,⍨'/'∘,⊢ validY)

代码说明

• 用数组掩码一次性筛选目标交易对，避免循环遍历
• 用命名空间实现哈希集合，O(1)时间复杂度检查交易对是否存在
• 所有操作均为向量级运算，充分利用APL的底层优化，性能比嵌套循环提升数个数量级
• 最后一次性生成结果数组，避免频繁的内存重新分配

内容的提问来源于stack exchange，提问作者конструктор