Best way to return lists of unknown length?


#1

In Python, if I were to make a function which would return a list whose length varies depending on the input, if I couldn’t fit the code into a list comprehension, I’d usually use a yield statement to yield each array element I want in the output. Is there a recommended pattern for doing this in Julia?

One could always create an empty list and then append each wanted entry to that list but I wonder if there’s a better way to do that? Speed is a very crucial factor here as this function will need to be applied to every element in a very large matrix.


In case anyone needs an example of what I actually mean, I’m trying to convert something similar to this function from Python to Julia:

def hop(x, n):
    for i in range(n-1):
        mask = 3 << i
        if x & mask != 0 and x & mask != mask:
            yield x ^ mask
    mask = (1 << (n-1)) | 1
    if x & mask != 0 and x & mask != mask:
        yield x ^ mask

What’s going on here is that you give this function two integers x and n, where you care about the binary pattern of x mod n. Ie. if I am concerned with the binary pattern 1010 then x should be 10 in base 10 and n should be 4 because I’m treating x as a 4 bit integer.

The function is making a mask, initially 3, ie. 0011 in base 2 and its checking checking if x shares exactly one 1 bit with mask and if so, will yield an integer whose binary pattern is the same those of x in the spots where mask has zeros and will yield the complement of x's digits in the positions where mask has 1s. Finally, it does the same thing with a mask that has 1s at both ends of the digit and 0s everywhere else.

From the amount of control structure here, I don’t think this is a good candidate for list comprehensions but I also suspect that creating an empty list and appending to it isn’t ideal.

Any ideas?


#2

A loop that pushes elements onto a vector maybe?


#3

I assume you mean a Vector. I would say that it ideal, especially if you know the element type. push! is very smart, in the sense that it allocates more space when it needs to expand the vector. Also see sizehint!.


#4

Check out ResumableFunctions.jl which is the alternative of Python’s yield-style functions in Julia.


#5

There is no need for that here. Just push! to a Vector.


#6

Yes, unless you actually need a Vector for the result, and you are processing the returned elements, then something like that (or writing an iterator type, with done, next, and start methods), can do better, esp. with very large (or unbounded) amounts of data.


#7

The allocation-free analogue of this in Julia is to write an iterator (i.e. create a type with start/next/done methods). This way you don’t need to allocate a list (vector) at all and can just loop over the results.

In some cases, you won’t need to define a custom iterator type, and can instead use a Generator expression.