python - 在 Python 中创建一个包含 70 万个项目的字典？

Question

我有一个名为 Point 的类，它只有 x_coordinate 和 y_coordinate float 作为其属性。我有大约 700000 个我想存储在字典中的 Point 对象。

字典的键是 Point 对象，对应的值是 Region 对象，其中包含大约一千个点。基本上，键p属于值r，这意味着点对象属于特定区域对象。

长话短说，这是我要执行的原始循环:

look_up_table = {}
for region in all_regions_list:
    for point in region.points_list:
        look_up_table[point] = region

在所有区域中，大约有 700000 个 Point 对象，已经加载到内存中。因此，代码中的第 4 行可能会执行 700k 次，字典将有大约 700k(键，值)对。

假设每个 Point 对象占用 1KB 的内存(这实际上是不可能的)，那么 700000 个 Point 将占用大约 680MB。而且我有超过 3GB 的可用 RAM。此外;那些 Point 和 Region 对象已经加载到内存中......

然而，那些简单的 4 行需要很长时间才能完成，我已经等了大约 2 个小时，但没有运气......仅散列 10k 个对象需要大约一个小时......

那么，我的问题是，我做错了什么吗？有没有另一种方法可以在内存中存储 700k 个对象并能够在 O(1) 时间内查找某个键？

顺便说一句，下面是 Point 类的重写方法:

def __hash__(self, *args, **kwargs):
        """ overriden hash method """
        hashcode = 133
        hashcode = hashcode * 23 + self.x_coordinate
        hashcode = hashcode * 23 + self.y_coordinate
        return hashcode

def __eq__(self, other):
    """ overriden equals method """
    if not other:
        return False
    else:
        return self.__cmp__(other) == 0

def __cmp__(self, other):
    """ overriden compare method """
    if other is not None:
        origin = Point(0.0, 0.0)
        if self.distance_between(origin) < other.distance_between(origin):
            return - 1
        elif self.distance_between(origin) > other.distance_between(origin):
        return 1
        else:
            return 0

提前致谢...

Answer 1

您的代码中至少有一个错误——可能不会导致性能问题，但值得指出。 __hash__() 方法必须根据 Python documentation 满足一项要求:

The only required property is that objects which compare equal have the same hash value; it is advised to somehow mix together (e.g. using exclusive or) the hash values for the components of the object that also play a part in comparison of objects.

根据您的方法定义，比较相等的两个对象完全有可能具有不同的哈希值。