如何检查实例的属性是否是O（1）中队列的成员？

Question

我正在尝试用python3.6设计一个队列数据结构

队列的目的是跟踪具有以下属性的节点对象：

class node(object):
    def __init__(self, state, parent):
        self.state = state
        self.parent = parent

我希望避免将状态相同的节点合并到队列中。因此我设计了以下队列：

class queue(object):
    def __init__(self):
        self.list = []
        self.explored = set()

    def insert(self, element):
        self.list = [element] + self.list
        self.explored.add(str(element.state))
        return self.list

    def pop(self):
        oldest_element = self.list.pop()
        self.explored.remove(str(oldest_element.state))
        return oldest_element

    def empty(self):
       return len(self.list) == 0

    def check_member(self, other):
       return other in self.explored

为了检查节点的状态是否在队列中，我使用属性state作为字符串类型的check_member方法来查看是否包含在集合中以及成员的所有字符串状态。但这仍然是缓慢的。你知道吗

那么是否可以检查一个实例是否与另一个实例具有相同的属性，而其他属性可能有所不同？例如，两个节点，状态属性相同，但父属性不同。

如何保持元素的顺序，并且仍然检查O（1）中的某个元素是否在队列中，而不使用额外的探索集？

Answer 1

如果可能的话，只需附加对象本身而不调用它们的状态就可以节省时间，但至少不调用str（）可以将时间减少一半。似乎没有必要。你知道吗

>>> setup="""class Obj(object):
...     def __init__(self):
...         self.str = "str"
...         
... tst_ob = Obj()
... 
... container = list()"""
>>> 
>>> test="""container.append(tst_ob.str)"""
>>> 
>>> from timeit import timeit
>>> 
>>> timeit(test, setup=setup)
0.16077090999988286





>>> setup="""class Obj(object):
...     def __init__(self):
...         self.str = "str"
...         
... tst_ob = Obj()
... 
... container = set()"""
>>> 
>>> test="""container.add(str(tst_ob.str))"""
>>> 
>>> from timeit import timeit
>>> 
>>> timeit(test, setup=setup)
0.29905145599991556

Answer 2

您需要一个set/dict类型的对象来实现O(1)包含的检查复杂性。最简单的方法是使用OrderedDict作为底层数据容器。使用状态作为键，节点作为值。通过这种方式，国家被强制要求是唯一的，而秩序仍然得以维持：

from collections import OrderedDict

class queue(object):
    def __init__(self):
        self.q = OrderedDict()

    def insert(self, element):
        s = str(element.state)
        if s not in self.q:
             self.q[s] = element  # adds to the end

    def pop(self):
        return self.q.popitem(0)[1]  # returns the node from beginning

    def empty(self):
       return not self.q

    def check_member(self, element):
       return str(element.state) in self.q