Array implementation in erlang

Question

My question is how arrays implemented in Erlang, as opposed to lists.

With immutable types doing things like

move ([X | Xs], Ys) -> [X | Ys]. Ls = move([1,2,3], [2,3,4]) 

will accept permanent memory on the heap, since this is all the reference work.

But for the same material in arrays

 move (A1, A2) -> array:set(0, array:get(0,A1),A2). A1 = array:from_list([1,2,3]). A2 = array:from_list([0,2,3,4]). A3 = move(A1,A2). 

Will move use a size proportional to A2, or will he be able to do this in a constant space, for example, with arrays?

Answer 1

To (hopefully) figure it out a bit. Remember that in Erlang ALL data is immutable! This deeply affects how you manage data.

The array module builds the structure of nested tuples, where all the array slots containing the data are on the same level. The size of each tuple is 10, so for access to the array we have O (lg10 (N)). Using a nested structure like this is common in immutable data languages. You can save the array in a flat tuple that will give you fast reads, but the records will become slow and the memory will depend on large arrays / tuples, since each record will require the creation of a new tuple. Using a tree structure means that much less data is created in the record.

How your move/2 function affects memory usage depends a bit on whether you write in a used or unused slot in an array. If the slot is already in use, the resulting memory usage will be the same. If you are writing a previously unused slot, you may need to increase the array, which means that more memory will be used.

This is exactly the same as for your list.

It also depends on having any references to the old data structure.

Answer 2

Here you can find the source code here . It appears that @rvirding mentioned that the array is a functional tree. I have not studied the implementation deeply - and there is no source in the source of the data source, but a quick review suggests that the worst case of the search is some logarithmic coefficient N.

I would have liked the fix if someone is even more familiar with this source / has a moment to study it.