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

Question

我正在尝试使用 python 3.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

为了检查一个节点的状态是否在队列中，我使用check_member方法，属性状态为字符串类型，看是否包含在所有字符串状态的集合中的成员。但这还是慢。

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

如何在不使用额外探索集的情况下保持元素的顺序并仍然检查某个元素是否在 O(1) 队列中？

Answer 1

您需要一个 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

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

how to check if the attribute of an instance is member of a queue in O(1)?

python

queue

priority-queue