是否有一個模塊在Erlang中實現了高效的數組類型？

我一直在尋找在Erlang中具有以下特徵的數組類型。是否有一個模塊在Erlang中實現了高效的數組類型？

append(vector(), term())  O(1) 
nth(Idx, vector())    O(1) 
set(Idx, vector(), term())  O(1) 
insert(Idx, vector(), term()) O(N) 
remove(Idx, vector())   O(N)

我通常使用一個元組用於此目的，但是性能特點是不是我所希望的大N.我的測試表明以下性能特點...

erlang:append_element/2   O(N). 
erlang:setelement/3    O(N).

我已經開始在基於clojure.lang.PersistentVector實現的模塊上，但如果它已經完成，我不會重新發明輪子。

編輯：

對於那些有興趣，我已經完成了實施vector.erl ......使用相同的算法爲clojure.lang.PersistentVector。它具有與陣列模塊相似的性能特徵，但在追加時具有稍好的常數因子。

下面的測試每間隔追加10000個項目，然後在隨機索引處進行10000次查找和10000次更新。所有操作都在O（1）附近。內部元組的時間以微秒爲單位。

3> seq_perf:test(vector, 100000, 10). 
{2685854, 
{ok,[{100000,{66966,88437,124376}}, 
     {200000,{66928,76882,125677}}, 
     {300000,{68030,76506,116753}}, 
     {400000,{72429,76852,118263}}, 
     {500000,{66296,84967,119828}}, 
     {600000,{66953,78155,116984}}, 
     {700000,{65996,77815,138046}}, 
     {800000,{67801,78455,118191}}, 
     {900000,{69489,77882,114886}}, 
     {1000000,{67444,80079,118428}}]}} 
4> seq_perf:test(array, 100000, 10). 
{2948361, 
{ok,[{100000,{105482,72841,108828}}, 
     {200000,{123655,78898,124092}}, 
     {300000,{110023,76130,106806}}, 
     {400000,{104126,73830,119640}}, 
     {500000,{104771,72593,110157}}, 
     {600000,{107306,72543,109713}}, 
     {700000,{122066,73340,110662}}, 
     {800000,{105853,72841,110618}}, 
     {900000,{105267,73090,106529}}, 
     {1000000,{103445,73206,109939}}]}}

來源

2012-09-12 dsmith

在PersistentVector實現中似乎有一些有用的技巧可以應用於Erlang數組模塊，例如拖延尾部插入。 – RichardC

確實。數組模塊使用一些技巧來用'undefined'未設置的索引來擴展數組。它似乎也壓縮了大量未定義的元素。 – dsmith

這些屬性在純功能實現中是不可能的。數組模塊（http://www.erlang.org/doc/man/array.html）是一個很好的折衷方案，但是如果您需要O（1）查找和更新，則必須使用ETS表。

來源

2012-09-12 21:36:45 RichardC

我完全錯過了這個模塊。它似乎有O（1）用於更新和查找（或至少接近常數）。正是我在找什麼。謝謝。 – dsmith

是否有一個模塊在Erlang中實現了高效的數組類型？

回答

相關問題