在erlang中实现数组 [英] Arrays implementation in erlang
问题描述
我们的问题是在Erlang中如何实现数组,而不是列表。
My question is, how are 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])
将在堆中占用常量mem,因为这是所有引用的工作。
would take up constant mem in the heap, since this is all reference work.
但是对于数组中的相同内容
But for the same stuff 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).
将移动
这里使用与A2成正比的大小或者是否可以像数组那样在恒定的空间中这样做?
Will move
here use size proportional to A2 or will it be able to do this in constant space like with the arrays?
推荐答案
(希望)清楚一点。请记住,在Erlang 全部数据是不可变的!这深刻地影响了你如何操纵数据。
To (hopefully) clear things up a little. Remember that in Erlang ALL data is immutable! This profoundly affects how you manipulate data.
数组
模块构建一个嵌套元组的结构,其中所有的数组槽包含数据处于同一级别。每个元组的大小是10,所以对于数组访问我们有O(lg10(N))。使用这样的嵌套结构在具有不可变数据的语言中是常见的。您可以将一个数组保存在一个平坦的元组中,这样可以让您快速读取数据,但是对于大型数组/元组而言,写入速度将会变慢,并且内存占用,因为每次写入都需要创建一个新的元组。使用树结构意味着在写入中创建的数据少得多。
The array
module builds a structure of nested tuples where all the array slots containing data are at the same level. The size of each tuple is 10 so for array access we have O(lg10(N)). Using nested structure like this is common in languages with immutable data. You could keep an array in a flat tuple which would give you fast reads, but writes would become slow and memory hogging for large arrays/tuples as every write would entail creating a new tuple. Using a tree structure means that much less data is created in a write.
您的 move / 2
函数如何影响内存使用情况取决于您是否在数组中写入已使用或未使用的插槽。如果插槽已经在使用,那么结果的内存使用情况将是一样的。如果您正在写入以前未使用的插槽,那么您可能需要增加数组,这意味着将使用更多的内存。
How your move/2
function affects memory usage depends a little on whether you are writing to a used or unused slot in the array. If the slot is already in use then the resultant memory usage will be the same. If you are writing to a previously unused slot then you may need to grow the array which mean that more memory will be used.
与您的列表完全相同
它还取决于是否有任何剩余的对旧数据结构的引用。
It also depends on whether there are any remaining references to the old data structure.
这篇关于在erlang中实现数组的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!