Counting Objects in C++

在c++中对给定类分配的所有对象进行计数并不困难，除非您必须处理分散注意力的问题。

有时候简单的事情很简单，但它们仍然很微妙。例如，假设您有一个类Widget，并且希望有一种方法能够在运行时查明存在多少Widget对象。一种既容易实现又给出正确答案的方法是在Widget中创建静态计数器，每次调用Widget构造函数时递增计数器，每次调用Widget析构函数时递减计数器。您还需要一个静态成员函数how many来报告当前有多少Widget。如果Widget什么也不做，只是跟踪它的类型存在的数量，那么它看起来或多或少是这样的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Widget {
public:
    Widget() { ++count; }
    Widget(const Widget&) { ++count; }
    ~Widget() { --count; }

    static size_t howMany()
    { return count; }

private:
    static size_t count;
};

// obligatory definition of count. This
// goes in an implementation file
size_t Widget::count = 0;

Read More

翻译自Why Python is Slow: Looking Under the Hood

我们以前都听说过 : Python很慢。

当我在Python上讲授关于科学计算的课程时，我在课程的早期就提出了这个观点，并告诉学生们为什么:它归结为Python是一种动态类型的解释语言，它的值不是存储在密集的缓冲区中，而是存储在分散的对象中。然后我将讨论如何通过使用NumPy、SciPy和相关工具对操作进行矢量化并调用到编译后的代码，然后继续。

但最近我意识到一些事情:尽管上面的陈述相对准确，“动态类型-解释-缓存-向量-编译”这个词对参加入门编程研讨会的人来说可能没什么意义。可以说，这些术语并不能让人们了解“幕后”到底在发生什么。

所以我决定写这篇文章，深入研究我经常忽略的细节。在此过程中，我们将研究如何使用Python的标准库来反思CPython本身的问题。因此，无论您是新手还是经验丰富的程序员，我希望您能从下面的探索中学到一些东西。

Read More

662. Maximum Width of Binary Tree bangbang

一上来的思路就是层次遍历，一开始用的是deque，这样的话就要自己往里面加分隔符，确定宽度。还有就是遇到空节点也不能停，要接着向队列里面压入两个空节点，然后每一层结束时判断最左非空节点和最右非空节点之间的节点数。
然后超时了。。。看了一下调用栈，就是空节点太多了，然后转回溯法试了一下，还是没能解决空节点的问题。注意的是每一层最左非空节点的左边的节点都不用考虑，右边的同理，然后用了两个数组进行层次遍历，然后加了一些小trick，每层最左最右的空节点直接跳过，勉勉强强的AC了，代码最后也是很丑陋。
然后看了top1的代码。。。思路真的很巧妙。。一开始我也往这边想了，就是贴着两边找，但是不知道怎么确定位置。位置这点怎么能没想到呢，刚刷完堆的题，对于完全二叉树，每个节点的紧凑表示后的位置是确定的啊！那然后给每个节点一个编号，然后随意遍历这棵树，看同一层中的编号的差值就好了。
现在觉得棒棒，多刷刷可能就好了。树的核心思想就是那几个遍历，这道题其实没有脱离框架的。

Read More

1. 散列表概述

C++的 STL 中的 map 就是一种关联容器,map 的实现基于 RB-tree(红黑树)，理论上,其搜索的复杂度为 O(logN)。Python 中同样提供关联式容器,即 PyDictObject 对象。与 map 不同的是,PyDictObject 对搜索的效率要求及其苛刻,这也是因为 PyDictObject 在 Python 本身的实现中被大量地采用,比如会通过 PyDictObject 来建立符号表。因此,PyDictObject 采用了散列表(hashtable)。理论上,在最优情况下,散列表能提供 O(1)复杂度的搜索效率。
有很多种方法可以用来解决产生的散列冲突,比如说开链法,这是 SGI STL 中的 hash table 所采用的方法;而 Python 中所采用的是另一种方法,即开放定址法。当产生散列冲突时, Python 会通过一个二次探测函数,计算下一个候选位置,如果这个位置可用,则可将待插入元素放到这个位置，如果不行将继续探测。

2. PyDictObject

2.1 关联容器的entry

在此后的描述中,我们将把关联容器中的一个(键,值)元素对称为一个 entry。

1
2
3
4
5
6
7

[dictobject.h]
typedef struct {
	long ma_hash;
	 /* cached hash code of ma_key */
	PyObject *ma_key;
	PyObject *ma_value;
} PyDictEntry;

Read More

1. PyListObject对象

PyListObject 对象可以有效地支持插入,添加,删除等操作,在 Python 的列表中,无一例外地存放的都是 PyObject 的指针。所以实际上,你可以这样看待 Python 中的列表: vector<PyObject*>。

1
2
3
4
5
6
7

[listobject.h]
typedef struct {
	PyObject_VAR_HEAD
	/* Vector of pointers to list elements. list[0] is ob_item[0],etc.*/
	PyObject **ob_item;
	int allocated;
} PyListObject;

PyObject_VAR_HEAD中的 ob_size 和 allocated 都和内存的管理有关，类似于C++ 中 vector 的 size 和 capacity ，allocated存放的是当前已经申请到的内存数量，而ob_size是实际存储的元素个数。因此一定满足：

1. 0 <= ob_size <= allocatted
2. len(list) == ob_size
3. ob_item == NULL 则 ob_size == allocated == 0

Read More