Python O(m+n) with clear search strategy


  • 9
    H
    class Solution:
        # @param {integer[][]} matrix
        # @param {integer} target
        # @return {boolean}
        def searchMatrix(self, matrix, target):
            if matrix:
                row,col,width=len(matrix)-1,0,len(matrix[0])
                while row>=0 and col<width:
                    if matrix[row][col]==target:
                        return True
                    elif matrix[row][col]>target:
                        row=row-1
                    else:
                        col=col+1
                return False

  • 0
    W

    good idea, but using 'row -= 1' instead of 'row=row-1' can reduce your running time


  • 0

    @whglamrock No, it can't. In Python, 'a -= b' is 'a = a - b' exactly. But it would be faster in other language. You can see this link text


  • 0
    W

    @Helly0000
    you are wrong. You can use python running time test to see the difference between those two.


  • 0

    @whglamrock Some interpreter can make optimization of '+=' of course. But the code of '+=' in the original edition Python is just using '+'.


  • 0
    W

  • 0
    S

    it's meaningless to argue about such minor improvements.


  • 0
    W

    @hamster
    Yes but who argued first? I just mentioned once.
    Also, when you are writing a long program, minor improvements make difference


  • 0
    S

    @whglamrock Your test program doesn't make a lot sense.

    1. You should separate it to 2 files and then run individually.
    2. Change the order: do the += first and then a+1, what will you see?
    3. 'a' should be reinialized to 1 for the 2nd test case.
    4. You should run each test more than 1 time. Do it for 1000000 times.

    I wrote it for you and please explain me why b += 1 runs slower than the other.

    import timeit
    
    b = 1
    start_time2 = timeit.default_timer()
    for j in range(1000000):
        b += 1
    elapsed2 = timeit.default_timer() - start_time2
    print(elapsed2)
    
    a = 1
    start_time = timeit.default_timer()
    for i in range(1000000):
        a = a + 1
    elapsed = timeit.default_timer() - start_time
    print(elapsed)
    

    output:

    0.1970914805773473
    0.15520109305984495

  • 1

    @Helly0000 said in Python O(m+n) with clear search strategy:

    In Python, 'a -= b' is 'a = a - b' exactly.

    No it isn't.

    >>> import dis
    
    >>> def f():
    	a -= b
    
    >>> def g():
    	a = a - b
    
    >>> dis.dis(f)
      3           0 LOAD_FAST                0 (a)
                  3 LOAD_GLOBAL              0 (b)
                  6 INPLACE_SUBTRACT    
                  7 STORE_FAST               0 (a)
                 10 LOAD_CONST               0 (None)
                 13 RETURN_VALUE        
    >>> dis.dis(g)
      3           0 LOAD_FAST                0 (a)
                  3 LOAD_GLOBAL              0 (b)
                  6 BINARY_SUBTRACT     
                  7 STORE_FAST               0 (a)
                 10 LOAD_CONST               0 (None)
                 13 RETURN_VALUE

  • 1

    @hamster Your test is better, but you're including the range-iteration and times well under a second aren't very trustworthy. This is a better test:

    >>> import timeit
    >>> for _ in range(3):
            for stmt in 'b += 1', 'b = b + 1':
                print(timeit.timeit(stmt, 'b = 1', number=10**8))
            print()
    
    5.103452482432317
    5.0561916657627535
    
    5.056493937881555
    5.120255927733524
    
    5.115592644150922
    5.093014479315229
    

    That's with Python 3 because it looks like that's what you used. Here's Python 2, because that's what LeetCode uses:

    2.3535724448
    2.35552549527
    
    2.32556570107
    2.39999855775
    
    2.32775281713
    2.39187537014
    

  • 2

    @StefanPochmann said in Python O(m+n) with clear search strategy:

    No it isn't.

    Also, maybe this demonstrates it even better:

    >>> a = b = {42}
    >>> a -= b
    >>> b
    set([])
    
    >>> a = b = {42}
    >>> a = a - b
    >>> b
    set([42])
    

Log in to reply
 

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