如何在python中安全地计算字典键

Question

我正在编写一个django应用程序,我将从用户那里获得可变大小的字典.我希望限制字典的大小,即(key, value)它可以容纳多少对字典.我希望它不超过200.我怀疑如果我这样做:

if len(user_dict)>200:
    raise ValidationError("dict has too many (key, value) pairs")

python必须统计整个字典.如果dict是巨大的,由于恶意用户,这将消耗不必要的处理能力.或者dict是否跟踪它拥有多少个对象,这意味着len(user_dict)一个简单的查找操作？解决这个问题的最佳方法是什么？

我想的是:

i=0
for key in user_dict.keys():
    i += 1
    if i>200:
        raise ValidationError("dict has too many (key, value) pairs")

Answer 1

或者dict是否跟踪它拥有多少个对象,这意味着len(user_dict)一个简单的查找操作？

字典 - 给出像CPython这样严格的解释器实现 - 确实跟踪存储在字典中的键值对的数量.所以,如果 user_dict确实是一本字典,那么len(user_dict)在O(1)中工作并且非常快.它在恒定时间内工作的事实也意味着,无论我们计算具有100k项目len(..)的dict对象,还是根本没有项目,它都没有(理论上的)差异.

不需要迭代来计算对象的数量.例如,dict该类的CPython源代码具有:

static Py_ssize_t
dict_length(PyDictObject *mp)
{
    return mp->ma_used;
}

因此它返回ma_used字典对象的字段(因此它是包含字典中项目数的字段).

这个文件中也描述了这个:

Dictionaries: dict and defaultdict
                               Complexity
Operation     | Example      | Class         | Notes
--------------+--------------+---------------+-------------------------------
Index         | d[k]         | O(1)      |
Store         | d[k] = v     | O(1)      |
Length        | len(d)       | O(1)      |
Delete        | del d[k]     | O(1)      |
get/setdefault| d.method     | O(1)      |
Pop           | d.pop(k)     | O(1)      |
Pop item      | d.popitem()  | O(1)      |
Clear         | d.clear()    | O(1)      | similar to s = {} or = dict()
View          | d.keys()     | O(1)      | same for d.values()

Construction  | dict(...)    | O(len(...))   | depends # (key,value) 2-tuples

Iteration     | for k in d:  | O(N)          | all forms: keys, values, items