Most time/space efficient way to check if all elements in list of integers are 0












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.










share|improve this question




















  • 1





    Second could be nicer: set(nums)=={0}

    – U9-Forward
    Nov 26 '18 at 7:48
















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.










share|improve this question




















  • 1





    Second could be nicer: set(nums)=={0}

    – U9-Forward
    Nov 26 '18 at 7:48














0












0








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.










share|improve this question
















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






share|improve this question















share|improve this question













share|improve this question




share|improve this question








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














  • 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












4 Answers
4






active

oldest

votes


















2














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.






share|improve this answer


























  • 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





















2














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





share|improve this answer





















  • 1





    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













  • 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





















0














If you can use numpy, then (np.array(nums) == 0).all() should do it.






share|improve this answer



















  • 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



















0














Additionally to @schwobaseggl's answer, second example could be even better:



if set(nums)=={0}:
# do something





share|improve this answer























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


    }
    });














    draft saved

    draft discarded


















    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









    2














    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.






    share|improve this answer


























    • 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


















    2














    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.






    share|improve this answer


























    • 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
















    2












    2








    2







    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.






    share|improve this answer















    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.







    share|improve this answer














    share|improve this answer



    share|improve this answer








    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)? Would not any(nums) and all(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











    • 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



















    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















    2














    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





    share|improve this answer





















    • 1





      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













    • 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


















    2














    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





    share|improve this answer





















    • 1





      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













    • 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
















    2












    2








    2







    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





    share|improve this answer















    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






    share|improve this answer














    share|improve this answer



    share|improve this answer








    edited Nov 26 '18 at 8:43

























    answered Nov 26 '18 at 7:51









    DYZDYZ

    26.5k62049




    26.5k62049








    • 1





      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













    • 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





      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













    • 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













    0














    If you can use numpy, then (np.array(nums) == 0).all() should do it.






    share|improve this answer



















    • 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
















    0














    If you can use numpy, then (np.array(nums) == 0).all() should do it.






    share|improve this answer



















    • 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














    0












    0








    0







    If you can use numpy, then (np.array(nums) == 0).all() should do it.






    share|improve this answer













    If you can use numpy, then (np.array(nums) == 0).all() should do it.







    share|improve this answer












    share|improve this answer



    share|improve this answer










    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














    • 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











    0














    Additionally to @schwobaseggl's answer, second example could be even better:



    if set(nums)=={0}:
    # do something





    share|improve this answer




























      0














      Additionally to @schwobaseggl's answer, second example could be even better:



      if set(nums)=={0}:
      # do something





      share|improve this answer


























        0












        0








        0







        Additionally to @schwobaseggl's answer, second example could be even better:



        if set(nums)=={0}:
        # do something





        share|improve this answer













        Additionally to @schwobaseggl's answer, second example could be even better:



        if set(nums)=={0}:
        # do something






        share|improve this answer












        share|improve this answer



        share|improve this answer










        answered Nov 26 '18 at 7:50









        U9-ForwardU9-Forward

        15.1k41438




        15.1k41438






























            draft saved

            draft discarded




















































            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.




            draft saved


            draft discarded














            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





















































            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







            Popular posts from this blog

            Lallio

            Futebolista

            Jornalista