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.
list-manipulation performance-tuning
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} *)
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.
list-manipulation performance-tuning
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
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.
list-manipulation performance-tuning
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} *)
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.
list-manipulation performance-tuning
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
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
158k13432926
add a comment |
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 forDeletethat 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 thatDeleteis 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
Nothingis slightly faster thanSequenceon 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 byr2;. 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
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
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
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
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 forDeletethat 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 thatDeleteis 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 forDeletethat 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 thatDeleteis 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
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
158k13432926
1
Embarrassing forDeletethat 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 thatDeleteis 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 forDeletethat 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 thatDeleteis not clever enough to do that automatically. I'd suggest to inform Wolfram Support.
– Henrik Schumacher
Dec 3 at 10:00
1
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
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
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
@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
Nothingis slightly faster thanSequenceon 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 byr2;. 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
Nothingis slightly faster thanSequenceon 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 byr2;. 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
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
66.7k385174
Nothingis slightly faster thanSequenceon 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 byr2;. 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 |
Nothingis slightly faster thanSequenceon 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 byr2;. 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
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
@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 |
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.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
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
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
