Python: why 20% people are getting below 76ms?


  • 1
    W

    I thought the following code exploit the efficiency, given that we use python. But it shows there are 20% submissions run below 76ms, which is my runtime. Can anyone tell me how I can further improve?

    def hasCycle(self, head):
        try:
            head1 = head
            head2 = head.next
            while not head1 is head2:
                head1 = head1.next
                head2 = head2.next.next
            return True
        except:
            return False

  • 0

    But it shows there are 20% submissions run below 76ms,

    No, it shows 3.83% ran below 76ms.

    Your code looks good, you can probably get to 72ms as well just by submitting a few more times and getting lucky eventually.


  • 0
    W

    Oh, I see.. There are 16% submission pilling on the same bin in the histogram. Thanks anyway!


  • 0

    One little thing I just noticed: You could use while head1 is not head2, which is just one operation instead of your two. Though apparently at least CPython optimizes it anyway:

    Experimental:

    >>> import timeit
    >>> timeit.timeit('not 1 is None', number=100000000)
    11.665418612408274
    >>> timeit.timeit('1 is not None', number=100000000)
    11.675055164981785
    

    Disassembling:

    >>> def test():
            return not 1 is None
    
    >>> import dis
    >>> dis.dis(test)
      2           0 LOAD_CONST               1 (1)
                  3 LOAD_CONST               0 (None)
                  6 COMPARE_OP               9 (is not)
                  9 RETURN_VALUE        
    
    >>> def test():
            return 1 is not None
    
    >>> dis.dis(test)
      2           0 LOAD_CONST               1 (1)
                  3 LOAD_CONST               0 (None)
                  6 COMPARE_OP               9 (is not)
                  9 RETURN_VALUE        
    

  • 0
    W

    Yes, it looks they are the same at assembly level in the end. But I guess "is not" might be more Pythonic, and thus I'll jump to that camp:)


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.