## New developments
[rasher][1] 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}, pos ~Join~ Range[no] ~Partition~ 1}, val ~Join~ 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 list
- `saInsert` is superior to all other methods posted so far for a greater number of insertions into a packed list
- `oInsert` is competitive with `saInsert` and `rashernator` on unpacked lists. It is faster than `rashernator` 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}
[1]: https://mathematica.stackexchange.com/users/11467/rasher