An interesting finding in Python


  • 0
    W

    '''

    def __init__(self, head):
        """
        @param head The linked list's head.
        Note that the head is guaranteed to be not null, so it contains at least one node.
        :type head: ListNode
        """
        self.head = head
        
    
    def getRandom(self):
        """
        Returns a random node's value.
        :rtype: int
        """
        if not self.head:
            return 
        
        count = 0
        tmp = self.head
        ans = tmp.val
        while tmp:
            if random.randint(0, count) is 0:
                ans = tmp.val
            tmp = tmp.next
            count += 1
        return ans
    

    '''

    If I change the "if random.randint(0, count) is 0:" into "if random.randint(0, count) == 0:", it will get TLE.

    @administrators Could you please explain why?


  • 0

    @whglamrock
    Have you tried for one more time? May be it was due to the instability of one of our judger machine.
    I just tried your solution and it was accepted within 400ms.
    According to the complexity of your code, it's rational to be in that range.
    0_1477505293559_upload-b75bd9d0-8809-4603-b28e-c8ed908a32a2


  • 0

    @whglamrock
    Further more, I'd recommend you to use == in this scenario. Each object has an id inside the context of python program, you can use id(x) to get such identity.

    1. == compares the value
    2. is judges whether they are the same object which is equivalent to id(a) == id(b).

  • 0
    W

    @xidui

    Well, I did try few times yesterday. It seems in another similar question Random Pick Index, the "is" operator also faster than "=".


  • 0

    @whglamrock
    Yeah that's an expected behavior.
    Comparing integer directly(use is to compare identity) only takes one CPU cycle, while comparing value(use ==) sometimes need more than one CPU cycle.


Log in to reply
 

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