我目前正在为自己的个人开发在Python中实现Fibonacci堆。在为循环的双链表编写对象类时，遇到了一个我不确定的问题。
为了对链接列表进行快速成员资格测试（以便更快地执行“删除”和“合并”之类的操作），我正在考虑将哈希表（python“设置”对象）添加到我的链接列表类中。有关执行此操作的方法，请参见下面我公认的非常不完善的代码：
class Node:
def __init__(self,value):
self.value = value
self.degree = 0
self.p = None
self.child = None
self.mark = False
self.next = self
self.prev = self
def __lt__(self,other):
return self.value < other.value
class Linked_list:
def __init__(self):
self.root = None
self.nNodes = 0
self.members = set()
def add_node(self,node):
if self.root == None:
self.root = node
else:
self.root.next.prev = node
node.next = self.root.next
self.root.next = node
node.prev = self.root
if node < self.root:
self.root = node
self.members.add(node)
self.nNodes = len(self.members)
def find_min():
min = None
for element in self.members:
if min == None or element<min:
min = element
return min
def remove_node(self,node):
if node not in self.members:
raise ValueError('node not in Linked List')
node.prev.next, node.next.prev = node.next, node.prev
self.members.remove(node)
if self.root not in self.members:
self.root = self.find_min()
self.nNodes -=1
def merge_linked_list(self,LL2):
for element in self.members&LL2.members:
self.remove_node(element)
self.root.prev.next = LL2.root
LL2.root.prev.next = self.root
self.root.prev, LL2.root.prev = LL2.root.prev, self.root.prev
if LL2.root < self.root:
self.root = LL2.root
self.members = self.members|LL2.members
self.nNodes = len(self.members)
def print_values(self):
print self.root.value
j = self.root.next
while j is not self.root:
print j.value
j = j.next
我的问题是，哈希表是否只占用了没有哈希表的链表的两倍？当我查看哈希表中的Node对象时，它们似乎与当它们是独立的节点对象时位于完全相同的内存位置。例如，如果我创建一个节点：
In: n1 = Node(5)
In: print n1
Out: <__main__.Node instance at 0x1041aa320>
然后将此节点放在集合中：
In: s1 = set()
In: s1.add(n1)
In: print s1
Out: <__main__.Node instance at 0x1041aa320>
这是相同的内存位置。因此，似乎集不复制节点。
我的问题是，大小为n且具有跟踪元素的哈希表的链表的空间复杂度是多少？是n还是2n？使用哈希表跟踪元素有什么基本错误。
我希望这不是重复的。我尝试搜索可以回答此问题的帖子，但没有找到满意的结果。
最佳答案
检查In-memory size of a Python structure和How do I determine the size of an object in Python?以获得确定对象大小的完整答案
我在使用python 3的64位计算机上有这样小的结果
>>> import sys
>>> sys.getsizeof (1)
28
>>> sys.getsizeof (set())
224
>>> sys.getsizeof (set(range(100)))
8416
结果以字节为单位。这可以为您提供关于大集合的提示（它们很大）。
我的问题是，大小为n且具有跟踪元素的哈希表的链表的空间复杂度是多少？是n还是2n？使用哈希表跟踪元素有什么基本错误。
复杂度计算永远不会在n和2n之间产生差异，而优化则会如此。通常说“早期优化是万恶之源”，以警告潜在的优化陷阱。因此，请按照您认为对支持的操作最好的方式进行操作。
关于python - 带有哈希表空间的循环双向链接列表，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/34573318/