Most time/space efficient way to check if all elements in list of integers are 0
This is an implementation question for Python 2.7
Say I have a list of integers called nums, and I need to check if all values in nums are equal to zero. nums contains many elements (i.e. more than 10000), with many repeating values.
Using all():
if all(n == 0 for n in set(nums)): # I assume this conversion from list to set helps?
# do something
Using set subtraction:
if set(nums) - {0} == set():
# do something
Edit: better way to do the above approach, courtesy of user U9-Forward
if set(nums) == {0}:
# do something
How do the time and space complexities compare for each of these approaches? Is there a more efficient way to check this?
Note: for this case, I am trying to avoid using numpy/pandas.
python python-2.7 python-2.x
add a comment |
This is an implementation question for Python 2.7
Say I have a list of integers called nums, and I need to check if all values in nums are equal to zero. nums contains many elements (i.e. more than 10000), with many repeating values.
Using all():
if all(n == 0 for n in set(nums)): # I assume this conversion from list to set helps?
# do something
Using set subtraction:
if set(nums) - {0} == set():
# do something
Edit: better way to do the above approach, courtesy of user U9-Forward
if set(nums) == {0}:
# do something
How do the time and space complexities compare for each of these approaches? Is there a more efficient way to check this?
Note: for this case, I am trying to avoid using numpy/pandas.
python python-2.7 python-2.x
1
Second could be nicer:set(nums)=={0}
– U9-Forward
Nov 26 '18 at 7:48
add a comment |
This is an implementation question for Python 2.7
Say I have a list of integers called nums, and I need to check if all values in nums are equal to zero. nums contains many elements (i.e. more than 10000), with many repeating values.
Using all():
if all(n == 0 for n in set(nums)): # I assume this conversion from list to set helps?
# do something
Using set subtraction:
if set(nums) - {0} == set():
# do something
Edit: better way to do the above approach, courtesy of user U9-Forward
if set(nums) == {0}:
# do something
How do the time and space complexities compare for each of these approaches? Is there a more efficient way to check this?
Note: for this case, I am trying to avoid using numpy/pandas.
python python-2.7 python-2.x
This is an implementation question for Python 2.7
Say I have a list of integers called nums, and I need to check if all values in nums are equal to zero. nums contains many elements (i.e. more than 10000), with many repeating values.
Using all():
if all(n == 0 for n in set(nums)): # I assume this conversion from list to set helps?
# do something
Using set subtraction:
if set(nums) - {0} == set():
# do something
Edit: better way to do the above approach, courtesy of user U9-Forward
if set(nums) == {0}:
# do something
How do the time and space complexities compare for each of these approaches? Is there a more efficient way to check this?
Note: for this case, I am trying to avoid using numpy/pandas.
python python-2.7 python-2.x
python python-2.7 python-2.x
edited Nov 26 '18 at 7:51
ericph
asked Nov 26 '18 at 7:46
ericphericph
32
32
1
Second could be nicer:set(nums)=={0}
– U9-Forward
Nov 26 '18 at 7:48
add a comment |
1
Second could be nicer:set(nums)=={0}
– U9-Forward
Nov 26 '18 at 7:48
1
1
Second could be nicer:
set(nums)=={0}– U9-Forward
Nov 26 '18 at 7:48
Second could be nicer:
set(nums)=={0}– U9-Forward
Nov 26 '18 at 7:48
add a comment |
4 Answers
4
active
oldest
votes
Any set conversion of nums won't help as it will iterate the entire list:
if all(n == 0 for n in nums):
# ...
is just fine as it stops at the first non-zero element, disregarding the remainder.
Asymptotically, all these approaches are linear with random data.
Implementational details (no repeated function calls on the generator) makes not any(nums) even faster, but that relies on the absence of any other falsy elements but0, e.g. '' or None.
You can get a x10 speedup by eliminating the explicit comparison and the generator.
– DYZ
Nov 26 '18 at 7:58
How about a case in which nums contains both 0 (int) and 0.0 (float)? Wouldnot any(nums)andall(nums)still work correctly?
– ericph
Nov 26 '18 at 8:12
add a comment |
not any(nums) is probably the fastest because it will stop when/if it finds any non-zero element.
Performance comparison:
a = range(10000)
b = [0] * 10000
%timeit not any(a) # 72 ns, fastest for non-zero lists
%timeit not any(b) # 33 ns, fastest for zero lists
%timeit all(n == 0 for n in a) # 365 ns
%timeit all(n == 0 for n in b) # 350 µs
%timeit set(a)=={0} # 228 µs
%timeit set(b)=={0} # 58 µs
1
And so willall.
– schwobaseggl
Nov 26 '18 at 7:52
@schwobaseggl In fact, your solution is about 10 times slower than mine - because of the generator.
– DYZ
Nov 26 '18 at 7:56
That's a valid point, but it doesn't make your argument any more true.
– schwobaseggl
Nov 26 '18 at 7:58
2
Let us continue this discussion in chat.
– schwobaseggl
Nov 26 '18 at 8:02
1
+1 Because you're timings look good. (I was running timings myself, but you beat me too it). But 'all()' doesn't provide a correct solution. all([0]) returns false where all elements are zero, true is correct. You can't just add a 'not' in front because all([0,1]) also returns false which is correct. If you think about it, you will realize 'all' is not the right test. All your other tests look good.
– jimhark
Nov 26 '18 at 8:41
|
show 4 more comments
If you can use numpy, then (np.array(nums) == 0).all() should do it.
1
That's unlikely to help since the list needs to be read fully to just create the array.
– Hannes Ovrén
Nov 26 '18 at 7:51
add a comment |
Additionally to @schwobaseggl's answer, second example could be even better:
if set(nums)=={0}:
# do something
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
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',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
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%2fstackoverflow.com%2fquestions%2f53476653%2fmost-time-space-efficient-way-to-check-if-all-elements-in-list-of-integers-are-0%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
4 Answers
4
active
oldest
votes
4 Answers
4
active
oldest
votes
active
oldest
votes
active
oldest
votes
Any set conversion of nums won't help as it will iterate the entire list:
if all(n == 0 for n in nums):
# ...
is just fine as it stops at the first non-zero element, disregarding the remainder.
Asymptotically, all these approaches are linear with random data.
Implementational details (no repeated function calls on the generator) makes not any(nums) even faster, but that relies on the absence of any other falsy elements but0, e.g. '' or None.
You can get a x10 speedup by eliminating the explicit comparison and the generator.
– DYZ
Nov 26 '18 at 7:58
How about a case in which nums contains both 0 (int) and 0.0 (float)? Wouldnot any(nums)andall(nums)still work correctly?
– ericph
Nov 26 '18 at 8:12
add a comment |
Any set conversion of nums won't help as it will iterate the entire list:
if all(n == 0 for n in nums):
# ...
is just fine as it stops at the first non-zero element, disregarding the remainder.
Asymptotically, all these approaches are linear with random data.
Implementational details (no repeated function calls on the generator) makes not any(nums) even faster, but that relies on the absence of any other falsy elements but0, e.g. '' or None.
You can get a x10 speedup by eliminating the explicit comparison and the generator.
– DYZ
Nov 26 '18 at 7:58
How about a case in which nums contains both 0 (int) and 0.0 (float)? Wouldnot any(nums)andall(nums)still work correctly?
– ericph
Nov 26 '18 at 8:12
add a comment |
Any set conversion of nums won't help as it will iterate the entire list:
if all(n == 0 for n in nums):
# ...
is just fine as it stops at the first non-zero element, disregarding the remainder.
Asymptotically, all these approaches are linear with random data.
Implementational details (no repeated function calls on the generator) makes not any(nums) even faster, but that relies on the absence of any other falsy elements but0, e.g. '' or None.
Any set conversion of nums won't help as it will iterate the entire list:
if all(n == 0 for n in nums):
# ...
is just fine as it stops at the first non-zero element, disregarding the remainder.
Asymptotically, all these approaches are linear with random data.
Implementational details (no repeated function calls on the generator) makes not any(nums) even faster, but that relies on the absence of any other falsy elements but0, e.g. '' or None.
edited Nov 26 '18 at 8:06
answered Nov 26 '18 at 7:48
schwobasegglschwobaseggl
37.2k32442
37.2k32442
You can get a x10 speedup by eliminating the explicit comparison and the generator.
– DYZ
Nov 26 '18 at 7:58
How about a case in which nums contains both 0 (int) and 0.0 (float)? Wouldnot any(nums)andall(nums)still work correctly?
– ericph
Nov 26 '18 at 8:12
add a comment |
You can get a x10 speedup by eliminating the explicit comparison and the generator.
– DYZ
Nov 26 '18 at 7:58
How about a case in which nums contains both 0 (int) and 0.0 (float)? Wouldnot any(nums)andall(nums)still work correctly?
– ericph
Nov 26 '18 at 8:12
You can get a x10 speedup by eliminating the explicit comparison and the generator.
– DYZ
Nov 26 '18 at 7:58
You can get a x10 speedup by eliminating the explicit comparison and the generator.
– DYZ
Nov 26 '18 at 7:58
How about a case in which nums contains both 0 (int) and 0.0 (float)? Would
not any(nums) and all(nums) still work correctly?– ericph
Nov 26 '18 at 8:12
How about a case in which nums contains both 0 (int) and 0.0 (float)? Would
not any(nums) and all(nums) still work correctly?– ericph
Nov 26 '18 at 8:12
add a comment |
not any(nums) is probably the fastest because it will stop when/if it finds any non-zero element.
Performance comparison:
a = range(10000)
b = [0] * 10000
%timeit not any(a) # 72 ns, fastest for non-zero lists
%timeit not any(b) # 33 ns, fastest for zero lists
%timeit all(n == 0 for n in a) # 365 ns
%timeit all(n == 0 for n in b) # 350 µs
%timeit set(a)=={0} # 228 µs
%timeit set(b)=={0} # 58 µs
1
And so willall.
– schwobaseggl
Nov 26 '18 at 7:52
@schwobaseggl In fact, your solution is about 10 times slower than mine - because of the generator.
– DYZ
Nov 26 '18 at 7:56
That's a valid point, but it doesn't make your argument any more true.
– schwobaseggl
Nov 26 '18 at 7:58
2
Let us continue this discussion in chat.
– schwobaseggl
Nov 26 '18 at 8:02
1
+1 Because you're timings look good. (I was running timings myself, but you beat me too it). But 'all()' doesn't provide a correct solution. all([0]) returns false where all elements are zero, true is correct. You can't just add a 'not' in front because all([0,1]) also returns false which is correct. If you think about it, you will realize 'all' is not the right test. All your other tests look good.
– jimhark
Nov 26 '18 at 8:41
|
show 4 more comments
not any(nums) is probably the fastest because it will stop when/if it finds any non-zero element.
Performance comparison:
a = range(10000)
b = [0] * 10000
%timeit not any(a) # 72 ns, fastest for non-zero lists
%timeit not any(b) # 33 ns, fastest for zero lists
%timeit all(n == 0 for n in a) # 365 ns
%timeit all(n == 0 for n in b) # 350 µs
%timeit set(a)=={0} # 228 µs
%timeit set(b)=={0} # 58 µs
1
And so willall.
– schwobaseggl
Nov 26 '18 at 7:52
@schwobaseggl In fact, your solution is about 10 times slower than mine - because of the generator.
– DYZ
Nov 26 '18 at 7:56
That's a valid point, but it doesn't make your argument any more true.
– schwobaseggl
Nov 26 '18 at 7:58
2
Let us continue this discussion in chat.
– schwobaseggl
Nov 26 '18 at 8:02
1
+1 Because you're timings look good. (I was running timings myself, but you beat me too it). But 'all()' doesn't provide a correct solution. all([0]) returns false where all elements are zero, true is correct. You can't just add a 'not' in front because all([0,1]) also returns false which is correct. If you think about it, you will realize 'all' is not the right test. All your other tests look good.
– jimhark
Nov 26 '18 at 8:41
|
show 4 more comments
not any(nums) is probably the fastest because it will stop when/if it finds any non-zero element.
Performance comparison:
a = range(10000)
b = [0] * 10000
%timeit not any(a) # 72 ns, fastest for non-zero lists
%timeit not any(b) # 33 ns, fastest for zero lists
%timeit all(n == 0 for n in a) # 365 ns
%timeit all(n == 0 for n in b) # 350 µs
%timeit set(a)=={0} # 228 µs
%timeit set(b)=={0} # 58 µs
not any(nums) is probably the fastest because it will stop when/if it finds any non-zero element.
Performance comparison:
a = range(10000)
b = [0] * 10000
%timeit not any(a) # 72 ns, fastest for non-zero lists
%timeit not any(b) # 33 ns, fastest for zero lists
%timeit all(n == 0 for n in a) # 365 ns
%timeit all(n == 0 for n in b) # 350 µs
%timeit set(a)=={0} # 228 µs
%timeit set(b)=={0} # 58 µs
edited Nov 26 '18 at 8:43
answered Nov 26 '18 at 7:51
DYZDYZ
26.5k62049
26.5k62049
1
And so willall.
– schwobaseggl
Nov 26 '18 at 7:52
@schwobaseggl In fact, your solution is about 10 times slower than mine - because of the generator.
– DYZ
Nov 26 '18 at 7:56
That's a valid point, but it doesn't make your argument any more true.
– schwobaseggl
Nov 26 '18 at 7:58
2
Let us continue this discussion in chat.
– schwobaseggl
Nov 26 '18 at 8:02
1
+1 Because you're timings look good. (I was running timings myself, but you beat me too it). But 'all()' doesn't provide a correct solution. all([0]) returns false where all elements are zero, true is correct. You can't just add a 'not' in front because all([0,1]) also returns false which is correct. If you think about it, you will realize 'all' is not the right test. All your other tests look good.
– jimhark
Nov 26 '18 at 8:41
|
show 4 more comments
1
And so willall.
– schwobaseggl
Nov 26 '18 at 7:52
@schwobaseggl In fact, your solution is about 10 times slower than mine - because of the generator.
– DYZ
Nov 26 '18 at 7:56
That's a valid point, but it doesn't make your argument any more true.
– schwobaseggl
Nov 26 '18 at 7:58
2
Let us continue this discussion in chat.
– schwobaseggl
Nov 26 '18 at 8:02
1
+1 Because you're timings look good. (I was running timings myself, but you beat me too it). But 'all()' doesn't provide a correct solution. all([0]) returns false where all elements are zero, true is correct. You can't just add a 'not' in front because all([0,1]) also returns false which is correct. If you think about it, you will realize 'all' is not the right test. All your other tests look good.
– jimhark
Nov 26 '18 at 8:41
1
1
And so will
all.– schwobaseggl
Nov 26 '18 at 7:52
And so will
all.– schwobaseggl
Nov 26 '18 at 7:52
@schwobaseggl In fact, your solution is about 10 times slower than mine - because of the generator.
– DYZ
Nov 26 '18 at 7:56
@schwobaseggl In fact, your solution is about 10 times slower than mine - because of the generator.
– DYZ
Nov 26 '18 at 7:56
That's a valid point, but it doesn't make your argument any more true.
– schwobaseggl
Nov 26 '18 at 7:58
That's a valid point, but it doesn't make your argument any more true.
– schwobaseggl
Nov 26 '18 at 7:58
2
2
Let us continue this discussion in chat.
– schwobaseggl
Nov 26 '18 at 8:02
Let us continue this discussion in chat.
– schwobaseggl
Nov 26 '18 at 8:02
1
1
+1 Because you're timings look good. (I was running timings myself, but you beat me too it). But 'all()' doesn't provide a correct solution. all([0]) returns false where all elements are zero, true is correct. You can't just add a 'not' in front because all([0,1]) also returns false which is correct. If you think about it, you will realize 'all' is not the right test. All your other tests look good.
– jimhark
Nov 26 '18 at 8:41
+1 Because you're timings look good. (I was running timings myself, but you beat me too it). But 'all()' doesn't provide a correct solution. all([0]) returns false where all elements are zero, true is correct. You can't just add a 'not' in front because all([0,1]) also returns false which is correct. If you think about it, you will realize 'all' is not the right test. All your other tests look good.
– jimhark
Nov 26 '18 at 8:41
|
show 4 more comments
If you can use numpy, then (np.array(nums) == 0).all() should do it.
1
That's unlikely to help since the list needs to be read fully to just create the array.
– Hannes Ovrén
Nov 26 '18 at 7:51
add a comment |
If you can use numpy, then (np.array(nums) == 0).all() should do it.
1
That's unlikely to help since the list needs to be read fully to just create the array.
– Hannes Ovrén
Nov 26 '18 at 7:51
add a comment |
If you can use numpy, then (np.array(nums) == 0).all() should do it.
If you can use numpy, then (np.array(nums) == 0).all() should do it.
answered Nov 26 '18 at 7:49
Thomas LangThomas Lang
44627
44627
1
That's unlikely to help since the list needs to be read fully to just create the array.
– Hannes Ovrén
Nov 26 '18 at 7:51
add a comment |
1
That's unlikely to help since the list needs to be read fully to just create the array.
– Hannes Ovrén
Nov 26 '18 at 7:51
1
1
That's unlikely to help since the list needs to be read fully to just create the array.
– Hannes Ovrén
Nov 26 '18 at 7:51
That's unlikely to help since the list needs to be read fully to just create the array.
– Hannes Ovrén
Nov 26 '18 at 7:51
add a comment |
Additionally to @schwobaseggl's answer, second example could be even better:
if set(nums)=={0}:
# do something
add a comment |
Additionally to @schwobaseggl's answer, second example could be even better:
if set(nums)=={0}:
# do something
add a comment |
Additionally to @schwobaseggl's answer, second example could be even better:
if set(nums)=={0}:
# do something
Additionally to @schwobaseggl's answer, second example could be even better:
if set(nums)=={0}:
# do something
answered Nov 26 '18 at 7:50
U9-ForwardU9-Forward
15.1k41438
15.1k41438
add a comment |
add a comment |
Thanks for contributing an answer to Stack Overflow!
- 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%2fstackoverflow.com%2fquestions%2f53476653%2fmost-time-space-efficient-way-to-check-if-all-elements-in-list-of-integers-are-0%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
1
Second could be nicer:
set(nums)=={0}– U9-Forward
Nov 26 '18 at 7:48