python - 具有哈希表空间的循环双向链表

Question

我目前正在为我自己的个人开发而在 Python 中实现斐波那契堆。在为循环双向链表编写对象类时，我遇到了一个我不确定的问题。

为了对链接列表进行快速成员资格测试(为了更快地执行“删除”和“合并”等操作)，我正在考虑向我的链接添加一个哈希表(一个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？使用哈希表来跟踪元素有什么基本错误吗？

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

Answer 1

检查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

结果以字节为单位。这可以给你一个关于集合有多大的提示(它们相当大)。

My question is, what is the space complexity for a linked list of size n with a hash-table that keeps track of elements. Is it n or 2n? Is there anything elementary wrong about using a hash table to keep track of elements.

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