14
$\begingroup$

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.

Improve this question
$\endgroup$
14
$\begingroup$

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} *)
Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ 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? $\endgroup$ – b3m2a1 Dec 3 '18 at 9:52
  • 5
    $\begingroup$ @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. $\endgroup$ – Henrik Schumacher Dec 3 '18 at 10:00
9
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ Nothing is slightly faster than Sequence[] on my laptop. $\endgroup$ – Sjoerd C. de Vries Dec 3 '18 at 20:11
  • $\begingroup$ @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 $\endgroup$ – Kuba♦ Dec 4 '18 at 7:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.