# Delete with multiple indices is extremely slow--workaround?

Delete is unbelievably slow when deleting multiple elements from a non-packed array.

Is there a robust workaround that will work on any non-packed array?

inds = List /@ RandomSample[Range[100000], 50000];
Delete[DeveloperFromPackedArray@Range[100000], inds]; // AbsoluteTiming
(* {17.8957, Null} *)


On packed arrays it performs as expected, but my array cannot be packed. It does not necessarily contain numbers.

inds = List /@ RandomSample[Range[100000], 50000];
Delete[Range[100000], inds]; // AbsoluteTiming
(* {0.005767, Null} *)


I did not try to test for this, but one possible explanation is that even when given multiple indices, Delete will delete elements one-by-one, re-allocating the array after each step. If someone feels like testing it, you can try to see if the timing is quadratic in the number of elements deleted.

Exploiting the fact that Delete works fine on packed arrays, we can first construct an index vector, delete the unneeded indices, then finally use the remaining ones to index into the main array.

arr = DeveloperFromPackedArray@Range[100000];
inds = List /@ RandomSample[Range[100000], 50000];

Part[arr, Delete[Range@Length[arr], inds]]; // AbsoluteTiming
(* {0.006371, Null} *)

• Embarrassing for Delete that this method which ought to have terrible time complexity is so much faster... Have you tested some of the other things like delete on unpacked arrays? Dec 3, 2018 at 9:52
• @b3m2a1 I don't think that this has larger complexity... Still it is pretty bad that Delete is not clever enough to do that automatically. I'd suggest to inform Wolfram Support. Dec 3, 2018 at 10:00

Why not use Part assignment (to Sequence[]) instead?

arr = DeveloperFromPackedArray@Range[100000];
inds = List /@ RandomSample[Range[100000],50000];

r1 = Part[arr, Delete[Range@Length[arr], inds]]; //RepeatedTiming
(r2 = arr; r2[[Flatten @ inds]] = Sequence[];) //RepeatedTiming

r1 === r2


{0.0059, Null}

{0.0019, Null}

True

• Nothing is slightly faster than Sequence[] on my laptop. Dec 3, 2018 at 20:11
• @SjoerdC.deVries and Carl, to fully reduce the array the procedure needs to be followed by r2;. Both Sequence and Nothing will now produce same timings as Part+Delete. p.s. to see what I mean try this: r = {1, 2}; r[[1]] = Nothing; Information@r`
– Kuba
Dec 4, 2018 at 7:28