Is there a way to avoid creating an array in this Julia expression?

Question

Is there a way to avoid creating an array in this Julia expression:

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

and make it behave similar to this Python generator expression:

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

Julia version is 2.3 times slower then Python due to array allocation and N*N iterations vs. Python's N*N/2.

EDIT

After playing a bit with a few implementations in Julia, the fastest loop style version I've got is:

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 

but an improved functional version isn't far behind (only 14% slower or significantly faster, if you consider 2x larger domain):

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 

There is 2.6x unexpected performance improvement by defining isPalindrome function, compared to original version on the top of this page.

Answer 1

We have talked about allowing the syntax

max(f(x) for x in itr)

as a shorthand for producing each of the values f(x) in one coroutine while computing the max in another coroutine. This would basically be shorthand for something like this:

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

Note, however, that this syntax that explicitly creates a task already works, although it is somewhat less pretty than the above. Your problem can be expressed like this:

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

With the hypothetical producer syntax above, it could be reduced to something like this:

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

While I'm a fan of functional style, in this case I would probably just use a for loop:

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

Personally, I don't find this version much harder to read and it will certainly be quite fast in Julia. In general, while functional style can be convenient and pretty, if your primary focus is on performance, then explicit for loops are your friend. Nevertheless, we should make sure that John's max/filter/product version works. The for loop version also makes other optimizations easier to add, like Harlan's suggestion of reversing the loop ordering and exiting on the first palindrome you find. There are also faster ways to check if a number is a palindrome in a given base than actually creating and comparing strings.

As to the general question of "getting flexible generators and list comprehensions in Julia", the language already has

1. A general high-performance iteration protocol based on the start/done/next functions.
2. Far more powerful multidimensional array comprehensions than most languages. At this point, the only missing feature is the if guard, which is complicated by the interaction with multidimensional comprehensions and the need to potentially dynamically grow the resulting array.
3. Coroutines (aka tasks) which allow, among other patterns, the producer-consumer pattern.

Python has the if guard but doesn't worry about comprehension performance nearly as much – if we're going to add that feature to Julia's comprehensions, we're going to do it in a way that's both fast and interacts well with multidimensional arrays, hence the delay.

Update: The max function is now called maximum (maximum is to max as sum is to +) and the generator syntax and/or filters work on master, so for example, you can do this:

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

Once 0.5 is out, I'll update this answer more thoroughly.

Answer 2

There are two questions being mixed together here: (1) can you filter a list comprehension mid-comprehension (for which the answer is currently no) and (2) can you use a generator that doesn't allocate an array (for which the answer is partially yes). Generators are provided by the Iterators package, but the Iterators package seems to not play well with filter at the moment. In principle, the code below should work:

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

Answer 3

I don't think so. There aren't currently filters in Julia array comprehensions. See discussion in this issue.

In this particular case, I'd suggest just nested for loops if you want to get faster computation.

(There might be faster approaches where you start with N and count backwards, stopping as soon as you find something that succeeds. Figuring out how to do that correctly is left as an exercise, etc...)

Answer 4

As mentioned, this is now possible (using 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)))

I'm sure there are better ways that others can comment on. Time (after warm-up):

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