2024-03-28 12:27:56 发布
网友
Python 2.7或Python 3.x中是否有内置类型的自平衡二叉搜索树(RED-BLACK,AVL或其他类型)?
我正在寻找与Java的TreeMap或TreeSet等价的东西。
如果没有这样的内置组件,为什么要对它们进行修改?不包括这些工具有什么特别的原因吗?
在标准库中找不到任何树。Python大量使用字典作为内部哈希表(对象、类和模块都基于dict)。因此,dicts得到了极大的优化。这使得搜索树的需求要小得多。为了提高效率,这样的树可以在扩展类型中实现。
据我所知,没有什么特别的原因-我想原因是对于许多应用程序来说,经过高度优化的dict和set实现(它们是哈希表)工作得很好。它们在大多数情况下都足够好。在某些情况下,您肯定需要平衡的二进制搜索树的性能特性(比如基于键的有序遍历,而不是加法顺序),但是这些特性已经远远偏离了常规路径,人们很乐意在这种情况下获取第三方包。
dict
set
我在PyPI上使用bintrees包有很好的经验。它在纯Python和Cython中都实现了不平衡、AVL和红黑二叉树。
我认为其余的原因本质上是历史偶然。如果编写bintrees的人游说将其包含在stdlib中,并且愿意忍受对维护和发布的限制,那么它很可能会加入。(我想,尽管Cython依赖性会引起问题。)
算法复杂度:
对于哈希表(如dict或set),插入和查找是O(1),而对于平衡树,插入和查找是O(log(n))。在树中,键的遍历顺序是O(n),但是要对哈希表执行相同的操作,需要首先对键进行排序,所以是O(n*log(n))。在选择要使用哪种数据结构时,需要考虑要使用哪种操作,并选择在应用程序中最有意义的折衷方案。
在标准库中找不到任何树。Python大量使用字典作为内部哈希表(对象、类和模块都基于dict)。因此,dicts得到了极大的优化。这使得搜索树的需求要小得多。为了提高效率,这样的树可以在扩展类型中实现。
据我所知,没有什么特别的原因-我想原因是对于许多应用程序来说,经过高度优化的
dict
和set
实现(它们是哈希表)工作得很好。它们在大多数情况下都足够好。在某些情况下,您肯定需要平衡的二进制搜索树的性能特性(比如基于键的有序遍历,而不是加法顺序),但是这些特性已经远远偏离了常规路径,人们很乐意在这种情况下获取第三方包。我在PyPI上使用bintrees包有很好的经验。它在纯Python和Cython中都实现了不平衡、AVL和红黑二叉树。
我认为其余的原因本质上是历史偶然。如果编写bintrees的人游说将其包含在stdlib中,并且愿意忍受对维护和发布的限制,那么它很可能会加入。(我想,尽管Cython依赖性会引起问题。)
算法复杂度:
对于哈希表(如dict或set),插入和查找是O(1),而对于平衡树,插入和查找是O(log(n))。在树中,键的遍历顺序是O(n),但是要对哈希表执行相同的操作,需要首先对键进行排序,所以是O(n*log(n))。在选择要使用哪种数据结构时,需要考虑要使用哪种操作,并选择在应用程序中最有意义的折衷方案。
相关问题 更多 >
编程相关推荐