Delete with multiple indices is extremely slow--workaround?

up vote
13
down vote

favorite

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.

edited Dec 4 at 6:56

xzczd

25.7k469245

asked Dec 3 at 9:40

Szabolcs

158k13432926

add a comment |

up vote
13
down vote

favorite

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} *)

edited Dec 4 at 6:56

xzczd

25.7k469245

asked Dec 3 at 9:40

Szabolcs

158k13432926

add a comment |

up vote
13
down vote

favorite

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} *)

edited Dec 4 at 6:56

xzczd

25.7k469245

asked Dec 3 at 9:40

Szabolcs

158k13432926

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} *)

list-manipulation performance-tuning

edited Dec 4 at 6:56

xzczd

25.7k469245

asked Dec 3 at 9:40

Szabolcs

158k13432926

edited Dec 4 at 6:56

xzczd

25.7k469245

asked Dec 3 at 9:40

Szabolcs

158k13432926

edited Dec 4 at 6:56

xzczd

25.7k469245

edited Dec 4 at 6:56

xzczd

25.7k469245

edited Dec 4 at 6:56

xzczd

25.7k469245

asked Dec 3 at 9:40

Szabolcs

158k13432926

asked Dec 3 at 9:40

Szabolcs

158k13432926

asked Dec 3 at 9:40

Szabolcs

158k13432926

add a comment |

2 Answers
2

active

oldest

votes

up vote
14
down vote

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} *)

answered Dec 3 at 9:42

Szabolcs

158k13432926

1

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?
– b3m2a1
Dec 3 at 9:52

3

@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.
– Henrik Schumacher
Dec 3 at 10:00

add a comment |

up vote
7
down vote

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

answered Dec 3 at 19:23

Carl Woll

66.7k385174

Nothing is slightly faster than Sequence on my laptop.
– Sjoerd C. de Vries
Dec 3 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 at 7:28

add a comment |

Your Answer

StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\$","\$"]]);
});
});
}, "mathjax-editing");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "387"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});

}
});

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmathematica.stackexchange.com%2fquestions%2f187206%2fdelete-with-multiple-indices-is-extremely-slow-workaround%23new-answer', 'question_page');
}
);

Post as a guest

Name

Required, but never shown

2 Answers
2

active

oldest

votes

2 Answers
2

active

oldest

votes

up vote
14
down vote

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} *)

answered Dec 3 at 9:42

Szabolcs

158k13432926

1

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?
– b3m2a1
Dec 3 at 9:52

3

@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.
– Henrik Schumacher
Dec 3 at 10:00

add a comment |

up vote
14
down vote

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} *)

answered Dec 3 at 9:42

Szabolcs

158k13432926

1

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?
– b3m2a1
Dec 3 at 9:52

3

@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.
– Henrik Schumacher
Dec 3 at 10:00

add a comment |

up vote
14
down vote

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} *)

answered Dec 3 at 9:42

Szabolcs

158k13432926

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} *)

answered Dec 3 at 9:42

Szabolcs

158k13432926

answered Dec 3 at 9:42

Szabolcs

158k13432926

answered Dec 3 at 9:42

Szabolcs

158k13432926

answered Dec 3 at 9:42

Szabolcs

158k13432926

1

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?
– b3m2a1
Dec 3 at 9:52

3

@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.
– Henrik Schumacher
Dec 3 at 10:00

add a comment |

1

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?
– b3m2a1
Dec 3 at 9:52

3

@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.
– Henrik Schumacher
Dec 3 at 10:00

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?
– b3m2a1
Dec 3 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.
– Henrik Schumacher
Dec 3 at 10:00

add a comment |

up vote
7
down vote

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

answered Dec 3 at 19:23

Carl Woll

66.7k385174

Nothing is slightly faster than Sequence on my laptop.
– Sjoerd C. de Vries
Dec 3 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 at 7:28

add a comment |

up vote
7
down vote

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

answered Dec 3 at 19:23

Carl Woll

66.7k385174

Nothing is slightly faster than Sequence on my laptop.
– Sjoerd C. de Vries
Dec 3 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 at 7:28

add a comment |

up vote
7
down vote

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

answered Dec 3 at 19:23

Carl Woll

66.7k385174

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

answered Dec 3 at 19:23

Carl Woll

66.7k385174

answered Dec 3 at 19:23

Carl Woll

66.7k385174

answered Dec 3 at 19:23

Carl Woll

66.7k385174

answered Dec 3 at 19:23

Carl Woll

66.7k385174

Nothing is slightly faster than Sequence on my laptop.
– Sjoerd C. de Vries
Dec 3 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 at 7:28

add a comment |

Nothing is slightly faster than Sequence on my laptop.
– Sjoerd C. de Vries
Dec 3 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 at 7:28

Nothing is slightly faster than Sequence on my laptop.
– Sjoerd C. de Vries
Dec 3 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 at 7:28

add a comment |

draft saved

draft discarded

Thanks for contributing an answer to Mathematica Stack Exchange!

Please be sure to answer the question. Provide details and share your research!

But avoid …

Asking for help, clarification, or responding to other answers.

Making statements based on opinion; back them up with references or personal experience.

Use MathJax to format equations. MathJax reference.

To learn more, see our tips on writing great answers.

Some of your past answers have not been well-received, and you're in danger of being blocked from answering.

Please pay close attention to the following guidance:

Please be sure to answer the question. Provide details and share your research!

But avoid …

Asking for help, clarification, or responding to other answers.

Making statements based on opinion; back them up with references or personal experience.

To learn more, see our tips on writing great answers.

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Name

Required, but never shown

Name

Required, but never shown

This page is only for reference, If you need detailed information, please check here

搜尋此網誌

Argthtjtr