New developments
rasher posted a new answer with clean and well performing code that caused me to look again at this problem. (It well deserves your vote.) I see now that there are good ways to approach this problem that haven't yet been fully developed. Fundamentally rasher's code operates by Sort
, but I don't think even he realized this as Riffle
et al are superfluous. We merely need Ordering
and Part
applied to joined lists of the correct order:
oInsert[list_, val_, pos_] :=
Join[val, list][[ Ordering @ Join[pos, Range @ Length @ list] ]]
In a way rasher solved the problem twice: Riffle
and sa[[ps]] = reps
already place the elements in the proper order; one merely needs to get rid of the zeros. We could use DeleteCases
but pattern based methods are slow. Instead I reimplemented the Riffle
operation in terms of SparseArray
, but to make it efficient I had to be clever and unfortunately here that (so far) implies less clean code.
saInsert[list_, val_, pos_] :=
With[{no = Length@list, ni = Length@val},
SparseArray[
Automatic, {2, no + 1},
0, {1, {{0, ni, no + ni}, {Join[pos, Range@no]}\[Transpose]}, Join[val, list]}
]\[Transpose]["NonzeroValues"]
]
This ugly bit of code manually constructs a two row SparseArray
, the upper row being the insertion elements and the lower being the original list. It then transposes them, and extracts the "NonzeroValues"
. (Despite the name these are actually the non-background values; this code still works correctly with zeros.)
Rudimentary test of both new methods:
oInsert[{a, b, c, d, e}, {W, X, Y, Z}, {1, 2, 4, 6}]
saInsert[{a, b, c, d, e}, {W, X, Y, Z}, {1, 2, 4, 6}]
{W, a, X, b, c, Y, d, e, Z}
{W, a, X, b, c, Y, d, e, Z}
I shall add timings for these functions later, but to summarize my early findings:
multiInsert2
is still the fastest for a limited number of insertions into a long listsaInsert
is superior to all other methods posted so far for a greater number of insertions into a packed listoInsert
is competitive withsaInsert
andrashernator
on unpacked lists. It is faster thanrashernator
on packed lists.
Original Method
If your list is a vector (has no sub-lists) this is perhaps the simplest way, and likely competitively fast:
m = origlist;
m[[{1, 5}]] = {{r, x}, m[[{1, 5}]]}\[Transpose]
Flatten[m]
{r, a, b, c, d, x, e, f, g}
Edit: Ray Koopman points out that this method, by itself, does not handle an edge case in Insert
where the position is one greater than the length of the list, i.e. Insert[{1,2,3}, x, 4]
. This is accounted for in the function below by padding the list as required.
If your list is not a vector (as defined above) we could use a different head for the inserted elements and then replace it with Sequence
to effect a flatten. Here is a function that handles both cases, selecting between the methods for best performance:
multiInsert[list_List, val_, pos_] /; Length@val == Length@pos :=
Module[{m = list, f, pad},
pad[x_] /; Max@pos == Length@list + 1 := AppendTo[m, x];
If[VectorQ[val] && VectorQ[list],
pad[{ }]; m[[pos]] = Transpose @ {val, m[[pos]]}; Flatten[m],
pad[f[]]; m[[pos]] = MapThread[f, {val, m[[pos]]}]; m /. f -> Sequence
]
]
Input is a little different from yours:
multiInsert[Range@15, {a, b, c}, {3, 7, 13}]
{1, 2, a, 3, 4, 5, 6, b, 7, 8, 9, 10, 11, 12, c, 13, 14, 15}
Preallocate Method
Nasser proposed a method of preallocating the array. This idea was promising if it could be optimized because a packed array could be preserved throughout the process theoretically reducing memory and computation time. His implementation was limited in performance because it used a tag that necessitated unpacking and because searching for that tag using Position
is slow. Here is an implementation that directly calculates the runs of original values rather than tagging and finding them afterward.
multiInsert2[list_, val_, pos_] /; Length@val == Length@pos :=
Module[{new, start, end, offset, n1, n2},
{n1, n2} = Length /@ {list, val};
new = ConstantArray[0, n1 + n2];
start = Prepend[pos, 1];
end = Append[pos - 1, n1];
offset = Range[0, n2];
MapThread[
new[[# ;; #2]] = list[[#3 ;; #4]]; &,
{offset + start, offset + end, start, end}
];
new[[pos + Range[0, n2 - 1]]] = val;
new
]
This function appear to be best for a moderate number of insertions into a long list. (See below)
Notes and timings
Ray Koopman posted a very elegant method, which on reflection I've seen before though I cannot remember where. I voted for that method but there is reason to use the longer forms that belisarius and I proposed: speed on long lists. Every Insert
operation reallocates the array which takes time proportional to the length of the list. As such, a method using Fold
will slow down considerably when doing many insertions into a very long list. I will call Ray Koopman's code foldInsert
:
foldInsert[list_, val_, pos_] /; Length@val == Length@pos :=
Fold[
Insert[#1, #2[[2]], #2[[1]]] &,
list,
Reverse @ Sort @ Transpose @ {pos, val}
]
And using this timing code for the three functions multiInsert
, multiInsert2
, foldInsert
:
timeAvg =
Function[func,
Do[If[# > 0.3, Return[#/5^i]] & @@ Timing@Do[func, {5^i}], {i, 0, 15}],
HoldFirst];
time[n_Integer, k_Integer, rand_: RandomInteger] :=
Module[{start, vals, pos},
start = Range@n;
vals = rand[9, k];
pos = Sort @ RandomSample[start, k];
timeAvg @ #[start, vals, pos] & /@ {multiInsert, multiInsert2, foldInsert}
]
With 3500 insertions into a length 5000 list:
time[5000, 3500]
{0.0017968, 0.007368, 0.01372}
With five insertions into a length 500,000 list:
time[500000, 5]
{0.02432, 0.0006736, 0.001448}
With 7500 insertions into the length 500,000 list:
time[500000, 7500]
{0.03244, 0.01812, 5.038}
All timings above were performing with integer into integer insertions. If inserting reals unpacking is necessary. Here are a few timings for that situation:
time[150000, 50, RandomReal]
time[150000, 500, RandomReal]
time[150000, 5000, RandomReal]
{0.01372, 0.005488, 0.0624}
{0.01308, 0.007368, 0.592}
{0.01684, 0.01748, 8.658}