5

有没有办法避免在这个 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 迭代与 Python 的 N*N/2 相比，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

但改进后的功能版本也紧随其后（如果您考虑 2 倍大的域，则仅慢 14% 或显着快）：

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 倍的意外性能提升。

4

4 回答 4

12

我们已经讨论过允许语法

max(f(x) for x in itr)

作为在一个协程中生成每个值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守卫，由于与多维理解的交互以及潜在地动态增长结果数组的需要而变得复杂。
  3. 协程（又名任务），除其他模式外，还允许生产者-消费者模式。

Python 有if保护，但几乎不担心理解性能——如果我们要将该功能添加到 Julia 的理解中，我们将以一种既快速又与多维数组交互良好的方式来完成，因此延误。

更新：该max函数现在被调用maximum（maximumis to maxas sumis to +）并且生成器语法和/或过滤器在 master 上工作，例如，您可以这样做：

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 出来，我会更彻底地更新这个答案。

于 2013-07-08T20:16:47.283 回答
6

这里有两个问题混合在一起：（1）你可以过滤列表理解中间理解（答案目前是否定的）和（2）你可以使用不分配数组的生成器（对于它答案部分是肯定的）。生成器由 Iterators 包提供，但 Iterators 包目前似乎不能很好地使用filter。原则上，下面的代码应该可以工作：

max((x, y) -> x * y,
    filter((x, y) -> string(x * y) == reverse(string(x * y)),
           product(1:N, 1:N)))
于 2013-07-08T03:47:47.237 回答
2

我不这么认为。Julia 数组解析中目前没有过滤器。请参阅本期的讨论。

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

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

于 2013-07-07T21:23:03.460 回答
1

如前所述，这现在是可能的（使用 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)
于 2017-01-14T22:23:27.827 回答