有没有一种方法可以避免在这个Julia表达式中创建一个数组？

Question

有没有办法在这个Julia表达式中避免创建一个数组：

max((filter(n -> string(n) == reverse(string(n)), [x*y for x = 1:N, y = 1:N])))

并使其表现类似于此 Python 生成器表达式：

max(x*y for x in range(N+1) for y in range(x, N+1) if str(x*y) == str(x*y)[::-1])

由于数组分配和N*N迭代，Julia版本比Python慢2.3倍。

编辑

在尝试了几个Julia实现之后，我得到的最快循环方式版本是：

function f(N)   # 320ms for N=1000  Julia 0.2.0 i686-w64-mingw32
    nMax = NaN
    for x = 1:N, y = x:N
        n = x*y 
        s = string(n)
        s == reverse(s) || continue
        nMax < n && (nMax = n)
    end 
    nMax
end 

但是一个功能更好的版本并不远了（只比原来慢14%，如果你考虑到2倍大的域名，它甚至会更快）：

function e(N)   # 366ms for N=1000  Julia 0.2.0 i686-w64-mingw32
    isPalindrome(n) = string(n) == reverse(string(n))
    max(filter(isPalindrome, [x*y for x = 1:N, y = 1:N]))
end 

在定义isPalindrome函数后，与本页面顶部原始版本相比，性能提升了2.6倍。

- Paul Jurczak

---

干得好。你可以在这里写filter(isPalindrome, ...)。 - StefanKarpinski

@StefanKarpinski 谢谢，现在看起来好多了。 - Paul Jurczak

Answer 1

我们已经谈论过允许语法。

max(f(x) for x in itr)

作为一种简写形式，可以在一个协程中产生每个值f(x)，同时在另一个协程中计算最大值。这基本上就是以下代码的简写：

作为一种简写形式，可以在一个协程中产生每个值f(x)，同时在另一个协程中计算最大值。这基本上就是以下代码的简写：

max(@task for x in itr; produce(f(x)); end)

请注意，这种显式创建任务的语法已经可以使用，虽然它比上面的语法略显繁琐。你的问题可以这样表达：

max(@task for x=1:N, y=x:N
    string(x*y) == reverse(string(x*y)) && produce(x*y)
end)

通过上述假设的生产者语法，它可以被简化为如下内容：

max(x*y if string(x*y) == reverse(string(x*y) for x=1:N, y=x:N)

虽然我喜欢函数式风格，但在这种情况下我可能会使用for循环：

m = 0
for x = 1:N, y = x:N
    n = x*y
    string(n) == reverse(string(n)) || continue
    m < n && (m = n)
end    

就我个人而言，我觉得这个版本不难阅读，而且在Julia中肯定会非常快。一般来说，虽然函数式风格可能很方便和漂亮，但如果您的主要关注点是性能，则明确的for循环是您的朋友。尽管如此，我们还是应该确保John的 max/filter/product 版本能够正常工作。for循环版本也可以更容易地添加其他优化，例如Harlan建议的反转循环顺序并在找到第一个回文时退出。在给定基数的情况下，检查数字是否为回文的更快方法也比实际创建和比较字符串更快。

至于“在Julia中获得灵活的生成器和列表理解”的一般问题，该语言已经拥有：

1. 基于start/done/next函数的通用高性能迭代协议。
2. 比大多数语言更强大的多维数组推导式。目前，唯一缺失的功能是if guard，由于与多维推导式的交互以及需要动态增长结果数组的需要而变得复杂。
3. 协程（又称任务），允许生产者-消费者模式等模式。

Python具有if guard，但几乎不关心推导性能——如果我们要将该功能添加到Julia的推导中，我们将以既快又良好地与多维数组交互的方式来完成它，因此需要一些时间。

更新： max函数现在被称为maximum（maximum是max的sum），生成器语法和/或过滤器在主分支上工作，因此，例如，您可以执行以下操作：

julia> @time maximum(100x - x^2 for x = 1:100 if x % 3 == 0)
  0.059185 seconds (31.16 k allocations: 1.307 MB)
2499

一旦0.5版本发布，我会更全面地更新这个答案。

- StefanKarpinski

---

在Julia中使用所有的元编程好处，将max(x*y if string(x*y) == reverse(string(x*y) for x=1:N, y=x:N)直接转换为您上面编写的循环，避免协程调用开销和粘合逻辑。这可行吗？ - Paul Jurczak

使用函数式编程风格的另一个原因是它可以保证正确性。当你编写一段命令式代码时，你必须验证它的正确性，而且很容易变得自满。我知道您最近很忙，但是您写的循环有两个问题：初始值应该是NaN，而max = n 应该是 nMax = max(n, nMax)。与此相反，上面那行声明式（函数式）版本没有这些问题。我的意思不是要挑剔，我只是想说明一点：声明式的max是一个真正的最大值，而命令式的实现在未经证明之前是不正确的。 - Paul Jurczak

我添加了最佳循环版本和修改的函数版本的基准测试，后者仅慢了16%。 - Paul Jurczak

元编程并不能为您提供新的语法或自动翻译语法，它只允许您编写诸如宏之类的东西。这种假设的语法不是宏，它是一个全新的语言特性，包括当前不是有效的Julia的新语法。 - StefanKarpinski

Answer 2

这里混淆了两个问题：（1）你能在列表推导式中间进行筛选吗（目前的答案是不行），（2）你能使用不分配数组的生成器（部分答案是可以）。 生成器由迭代器包提供，但是迭代器包目前似乎无法很好地与filter一起使用。原则上，下面的代码应该可以工作：

max((x, y) -> x * y,
    filter((x, y) -> string(x * y) == reverse(string(x * y)),
           product(1:N, 1:N)))

- John Myles White

---

“product”函数可用吗？我在哪里可以找到它？ - Paul Jurczak

Answer 3

我不这样认为。目前Julia数组推导中没有过滤器。请参阅此问题中的讨论。

在这种情况下，如果你想获得更快的计算速度，我建议使用嵌套的for循环。

（可能有更快的方法，比如从N开始倒数，一旦找到成功的东西就停止。如何正确地做到这一点留作练习等...）

- Harlan

---

我看过那个帖子。在Julia中是否有希望获得灵活的生成器或列表推导式？它们是否与Matlab范例相距太远？至于更改算法，那是另一种不同的练习，超出了我的问题范围。 - Paul Jurczak

Answer 4

如前所述，现在可以实现这一点（使用Julia 0.5.0）。

isPalindrome(n::String) = n == reverse(n)
fun(N::Int) =  maximum(x*y for x in 1:N for y in x:N if isPalindrome(string(x*y)))

我相信其他人可能有更好的方式来评论。时间（热身后）：

julia> @time fun(1000);
   0.082785 seconds (2.03 M allocations: 108.109 MB, 27.35% gc time)

- S Gilmore