python 利用dict构造多重集合multiset类

python 利用dict构造多重集合multiset类

python有set()结构,但是set不允许重复元素出现。如果我们的任务像优先队列那样经常访问最大最小值,那么使用set要比list快。而字典dict的键是set组织的,我们利用data作为key,出现次数作为value可以自己构造一个multiset类。

对照C++的multiset类,设计以下的方法:构造;元素个数,是否为空;修改:插入,删除,清空;取值:最大、最小、计数、存在性.

由于python不能做函数重载,所以没有对multiSet的构造函数添加从其它数据结构的构造方法。但可以视需要再添加。

由于使用字典的值表示键的出现次数,若要求多重集合的元素数可以遍历整个字典的值并累加,但如果字典的键比较多并且访问集合元素数比较频繁,这一步是相当耗时的,所以额外定义一个变量专门保存整个多重集合的大小。

修改集合需要插入、删除和清空。插入时检查当前键是否存在于字典中,若存在则相应值+=1,否则建立这个键并赋值为1。删除操作类似地,检查待删除元素是否存在于字典中,若不存在则什么也不做。存在时若此值为1则删除此键,否则此值自减1。清空操作则是将字典置空并将集合大小置0.

取数操作有最大、最小、查找、计数。直接对字典取max是取的键的最大值,这恰与我们所需相符。字典的键本身是set组织的,用关键字in查找是O(logN)的复杂度,比线性表快。count同样是O(logN)的复杂度。

class multiSet:
    def __init__(self):
        self.container = {}
        self.capSize = 0
    # capacity
    def size(self):
        return self.capSize
    def isEmpty(self):
        return self.capSize==0


    # modifiers:
    def insert(self,v):
        self.capSize+=1
        if(v in self.container):
            self.container[v]+=1
        else:
            self.container[v]=1
    def remove(self,v):
        if v in self.container:
            self.capSize-=1
            if(self.container[v]==1):
                del self.container[v]
            else:
                self.container[v]-=1
    def clear(self):
        self.capSize = 0
        self.capacity = {}

    # Operations:
    def max(self):
        return max(self.container)
    def min(self):
        return min(self.container)
    def find(self,v):
        return v in self.container
    def count(self,v):
        if v in self.container:
            return self.container[v]
        else:
            return 0

发表评论

电子邮件地址不会被公开。 必填项已用*标注