Why is python's dict so slow?


  • 0
    H

    I use this code to AC, but it need 1814 ms!!! I can not understand, hope someone to help me. Thinks~

    class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        dic = {}
        for i in nums:
            if i not in dic.keys():
                dic[i] = 1
            else:
                del(dic[i])
        return dic.keys()

  • 1

    Because you're doing it wrong. Instead of

    if i not in dic.keys():
    

    do

    if i not in dic:
    

    which gets it down to about 50-60 ms.


  • 0
    H

    I seem like to find some reason: I replace this if statement(" if i not in dic.keys() ") with " if not dic.has_key(i): " , and then, run time promote to 52ms~~


  • 0
    H

    yes, this statement has something wrong, but why? the before code can be AC, too. why is difference of efficiency so big? Thinks~


  • 0

    Well one is a lookup of a single item in a hash map (expected O(1)) while the other first gathers all items in a list (O(n)) and then searches that list (again O(n)). Of course the latter is much slower.


Log in to reply
 

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