6

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の実装に基づいたモジュールを開始しましたが、すでに実行されている場合は、車輪の再発明は行いません。

編集：

興味のある方のために、clojure.lang.PersistentVectorと同じアルゴリズムを使用してvector.erl...の実装を終了しました。アレイモジュールと同様のパフォーマンス特性を備えていますが、追加時の定数係数がわずかに優れています。

次のテストでは、間隔ごとに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}}]}}
4

1 に答える 1

8

これらのプロパティは、純粋関数型の実装では不可能です。配列モジュール（http://www.erlang.org/doc/man/array.html）は非常に良い妥協案ですが、O（1）のルックアップと更新が必要な場合は、代わりにETSテーブルを使用する必要があります。 。

于 2012-09-12T21:36:45.720 に答える