Computing array elements on call


#1

Hello,

I’d like to have an array which elements A[i, j] are computed from a given function f(i, j) (say f(i, j) = i + j) only when that element is used, i.e. I would not like to build the whole matrix beforehand.

I was thinking of maybe writing a new type which subtypes AbstractArray, but it’s a bit of work. I’ve tried looking for implementations of something like that, but wasn’t able to find anything.
Does anyone has any suggestions?

Thanks :slight_smile:


A curious case of allocating behavior
#2

#3

Ah that’s a cool package, thanks!
However, it’s not exactly what I’ve been looking for… What I want is to have an actual array, which can e.g. be passed to a function which takes AbstractArrays, but I don’t want to build this array, I want to define it via a function, something like

f(i, j) = i + j
A = FunctionArray(f, 10, 10) # 10x10 array such that A_{ij} = i + j
s = sum(A)

That way I wouldn’t have to store the whole matrix in memory. Also if I don’t need the whole matrix (say I want to do sum(A[:, 1])), I can only compute the elements I need.

Any clue?
Thanks again!


#4
using NullableArrays

immutable LazyArray{T,N}
    generator
    values::NullableArray{T,N}
end

function LazyArray(f, T, dims::Int...)
    LazyArray{T,length(dims)}(f, NullableArray(T, dims...))
end

function Base.getindex{T,N}(la::LazyArray{T,N}, inds...)
    elt = la.values[inds...]
    if isnull(elt)
        v = la.generator(inds...)
        la.values[inds...] = Nullable(v)
        v
    else
        get(elt)
    end
end

la = LazyArray(+, Int, 10, 10)

la[1,2]
la[3,4]

You would still need to implement the AbstractArray interface in order to use it as one, but it is pretty trivial. I did not optimize anything, so you might want to do that.


#5

Cool, that’s exactly what I needed!!! Thank you :slight_smile:


#6

Note that you can

  1. make it a subtype of AbstractArray{T,N}, but it will mess up show etc unless you implement the interface, so do it after,
  2. check whether a type parameter for the function would improve anything (it may, I did not benchmark and don’t have a good mental model of it). In case it does, please report back, I am curious.

#7

it is easy to implement your own. two weird things:

1, show throws an error on one dimensional arrays, because apparently you have to implement (i, 1) indexing, even for vectors? need to look into that. however, it works, just does not show in the REPL

2, the second constructor invokes the function to determine its type. this is not the most elegant way, and there might be some trickery to find that out without invoking.

immutable CalculatedArray{T, N} <: AbstractArray{T, N}
  f::Function
  dims::NTuple{N, Int}
end
CalculatedArray(T, f, dims) = CalculatedArray{T, length(dims)}(f, dims)
CalculatedArray(f, dims) = CalculatedArray{typeof(f((ones(Int,dims)...))), length(dims)}(f, dims)
Base.size(a::CalculatedArray) = a.dims
Base.eltype{T, N}(::Type{CalculatedArray{T, N}}) = T
Base.getindex{T, N}(a::CalculatedArray{N, T}, i...) = a.f(i...)

#8

and with some hackery, we can improve. i have no clue if it is documented.

rettype(f, n) = Base.return_types(f, ntuple(_->Int, n))[1]
CalculatedArray(f, dims) = CalculatedArray{rettype(f, length(dims)), length(dims)}(f, dims)