3

私はmathematica7を使用しており、速度を上げるために動的リストでAppendToを使用しないように、単一リンクリスト(〜50,000要素)を使用しようとしています。このテストでは、次のように10個の要素のリストを作成できます。

list1 = Fold[{#1, #2} &, {}, RandomInteger[10^5, 10]]

そして、私はPartこのようにそれにアクセスしようとします(ランダムな要素に100回アクセスします)

Timing[list1[[Sequence @@ ConstantArray[1, #], 2]] & /@RandomInteger[{1,10}, 100]]

これは、小さなリスト(上記の10)では問題なく機能します。私が理解していない理由で、リストにもっと多くの要素(10 ^ 4など)がある場合、これはカーネルを強制終了します。このサイトや他の場所を見て回ってみましたが、リンクリストをどのように使用すべきかわかりません。のようなさまざまな実装を使用しようとしたこともf[e1,f[e2,f[e3,...f[]...]]]ありますが、このスキームを使用するときに要素にアクセスして操作するための優れた方法がわかりません。問題はw/に関係していると思い$RecursionLimitますが、それを回避する方法がわかりません。

特に使えるようになりたい

list1[[Sequence @@ ConstantArray[1, index], 2]] = new value

私のコードで。繰り返しますが、これはリストが小さい場合は機能しますが、リストが大きい場合は最終的にカーネルをクラッシュさせます。奇妙なことに、カーネルは常にクラッシュするわけではなく、大きなリストの場合にのみ確率的にクラッシュします。これは、ここSEで説明したものと似ていますが、その議論が適切かどうかはわかりません。本当に私はLL要素を修正して数学でLLを正しく使うのに助けが必要です。

前もって感謝します。

4

1 に答える 1

3

クラッシュを確認できますが、かなり深いPart仕様でのみです。

n = 5000000;

list1 = Fold[List, {}, RandomInteger[10^5, n]];

Do[
 list1[[Sequence @@ ConstantArray[1, i], 2]] = "token"; Print[i],
 {i, 100000, 200000, 10000}
]

100000 110000 120000 130000 140000 150000 160000 170000

したがって、私のシステムでは、170,000 を超える深さでクラッシュが発生します。また、少なくともこの深さでは、単にパーツを抽出するのではなく、パーツを割り当てるときにのみ発生します。

Timing[
 list1[[##, 2]] & @@ ConstantArray[1, #] & /@ RandomInteger[{1, n - 1}, 10]
]
{1.03, {77041, 74008, 29990, 13286, 12762, 48702, 76027, 25009, 31267, 1887}}

おすすめ

Internal` *Bag*別の方法として、 functionsを使用することを提案します。

n = 5000000;

list2 = Internal`Bag @ RandomInteger[10^5, n];  (* fill our Bag *)

Internal`StuffBag[list2, 27182];  (* add an element to the Bag *)

Internal`BagLength @ list2  (* check the length of our Bag *)
5000001
pos = RandomInteger[{1, n}, 10];  (* pick ten random positions *)

(* assign to those positions values 1 through 10 *)
MapIndexed[
  (Internal`BagPart[list2, #] = #2[[1]]) &,
  pos
];

Internal`BagPart[list2, pos]  (* check the contents of those positions *)
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
(* convert our Bag into a standard list *)
flat = Internal`BagPart[list2, All];

flat[[pos]]  (* check the contents again *)
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
Last @ flat  (* check that the element we appended is still there *)
27182
于 2012-12-08T12:14:30.273 に答える