Infinite array

Hello,
How can I define an infinite array? For example, I don’t know the number of data that will be entered into the array and I want to have an infinite array where no matter how much data I put into it, the length of the array will be the same number of data.

Thank you.

why not define a empty Array or Vector, and push! the elements?

4 Likes

An array that can truly hold infinitely many things is impossible on a computer with finite memory/storage.

Is what you need a way to dynamically increase the size of an array? Then you could have a look at the functions push!, resize!, and append! for example. It is fairly common that the final size of an array is not known at the time of creation, so what you could do is something like

data = [] # If you know the type of the elements, it's usually better to specify it here

userInput = ...

append!(data, userInput)

Julia automatically takes care that the array data is large enough to hold everything you want to put into it. But it is not “infinite” since you will run out of memory at some point and get an error, e.g. here I’m trying to ask for more space than my machine actually has:

julia> data = Array{Int, 1}(undef, 1000000000000000000)
ERROR: OutOfMemoryError()
Stacktrace:
 [1] Vector{Int64}(::UndefInitializer, m::Int64)
   @ Core ./boot.jl:477
 [2] top-level scope
   @ REPL[9]:1

I’m sure there are better ways than this, but maybe you could specify what you need exactly a bit more in detail.

7 Likes

Hello,
Thank you so much for your reply.
I did:

function duplicate()
    array = [1,2,3,4,4,4,5]
    dup = []
    counter = 1
    for i = 1 : (length(array)-1)
        for j = 1 : i
            if array[j] == array[i+1]
                dup[counter] = array[j]
                counter += 1
            end
        end
    end
print(dup)
end
duplicate()

But I got:

ERROR: LoadError: BoundsError: attempt to access 0-element Vector{Any} at index [1]

In Julia arrays are not automatically extended when you add something to a nonexistent index. You should do:

push!(dup, array[j])

This will extend dup by 1 and add array[j]. If you want to add several items at once you should use append!. See the docs

5 Likes

Hi, thanks for your attempt and welcome to the community!
If you create an empty array using dup=[], julia doesn’t automatically index it. If you are assigning elements sequentially, I would advise using

push!(dup, array[j])

instead of your previous attempt. If you want to push many elements in one time, please use append!() etc.
You can also assign the empty array with a large number, like

dup = zeros(Int64, 100)

That would create an indexed 100 element array with default number 0.

2 Likes

While I would also advise you to use push! etc. on Vectors, you could alternatively use dictionaries.

function duplicate()
    array = [1,2,3,4,4,4,5]
    dup = Dict()  # or Dict{Int, Int}() for better performance
    counter = 1
    for i = 1 : (length(array)-1)
        for j = 1 : i
            if array[j] == array[i+1]
                dup[counter] = array[j]
                counter += 1
            end
        end
    end
    return dup
end

dup = duplicate()  # (Note that the entries in dup are stored in arbitrary order)
for i = 1:length(dup)
    println(dup[i]) 
end
4
4
4

This will be less performant than using Vectors, but that’s presumably not really a concern at this point. And obviously you will get a Dict, not an Array. But this would allow you to assign to entries which do not exist yet.

2 Likes

Independent of what duplicate is actually supposed to do (not sure if the name communicates well what it actually does), comprehensions are very convenient for building new arrays (also of unknown size):

function duplicate(array)
    [array[j] 
     for i in 1:(length(array)-1) 
     for j in 1:i
     if array[j] == array[i+1]]
end
2 Likes

Hello,
Thank you so much for you reply.
Is Dict much less efficient than array?

This all depends on the context. You can time and check allocated memory yourself using among others @time, BenchmarkTools.jl’s @btime, @benchmark, or Chairmark.jl’s @b:

Method definitions
using BenchmarkTools

function duplicate_preallocated()
    array = [1,2,3,4,4,4,5]
    dup = zeros(Int, length(array))
    counter = 1
     for i = 1 : (length(array)-1)
        for j = 1 : i
            if array[j] == array[i+1]
                dup[counter] = array[j]
                counter += 1
            end
        end
    end
    return dup
end

function duplicate_push()  # cf. hz-xiaxz, Eliassj
    array = [1,2,3,4,4,4,5]
    dup = Int[]  # could use sizehint! for potentially slightly better performance
    for i = 1 : (length(array)-1)
        for j = 1 : i
            if array[j] == array[i+1]
                push!(dup, array[j])
            end
        end
    end
    return dup
end

function duplicate_comprehension()  # cf. bertschi
    array = [1,2,3,4,4,4,5]
    return [array[j] 
        for i in 1:(length(array)-1) 
        for j in 1:i
        if array[j] == array[i+1]]
end

function duplicate_dict() 
    array = [1,2,3,4,4,4,5]
    dup = Dict{Int, Int}()
    counter = 1
    for i = 1 : (length(array)-1)
        for j = 1 : i
            if array[j] == array[i+1]
                dup[counter] = array[j]
                counter += 1
            end
        end
    end
    return dup
end
julia> @btime duplicate_preallocated()
  47.172 ns (4 allocations: 224 bytes)
7-element Vector{Int64}:
 4
 4
 4
 0
 0
 0
 0

julia> @btime duplicate_push()
  47.730 ns (3 allocations: 208 bytes)
3-element Vector{Int64}:
 4
 4
 4

julia> @btime duplicate_comprehension()
  73.975 ns (5 allocations: 272 bytes)
3-element Vector{Int64}:
 4
 4
 4

julia> @btime duplicate_dict()
  109.903 ns (6 allocations: 560 bytes)
Dict{Int64, Int64} with 3 entries:
  2 => 4
  3 => 4
  1 => 4

If I were to phrase these results as the Dict approach being more than twice as slow as the push! version, you might conclude that it is much less efficient. If you needed to run this function many times for different (small) input arrays, this would certainly be a valid conclusion.

Alternatively, you might say that using Dicts here is only some 60 ns slower, which is completely negligible. This conclusion would be equally valid, if you would only need to run this function once.

1 Like

ElasticArrays.jl ??