为什么dict()中的key比Python3中的dict.get(key)更快?

阿瓦拉尔·斯里瓦斯塔瓦(Aviral Srivastava)

我想检查字典中是否存在键。据我所知,最合适的方法是:if d_.get(s):但是,在尝试对Leetcode提问时,当我使用此方法时出现TLE错误。但是,当我尝试时if s in d_,TLE消失了。我想知道为什么in比快get()

我试图通过一些问题去,发现这个地方有一个解释d_.get()V / S d_[s]d_.get()v / s均未解决任何问题s in d_

以防万一,一些上下文:

失败的代码if self.memo.get(s):

from typing import List


class Solution:
    def __init__(self):
        self.word_dict = {}
        self.memo = {}

    def word_break(self, s):
        if not s:
            return True
        if self.memo.get(s):
            return self.memo[s]
        res = False
        for word in self.word_dict.keys():
            if len(word) <= len(s) and s[:len(word)] == word:
                res = res or self.word_break(s[len(word):])
                self.memo[s] = res
        return res

    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        for word in wordDict:
            self.word_dict[word] = 1
        return(self.word_break(s))

代码已被接受if s in self.memo

from typing import List


class Solution:
    def __init__(self):
        self.word_dict = {}
        self.memo = {}

    def word_break(self, s):
        if not s:
            return True
        if s in self.memo:
            return self.memo[s]
        res = False
        for word in self.word_dict.keys():
            if len(word) <= len(s) and s[:len(word)] == word:
                res = res or self.word_break(s[len(word):])
                self.memo[s] = res
        return res

    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        for word in wordDict:
            self.word_dict[word] = 1
        return(self.word_break(s))

我一直以为那in会比获取属性(在此处get()

拉萨尔

使用dis.dis链接问题中方法:

>>> import dis
>>> dis.dis(compile('d.get(key)', '', 'eval'))
  1           0 LOAD_NAME                0 (d)
              2 LOAD_METHOD              1 (get)
              4 LOAD_NAME                2 (key)
              6 CALL_METHOD              1
              8 RETURN_VALUE
>>> dis.dis(compile('key in d', '', 'eval'))
  1           0 LOAD_NAME                0 (key)
              2 LOAD_NAME                1 (d)
              4 COMPARE_OP               6 (in)
              6 RETURN_VALUE

我们可以清楚地看到,d.get(key)必须再执行一个步骤:该LOAD_METHOD步骤。此外,d.get必须处理更多信息:它必须:

  1. 检查是否存在
  2. 如果找到,则返回值
  3. 否则,返回指定的默认值(或者None如果未指定默认值)。

另外,通过查看的C代码in和的C代码.get,我们可以看到它们非常相似。

int                                                           static PyObject * 
PyDict_Contains(PyObject *op, PyObject *key)                  dict_get_impl(PyDictObject *self, PyObject *key, PyObject *default_value)
{                                                             {
    Py_hash_t hash;                                               PyObject *val = NULL;
    Py_ssize_t ix;                                                Py_hash_t hash;
    PyDictObject *mp = (PyDictObject *)op;                        Py_ssize_t ix;                       
    PyObject *value;                                           

    if (!PyUnicode_CheckExact(key) ||                             if (!PyUnicode_CheckExact(key) ||                  
        (hash = ((PyASCIIObject *) key)->hash) == -1) {               (hash = ((PyASCIIObject *) key)->hash) == -1) {                             
        hash = PyObject_Hash(key);                                    hash = PyObject_Hash(key);        
        if (hash == -1)                                               if (hash == -1)
            return -1;                                                    return NULL;
    }                                                             }
    ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &value);         ix = (self->ma_keys->dk_lookup) (self, key, hash, &val);                                         
    if (ix == DKIX_ERROR)                                         if (ix == DKIX_ERROR) 
        return -1;                                                    return NULL;
    return (ix != DKIX_EMPTY && value != NULL);                   if (ix == DKIX_EMPTY || val == NULL) {                        
}                                                                     val = default_value;
                                                                  }
                                                                  Py_INCREF(val);
                                                                  return val;
                                                              }

实际上,它们几乎相同,但是.get开销更大,必须返回一个值。

但是,如果已知哈希值,则似乎d in key将使用更快的方法,而d.get每次都会重新计算哈希值。此外,CALL_METHODLOAD_METHOD比更高的开销COMPARE_OP,它执行的一个内置的布尔运算。请注意,COMPARE_OP只会跳到此处

本文收集自互联网,转载请注明来源。

如有侵权,请联系[email protected] 删除。

编辑于
0

我来说两句

0条评论
登录后参与评论

相关文章

Related 相关文章

热门标签

归档