python中有什么哈希表吗

2024-03-29 11:57:32 发布

您现在位置:Python中文网/ 问答频道 /正文

我试图在这里和Python-doc中找到答案,但我得到的只有关于哈希列表对象的问题,以及关于dict如何工作的细节。在

背景

我正在开发一个程序来解析一个巨大的图形(atm)。44K个节点,其中14K个节点是有意义的,它们是由15K个边连接的)虽然我已经尽我所能优化了我的算法,现在最后的办法是优化数据结构:

def single_pass_build(nodes):
    for node in nodes:
        if node.__class__ in listOfRequiredClasses:
            children = get_children(node)
            for child in children:
                if child__class__ in listOfRequiredClasses:
                    add_edge(node, child)

def get_children(node):
    return [attr for attr in node.__dict__.values() if attr.__class__ in listOfRequiredClasses]

我仍然需要关心我的add_connection函数,但是即使没有它,我的程序也要花10分钟多一点的时间来完成这个迭代。比较:我从中获取数据的模块在不超过5秒钟的时间内从xml文档生成数据。 我总共有44K个对象,每个对象代表关系图中的一个节点。我得到的对象有很多属性,所以我可以尝试优化get_children以了解每个类的所有相关属性,或者只是加快查找速度。list取O(n)(所以如果a是os属性的数量,k是列表中类的数量,那么我得到的是总数O(nak+mak))。我的许多属性类不在这个列表中,所以我更接近最坏情况而不是平均值。我想加快从O(k)到O(1)或至少O(log(k))的查找速度

问题

知道dict的键查找对于许多散列冲突应该是O(log(n)),并且在(很少到)没有哈希冲突的情况下,它变得(几乎)是静态的。在我不关心任何值之后,我想知道是否有一种(哈希)列表优化了x in list
我可以使用一个没有值的dict,但是在将来有70000个查找和更大的图形,每毫秒都很重要。空间不是这里的大问题,因为我预计总共有50个类,在任何情况下都不会超过100个类。在其他情况下,空间也可能是个问题。在

我不希望答案是在标准Python中,但是也许有人知道一个通用的框架,它可以帮助或者让我相信,我没有理由不使用dict来完成这项工作。在


Tags: 对象innodechild列表forgetif