Why does mathematica kernel crash when I access my linked list?

Question

I'm using mathematica 7, and I'm trying to use a singly linked list (~50,000 elements) to avoid using AppendTo in a dynamic list to increase speed. In this test, I can create a list of 10 elements as follows

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

And I try to access it with Part like this (accessing a random element 100 times)

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

This works fine for small lists (10 as above). For reasons I don't understand, this kills the kernel when the list has more elements (like 10^4). I've tried looking around on this site & elsewhere, but just can't figure out how I should be using the linked list. I've even tried to use different implementations like f[e1,f[e2,f[e3,...f[]...]]] but I don't know a nice way to access & manipulate elements when using this scheme. I imagine the problem has to do w/ $RecursionLimit but I don't know how to get around it.

In particular I'd like to be able to use

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

in my code. Again, this works when the list is small but crashes the kernel eventually for larger lists. What's weird is that the kernel doesn't crash always, but only stochastically for large lists. This sounds similar to something that was described here on SE, but I don't know if that discussion is relevant. Really I just need help in modifying LL elements & using LL correctly in mathematica.

Thanks in advance.

Answer 1

I can confirm the crash, but only with a significantly deeper Part specification:

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

So on my system the crash happens with a depth somewhere over 170,000. It also happens, at least at this depth, only when assigning a part rather than merely extracting one:

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

{1.03, {77041, 74008, 29990, 13286, 12762, 48702, 76027, 25009, 31267, 1887}}

---

Recommendation

As an alternative I propose using the 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