具有哈希表空间的循环双链接列表

Question

我目前正在Python中实现一个Fibonacci堆，用于我自己的个人开发。在为循环的双链接列表编写对象类时，我遇到了一个我不确定的问题。

为了快速测试链表的成员身份（为了更快地执行"remove"one_answers"merge"等操作），我想在链表类中添加一个哈希表（一个python"set"对象）。请参阅下面我公认的非常不完美的代码，了解我是如何做到这一点的：

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？使用哈希表来跟踪元素有什么基本错误吗。

我希望这不是重复的。我试着搜索一个能回答这个问题的帖子，但没有找到任何令人满意的内容。

Answer 1

检查Python结构的内存大小以及如何在Python中确定对象的大小？用于确定对象大小的完整答案

我在一台64位机器上用python 3 得到了这个小结果

>>> import sys
>>> sys.getsizeof (1)
28
>>> sys.getsizeof (set())
224
>>> sys.getsizeof (set(range(100)))
8416

结果以字节为单位。这可以给你一个关于布景有多大的提示（它们相当大）。

我的问题是，对于一个具有跟踪元素的哈希表的大小为n的链表，其空间复杂度是多少。是n还是2n？使用哈希表来跟踪元素有什么基本错误吗。

复杂度计算从来不会在n和2n之间产生差异优化确实如此。人们常说"早期优化是万恶之源"，以警告潜在的优化陷阱。所以，按照您认为最适合支持的操作进行操作。