Delete with multiple indices is extremely slow--workaround?

Question

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[Developer`FromPackedArray@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.

Answer 1

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 = Developer`FromPackedArray@Range[100000];
inds = List /@ RandomSample[Range[100000], 50000];

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

Answer 2

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

arr = Developer`FromPackedArray@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