3

我正在使用mathematica 7，并且正在尝试使用单链表（~50,000 个元素）来避免在动态列表中使用 AppendTo 来提高速度。在这个测试中，我可以创建一个包含 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[]...]]]但我不知道在使用此方案时访问和操作元素的好方法。我想这个问题必须解决，$RecursionLimit但我不知道如何解决它。

特别是我希望能够使用

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

在我的代码中。同样，这在列表很小但最终会导致较大列表崩溃的情况下有效。奇怪的是内核并不总是崩溃，而只是随机地用于大型列表。这听起来类似于在 SE 上描述的内容，但我不知道该讨论是否相关。真的，我只需要帮助修改 LL 元素并在mathematica 中正确使用 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*函数。

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 回答