Python中用tuple作为key

其实当我得到这个结论的时候,我觉得很简单很正常,但是我第一次看到这个用法时,我觉得很新奇:

class Solution(object):
    def lenLongestFibSubseq(self, A):
        index = {x: i for i, x in enumerate(A)}
        longest = collections.defaultdict(lambda: 2)

        ans = 0
        for k, z in enumerate(A):
            for j in xrange(k):
                i = index.get(z - A[j], None)
                if i is not None and i < j:
                    cand = longest[j, k] = longest[i, j] + 1
                    ans = max(ans, cand)

        return ans if ans >= 3 else 0

注意倒数低三行代码中的 longest[j, k],居然可以这样用?一开始我以为是 defaultdict 提供的功能,因此我去翻了一下 collections 的实现,在 _collectionsmodule.c 里,但是没有找到诸如 __getitem__ 的方法,但是我看到 defaultdict 的定义如下:

typedef struct {
    PyDictObject dict;
    PyObject *default_factory;
} defdictobject;

dict 里没有key时,就会去调用 default_factory 拿到默认的key,这么说来,dict 也支持这种用法?我试试:

>>> a = {}
>>> a[1, 2] = 3
>>> a[1,2]
3
>>> a
{(1, 2): 3}

还真的是。看到这里,我大概知道为啥了,因为 1, 2 其实是一个tuple,tuple是不可变对象,是hashable的,来验证一下。但是我没有 找到 __getitem__ 的实现,不过我找到了 key in dict 这个操作的实现:

/* Return 1 if `key` is in dict `op`, 0 if not, and -1 on error. */
int
PyDict_Contains(PyObject *op, PyObject *key)
{
    Py_hash_t hash;
    Py_ssize_t ix;
    PyDictObject *mp = (PyDictObject *)op;
    PyObject *value;

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

/* Internal version of PyDict_Contains used when the hash value is already known */
int
_PyDict_Contains(PyObject *op, PyObject *key, Py_hash_t hash)
{
    PyDictObject *mp = (PyDictObject *)op;
    PyObject *value;
    Py_ssize_t ix;

    ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &value);
    if (ix == DKIX_ERROR)
        return -1;
    return (ix != DKIX_EMPTY && value != NULL);
}

可以看出来,只要 hash = PyObject_Hash(key); 这一步是成功的,就可以。也就是说,只要能算出hash值即可,那么我们可以来试试 把一个class,重写 __hash__ 方法,来看看是否可以做key:

class A(list):
    pass

a = A()

d = {}

d[a] = 1

原本这样是会报错的:

$ python test.py 
Traceback (most recent call last):
  File "test.py", line 8, in <module>
    d[a] = 1
TypeError: unhashable type: 'A'

因为list并不是immutable的,所以没法计算hash值,但是我们可以给他加上方法:

class A(list):
    def __hash__(self):
        return 1

a = A()

d = {}

d[a] = 1

这样就可以了。

好了,到这里终于弄明白为啥可以这样做了。那么 dict[1, 2, 3] 这种写法的好处是啥呢?那就是,原本如果我们遇到了二位矩阵、 三维矩阵时,我们得弄一个矩阵:[[1, 2, 3], [4, 5, 6]] 然后访问其中的数据时,就这样访问:a[1][2],但是有了这个特性 之后,我们可以像最开始的代码那样,结合 defaultdict,然后 a[1, 2] 来访问和赋值,感觉方便了不少。


更多文章
  • Linux高分屏支持
  • GCC默认的头文件搜索路径
  • 读《远见-如何规划职业生涯3大阶段》
  • 后端工程师学前端(五): SASS
  • 后端工程师学前端(四): CSS进阶(盒子模型)
  • 读《投资中最简单的事》
  • 后端工程师学前端(三): CSS进阶(特指度、单位和字体族)
  • 后端工程师学前端(二): CSS基础知识(规则与选择器)
  • Swift语法笔记
  • 读《管理的实践》
  • 后端工程师学前端(一): HTML
  • frp 源码阅读与分析(二):TCP内网穿透的实现
  • 五天不用微信 - 爽得很
  • frp 源码阅读与分析(一):流程和概念
  • 学习frp源码之简洁的在两个connection之间转发流量