5

I want to check whether a key exists in a dictionary. The most appropriate way, as per my knowledge is: if d_.get(s):. But, while attempting a question on Leetcode, there was a TLE error when I was using this method. However, when I tried if s in d_, TLE was gone. I want to know why in is faster than get().

I tried going through some questions, found this one where there is an explanation for d_.get() v/s d_[s]. None of the questions addressed d_.get() v/s s in d_.

Just in case, some context:

The code that failed with 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))

The code than got accepted with 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))

I always presumed that in would be slower than fetching attributes(here, get()).

CypherX
  • 7,019
  • 3
  • 25
  • 37
Aviral Srivastava
  • 4,058
  • 8
  • 29
  • 81
  • 10
    [You're free to look at the C source code yourself](https://github.com/python/cpython/blob/master/Objects/dictobject.c) - I'm too lazy right now - but I would assume it's because `in` just looks to see if a value exists in the hashtable, whereas `.get()` has to do the additional overhead of actually retrieving that value and allocating temporary memory for it. – Green Cloak Guy Oct 31 '19 at 19:45
  • 1
    Dictionaries are indexed by their keys so you're just doing a simple lookup than having to retrieve any data. – Sayse Oct 31 '19 at 19:45
  • 1
    `d.get(s)` and `s in d` perform two different operations. `d.get()` returns the value from the dictionary or a default value if it doesn't exist. `s in d` returns a boolean value. – Code-Apprentice Oct 31 '19 at 19:47
  • `d.get(key)` also has to perform a method look-up and a function call, making it slower. – iz_ Oct 31 '19 at 19:48
  • @Code-Apprentice Can you answer this? – Aviral Srivastava Oct 31 '19 at 19:48
  • @GreenCloakGuy Can you help me what should I look into it? Sorry for being a noob. – Aviral Srivastava Oct 31 '19 at 19:49
  • @AviralSrivastava I cannot answer your question definitively. My guess is similar to Green Cloak Guy's: `d.get(s)` does a lot more work than `s in d`. – Code-Apprentice Oct 31 '19 at 19:54
  • @iz_, `s in d` also looks up the `__contains__` method and calls it. – kaya3 Oct 31 '19 at 19:56
  • 1
    @kaya3 No, it does not have to perform a lookup for `__contains__` if called via `in`. You can confirm this with `dis`. – iz_ Oct 31 '19 at 20:03
  • 1
    Oh, interesting, it only looks up `__contains__` if it's not a type with a C implementation of that method. – kaya3 Oct 31 '19 at 22:18

3 Answers3

6

Using the dis.dis method from the linked question:

>>> 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

we can clearly see that d.get(key) has to run one more step: the LOAD_METHOD step. Additionally, d.get must deal with more information: it has to:

  1. check for the presence
  2. if it was found, return the value
  3. otherwise, return the specified default value (or None if no default was specified).

Also, from looking at the C code for in and the C code for .get, we can see that they are very similar.

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;
                                                              }

In fact, they are almost the same, but .get has more overhead and must return a value.

However, it seems that d in key will use a faster method if the hash is known, while d.get recalculates the hash every time. Additionally, CALL_METHOD and LOAD_METHOD have much higher overhead than COMPARE_OP, which performs one of the built-in boolean operations. Note that COMPARE_OP will simply jump to here.

rassar
  • 5,412
  • 3
  • 25
  • 41
  • Is `COMPARE_OP` not calling a method? `PyDict_Contains` has to do a similar check to `dict_get_impl`, and up the refcount of one of the boolean objects. – Mad Physicist Oct 31 '19 at 20:24
  • @MadPhysicist It is a method, but I was trying to say that the dis.dis didn't show a `LOAD_METHOD`. Edited. – rassar Oct 31 '19 at 20:26
  • This doesn't actually answer the question. The conclusion from the evidence you've presented seems to be that the time should be nearly identical. – Mad Physicist Oct 31 '19 at 20:28
  • @MadPhysicist I added some information about the different `dis.dis` lines, and the amount of hashing done by each function. – rassar Oct 31 '19 at 20:38
  • 1
    Thank you for adding that. Now there's a clear story here – Mad Physicist Oct 31 '19 at 23:34
2

The time overhead is in calling a method explicitly, as opposed to letting language constructs take care of it. We can demonstrate this with timeit:

>>> timeit.timeit('"__name__" in x', 'x = globals()')
0.037103720999766665
>>> timeit.timeit('x.__contains__("__name__")', 'x = globals()')
0.07471312899997429
>>> timeit.timeit('x["__name__"]', 'x = globals()')
0.03828814600001351
>>> timeit.timeit('x.__getitem__("__name__")', 'x = globals()')
0.07529343100031838
>>> timeit.timeit('x.get("__name__")', 'x = globals()')
0.08261531900006958

I initially started trying to figure out the difference by looking at the source code for __contains__() and .get(), respectively, only to find that they're nearly identical except for .get() incrementing the object's reference count (which should be more or less negligible). Certainly there wasn't enough difference to explain the time difference you'd be seeing.

But, doing tests, we can see that actually using language constructs (in and []) as opposed to the explicit method calls that they would turn into (__contains__() and __getitem__(), respectively), is a full 50% faster.

A full investigation would take a while and more effort than I care to spend, but I hypothesize this is due to some built-in speedups and skipped steps that the interpreter applies - using a language construct instead of explicitly calling a method narrows down the level of complexity that can be expected, and the interpreter could jump straight into the C code without the overhead of calling the method first.

As @rassar's answer demonstrates, this is, in fact, basically what happens.

Green Cloak Guy
  • 23,793
  • 4
  • 33
  • 53
1

The two pieces of code do not do the same thing. Notice how self.memo is set:

self.memo[s] = res

If res is False, the if statement for the get will fail while the if for in will succeed.

Mark Ransom
  • 299,747
  • 42
  • 398
  • 622