注意事项
这不是特定于 REBOL 的问题。您可以用任何语言回答。
背景
REBOL language 支持创建特定领域的语言,在 REBOL parlance 中称为“方言”。我为列表理解创建了这样一种方言,REBOL 本身不支持它。
列表理解需要一个好的笛卡尔积算法。
问题
我使用元编程来解决这个问题,方法是动态创建然后执行一系列嵌套的 foreach
语句。它工作得很漂亮。但是,因为它是动态的,所以代码可读性不是很好。 REBOL 不能很好地进行递归。它会迅速耗尽堆栈空间并崩溃。所以递归解决方案是不可能的。
总而言之,如果可能的话,我想用可读的、非递归的“内联”算法替换我的元编程。解决方案可以是任何语言,只要我能在 REBOL 中重现它。 (我几乎可以阅读任何编程语言:C#、C、C++、Perl、Oz、Haskell、Erlang,等等。)
我要强调的是,这个算法需要支持任意数量的集合来“连接”,因为列表理解可以涉及任意数量的集合。
最佳答案
速度提高 3 倍,内存使用量减少(回收次数减少)。
cartesian: func [
d [block! ]
/local len set i res
][
d: copy d
len: 1
res: make block! foreach d d [len: len * length? d]
len: length? d
until [
set: clear []
loop i: len [insert set d/:i/1 i: i - 1]
res: change/only res copy set
loop i: len [
unless tail? d/:i: next d/:i [break]
if i = 1 [break]
d/:i: head d/:i
i: i - 1
]
tail? d/1
]
head res
]
关于algorithm - 什么是计算笛卡尔积的良好非递归算法?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/215908/