有没有办法避免在这个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迭代与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 

但改进的功能版本并不落后(如果你认为2x更大的域,只有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倍的意外性能提升.

Answer 1

我们已经讨论过允许语法

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建议撤消循环排序并退出您找到的第一个回文.还有更快的方法来检查某个数字是否是给定基数中的回文,而不是实际创建和比较字符串.

关于"在朱莉娅获得灵活的生成器和列表理解"的一般问题,语言已经存在

1. 基于start/done/next函数的通用高性能迭代协议.
2. 比大多数语言更强大的多维数组理解.此时,唯一缺少的功能是if防护,由于与多维理解的交互以及可能动态增长结果数组的需要而变得复杂.
3. 协同程序(又称任务),除了其他模式之外,还允许生产者 - 消费者模式.

Python有if保护但不担心理解性能几乎同样多 - 如果我们要将这个特性添加到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出来,我会更彻底地更新这个答案.

Answer 2

这里有两个问题混合在一起:(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)))