龙空技术网

Python数据结构与算法57:排序与查找:ADT Map

挂可挂 118

前言:

目前同学们对“python对map排序”大概比较珍视,小伙伴们都需要学习一些“python对map排序”的相关资讯。那么小编也在网上收集了一些关于“python对map排序””的相关内容,希望同学们能喜欢,小伙伴们一起来学习一下吧!

注:本文如涉及到代码,均经过Python 3.7实际运行检验,保证其严谨性。

本文阅读时间约为6分钟。

映射抽象数据类型及Python实现

在Python字典中,我们可以通过“键”访问对应的“值”。字典这种键值关联的方法称为映射(map)。

字典就是这样一种抽象数据类型映射(ADT Map)结构。ADT Map结构是键-值关联的集合。在这个集合中,关键码具有唯一性,我们可以通过关键码唯一确定一个数据值。

抽象数据类型映射(ADT Map)定义的操作如下:

Map()——创建一个空映射,返回空映射对象。put(key, val)——将key-val关联对加入到映射中。若映射中key已存在,则val将替换key的旧关联值。get(key)——给定key,返回关联的数据值。如key不存在,则返回None.del——通过del map[key]的语句形式删除key-val关联。len()——返回映射中key-val关联的数目。in——通过key in map的语句形式,返回key是否存在于关联中,布尔值。

字典的优势在于,给定关键码key,能够很快找到关联的数据值data。 为了达到快速查找的目标,需要一个支持高效查找的ADT(Abstract Data Type,抽象数据类型)实现——可以采用列表数据结构加顺序查找或者二分查找,当然,更为合适的是,使用散列表来实现,因可以达到最快O(1)的性能。

实现抽象数据类型映射

下面,我们用一个Hash Table类来实现ADT Map,该类包含了两个列表作为成员:一个是slot列表,用于保存key;另一个是平行的data列表,用于保存数据项。

在slot列表查找到一个key的位置以后,在data列表对应的相对位置的数据项即为关联数据。

保存key的列表就作为散列表来处理,这样可以迅速查找指定的key。

注意散列表的大小,虽然可以是任意数,但考虑到要让冲突解决算法能有效工作,应该选择为素数。

hashfunction方法采用了简单求余方法来实现散列函数,而冲突解决则采用线性探测“加1”再散列函数。

综上所述,ADT Map的put、get等方法的实现的完全代码如下:

# 实现抽象数据类型映射的实现。class HashTable:    def __init__(self):        self.size = 11        self.slots =  [None] * self.size        self.data = [None] * self.size        # ADT Map的put方法。    def put(self, key, data):        hashvalue = self.hashfunction(key)                if self.slots[hashvalue] == None:  # key不存在的情况。            self.slots[hashvalue] = key            self.data[hashvalue] = data        else:            if self.slots[hashvalue] == key:  # key存在的情况。                self.data[hashvalue] = data  # 替换。            else:                nextslot = self.rehash(hashvalue)                                # 散列冲突,再散列,直到找到空槽或者key。                while self.slots[nextslot] != None and self.slots[nextslot] != key:                    nextslot = self.rehash(nextslot)                                if self.slots[nextslot] == None:                    self.slots[nextslot] = key                    self.data[nextslot] = data                else:                    self.data[nextslot] = data  # 替换。                        def hashfunction(self, key):        return key % self.size        def rehash(self, oldhash):        return (oldhash + 1) % self.size        # ADT Map的get方法。    def get(self, key):        startslot = self.hashfunction(key)  # 标记散列值为查找起点。                data = None        stop = False        found = False        position =  startslot        while self.slots[position] != None and not found and not stop:        # 找到key,直到空槽或者回到起点。            if self.slots[position] == key:                found = True                data = self.data[position]            else:  #未找到key,再散列继续找。                position = self.rehash(position)                if position == startslot:                    stop = True  # 没找到key,回到起点,停下来了。        return data        # 通过特殊方法实现[]访问。    def __getitem__(self, key):        return self.get(key)        def __setitem__(self, key, data):        self.put(key, data)H = HashTable()H[54]="cat"H[26]="dog"H[93]="lion"H[17]="tiger"H[77]="bird"H[31]="cow"H[44]="goat"H[55]="pig"H[20]="chicken"print(H.slots)print(H.data)print(H[20])<<<[77, 44, 55, 20, 26, 93, 17, None, None, 31, 54]['bird', 'goat', 'pig', 'chicken', 'dog', 'lion', 'tiger', None, None, 'cow', 'cat']chicken<<<
散列的算法分析

散列在最好的情况下,可以提供O(1)即常数级的时间复杂度的查找性能。当然,因为实际情况中不免有散列冲突的存在,所以查找比较次数就没这么简单。

评估散列冲突的最重要信息就是负载因子λ,一般来说:

如果λ较小,散列冲突的几率就小,数据项通常会保存在其所属的散列槽中;如果λ较大,意味着散列表填充较满,冲突会越来越多,冲突解决也越来越复杂,也就需要更多的比较来找到空槽;如果采用数据项链的方式,则意味着每条链上的数据项增多。

如果采用线性探测的开放定址法来解决冲突问题(λ在0~1之间),则:

成功的查找,平均需要比对次数为:(1+1/(1-λ))/2。不成功的查找,平均比对次数为:(1+(1/(1-λ))^2)/2。

如果采用数据项链法来解决冲突问题(λ可大于1),则:

成功的查找,平均需要比对次数为:1+λ/2。不成功的查找,平均比对次数为:λ。

To be continued.

标签: #python对map排序